优化可变数组状态重操作代码 [英] Optimizing mutable array state heavy manipulation code
问题描述
我一直在努力在hackerrank上完成
我的Haskell解决方案
<$ p $导入Data.Vector（Vector（..），fromList，（！），（//），toList）
导入Data.Vector.Mutable
导入限定数据。 Vector as V
import Data.ByteString.Lazy.Char8（ByteString（..））
将合格的Data.ByteString.Lazy.Char8导入为L
import Data.ByteString.Lazy.Builder
导入Data.Maybe
导入Control.Applicative
导入Data.Monoid
导入前导隐藏（长度）
readInt'= fst。来自Just。 L.readInt
toB [] = mempty
toB（x：xs）= string8（show x）< string8<> toB xs
main = do
[firstLine，secondLine]< - L.lines< $> L.getContents
let [n，k] = map readInt'$ L.words firstLine
let xs = largestPermutation nk $ fromList $ map readInt'$ Prelude.take n $ L.words secondLine
L.putStrLn $ toLazyByteString $ toB $ toList xs
largestPermutation nkv
| i> = 1 || k == 0 = v
| n == x = maximumPermutation（n-1）k v
|否则= maximumPermutation（n-1）（k-1）（replaceOne nx（i + 1）（V.modify（\v'-> write v'in）v））
where l = V.长度v
i = l - n
x = v！i
replaceOne nxiv
| n == h = V.modify（\v' - > write v'i x）v
|否则= replaceOne nx（i + 1）v
其中h = v！i
大多数我发现不断更新2个阵列的最佳解决方案。一个数组是主要目标，另一个数组是用于快速索引查找。
更好的Java解决方案
public static void main（String [] args）{
Scanner input = new Scanner（System.in）;
int n = input.nextInt（）;
int k = input.nextInt（）;
int [] a = new int [n];
int [] index = new int [n + 1];
for（int i = 0; i< n; i ++）{
a [i] = input.nextInt（）;
index [a [i]] = i;
}
for（int i = 0; i< n& k> 0; i ++）{
if（a [i] == n - i）{
继续;
}
a [index [n - i]] = a [i];
index [a [i]] = index [n - i];
a [i] = n - i;
index [n - i] = i;
k--;
}
for（int i = 0; i
$ / code $ / pre
$ b $ 我的问题是
- 这个算法在Haskell中的优雅和快速实现是什么？
- 有没有比Java解决方案更快的方法来解决这个问题？
-
解决方案你可以对可变数组进行的一种优化根本不是使用它们。特别是，您链接的问题有一个正确的折叠解决方案。
这个想法是，您折叠列表并贪婪地将具有最大值的项目交换到右边，并维护已在 Data.Map ：
$ p $ 将限定的Data.Map作为M
导入Data.Map（空，插入）
solve :: Int - > Int - > [Int] - > [Int]
求解nk xs = foldr go（\ _ _ - > []）xs n空k
其中
转到x运行imk
- 转出预算做一个交换或不需要交换
| k == 0 || y == i = y：run（pred i）m k
- 交换并记录在地图中进行的交换
|否则= i：运行（pred i）（插入iym）（k - 1）
其中
- 找到当前位置的值与$ b $替换= find x
find k =案例M.lookup公里的
只是 - >找到
Nothing - > k
在上面， run 是一个函数它给出了反向索引 i ，当前映射 m 和剩余交换预算 k ，解决列表的其余部分。通过反向索引我的意思是指向相反方向的列表： n，n - 1，...，1 。
折叠函数 go 在每个步骤中构建 run 函数更新已传递的 i ， m 和 k 的值到下一步。最后，我们用初始参数 i = n ， m = empty 和初始交换预算<$ c
$ b $ p find 中的递归搜索可以优化出来维护一个反向映射，但是这已经比你发布的java代码执行得快得多。
编辑：以上解决方案仍支付树访问的对数成本。以下是使用可变替代解决方案 STUArray 和monadic fold foldM _ ，它实际上执行速度比上面快：
import Control.Monad.ST（ST）
import Control.Monad（foldM_）
import Data.Array.Unboxed（UArray，elems，listArray，数组）
导入Data.Array.ST（STUArray，readArray，writeArray，runSTUArray，thaw）
- 前3个参数是作用域的范围，它将被curried
swap： ：STUArray s Int Int - > STUArray s Int Int - > Int
- > Int - > Int - > ST s Int
swap _ _ _ 0 _ =返回0 - 超出预算以进行交换
swap arr rev nki = do
xi< - readArray arr i
如果xi + i == n + 1
，则返回k - 不需要交换
else else - 交换并减少预算
j< - readArray rev（n + 1 - i）
writeArray rev xi j
writeArray arr j xi
writeArray arr i（n + 1 - i）
return $ pred k
解决方案： ：Int - > Int - > [Int] - > [int]
求解nk xs = elems $ runSTUArray $ do
arr< - thaw（listArray（1，n）xs :: UArray Int Int）
rev< - thaw（array （1，n）（zip xs [1 ..]）:: UArray Int Int）
foldM_（swap arr rev n）k [1..n]
return arr
I've been trying to complete this exercise on hackerrank in time. But my following Haskell solution fails on test case 13 to 15 due to time out.
My Haskell solution
import Data.Vector(Vector(..),fromList,(!),(//),toList)
import Data.Vector.Mutable
import qualified Data.Vector as V
import Data.ByteString.Lazy.Char8 (ByteString(..))
import qualified Data.ByteString.Lazy.Char8 as L
import Data.ByteString.Lazy.Builder
import Data.Maybe
import Control.Applicative
import Data.Monoid
import Prelude hiding (length)
readInt' = fst . fromJust . L.readInt
toB [] = mempty
toB (x:xs) = string8 (show x) <> string8 " " <> toB xs
main = do
[firstLine, secondLine] <- L.lines <$> L.getContents
let [n,k] = map readInt' $ L.words firstLine
let xs = largestPermutation n k $ fromList $ map readInt' $ Prelude.take n $ L.words secondLine
L.putStrLn $ toLazyByteString $ toB $ toList xs
largestPermutation n k v
| i >= l || k == 0 = v
| n == x = largestPermutation (n-1) k v
| otherwise = largestPermutation (n-1) (k-1) (replaceOne n x (i+1) (V.modify (\v' -> write v' i n) v))
where l = V.length v
i = l - n
x = v!i
replaceOne n x i v
| n == h = V.modify (\v' -> write v' i x ) v
| otherwise = replaceOne n x (i+1) v
where h = v!i
Most optimal solution that I've found constantly updates 2 arrays. One array being the main target, and other array being for fast index look ups.
Better Java solution
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int k = input.nextInt();
int[] a = new int[n];
int[] index = new int[n + 1];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
index[a[i]] = i;
}
for (int i = 0; i < n && k > 0; i++) {
if (a[i] == n - i) {
continue;
}
a[index[n - i]] = a[i];
index[a[i]] = index[n - i];
a[i] = n - i;
index[n - i] = i;
k--;
}
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
}
My question is
- What's the elegant and fast implementation of this algorithm in Haskell?
- Is there a faster way to do this problem than the Java solution?
- How should I deal with heavy array update elegantly and yet efficiently in Haskell in general?
One optimization you can do to mutable arrays is not to use them at all. In particular, the problem you have linked to has a right fold solution.
The idea being that you fold the list and greedily swap the items with the largest value to the right and maintain swaps already made in a Data.Map:
import qualified Data.Map as M
import Data.Map (empty, insert)
solve :: Int -> Int -> [Int] -> [Int]
solve n k xs = foldr go (\_ _ _ -> []) xs n empty k
where
go x run i m k
-- out of budget to do a swap or no swap necessary
| k == 0 || y == i = y : run (pred i) m k
-- make a swap and record the swap made in the map
| otherwise = i : run (pred i) (insert i y m) (k - 1)
where
-- find the value current position is swapped with
y = find x
find k = case M.lookup k m of
Just a -> find a
Nothing -> k
In above, run is a function which given the reverse index i, current mapping m and the remaining swap budget k, solves the rest of the list onwards. By reverse index I mean indices of the list in the reverse direction: n, n - 1, ..., 1.
The folding function go, builds the run function at each step by updating values of i, m and k which are passed to the next step. At the end we call this function with initial parameters i = n, m = empty and initial swap budget k.
The recursive search in find can be optimized out by maintaining a reverse map, but this already performs much faster than the java code you have posted.
Edit: Above solution, still pays a logarithmic cost for tree access. Here is an alternative solution using mutable STUArray and monadic fold foldM_, which in fact performs faster than above:
import Control.Monad.ST (ST)
import Control.Monad (foldM_)
import Data.Array.Unboxed (UArray, elems, listArray, array)
import Data.Array.ST (STUArray, readArray, writeArray, runSTUArray, thaw)
-- first 3 args are the scope, which will be curried
swap :: STUArray s Int Int -> STUArray s Int Int -> Int
-> Int -> Int -> ST s Int
swap _ _ _ 0 _ = return 0 -- out of budget to make a swap
swap arr rev n k i = do
xi <- readArray arr i
if xi + i == n + 1
then return k -- no swap necessary
else do -- make a swap, and reduce budget
j <- readArray rev (n + 1 - i)
writeArray rev xi j
writeArray arr j xi
writeArray arr i (n + 1 - i)
return $ pred k
solve :: Int -> Int -> [Int] -> [Int]
solve n k xs = elems $ runSTUArray $ do
arr <- thaw (listArray (1, n) xs :: UArray Int Int)
rev <- thaw (array (1, n) (zip xs [1..]) :: UArray Int Int)
foldM_ (swap arr rev n) k [1..n]
return arr
这篇关于优化可变数组状态重操作代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
