优化可变数组状态重操作代码
Optimizing mutable array state heavy manipulation code
我一直在努力及时完成 this 关于 hackerrank 的练习。
但是由于超时，我的以下 Haskell 解决方案在测试用例 13 到 15 上失败。
我的Haskell解决方案
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
我发现的最佳解决方案是不断更新 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) {
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] + " ");
}
}
我的问题是
- 这个算法在Haskell中优雅而快速的实现是什么？
- 有没有比 Java 解决方案更快的方法来解决这个问题？
- 一般来说，在 Haskell 中，我应该如何优雅而高效地处理繁重的数组更新？
您可以对可变数组进行的一种优化是完全不使用它们。特别是，您链接到的问题有一个正确的折叠解决方案。
想法是折叠列表并贪婪地将具有最大值的项目向右交换并保持已经在 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
在上面，run 是给定 反向索引 i、当前映射 m 和剩余交换预算 k，解决列表的其余部分。通过 reverse index 我的意思是反向列表的索引：n, n - 1, ..., 1.
折叠函数go，通过更新传递给下一步。最后，我们使用初始参数 i = n、m = empty 和初始交换预算 k.
调用此函数
find 中的递归搜索可以通过维护反向映射来优化，但这已经比您发布的 java 代码执行得快得多。
编辑：以上解决方案，仍然为树访问支付对数成本。这是一个使用可变 STUArray and monadic fold foldM_ 的替代解决方案，它实际上比上面的执行速度更快：
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
不完全是 #2 的答案，但有一个左折叠解决方案需要一次在内存中加载最多 ~K 个值。
因为问题涉及排列，所以我们知道 1 到 N 将出现在输出中。如果 K > 0，至少前 K 项将是 N、N-1、... N-K，因为我们至少可以负担 K 次交换。此外，我们希望一些 (K/N) 位数字处于最佳位置。
这表明一个算法：
初始化地图/字典并将输入 xs 扫描为 zip xs [n, n-1..]。对于每个 (x, i)，如果 x \= i，我们 'decrement' K 并更新字典 s.t。 dct[i] = x。当 K == 0（没有交换）或我们 运行 没有输入（可以输出 {N, N-1, ... 1}）时，此过程终止。
接下来，如果我们还有更多 x <- xs，我们会查看每一个并打印 x 如果 x 不在我们的字典中，否则 dct[x]。
仅当我们的字典包含循环时，上述算法才能产生最佳排列。在这种情况下，我们使用 |cycle| 交换来移动绝对值 >= K 的元素。但这意味着我们将一个元素移到了它原来的位置！所以我们总是可以在每个周期保存一个交换（即增量 K）。
最后，这给出了内存效率算法。
第0步：得到N、K
第1步：读取输入排列，输出{N, N-1, ... N-K-E}, N <- N - K - E, K <- 0, 更新字典如上，
其中 E = 元素数 X 等于 N -（X 的索引）
第2步：从dict中删除并计算周期；让 cycles = 循环数；如果 cycles > 0，让 K <- |cycles|，转到第 1 步，
否则转到第3步。我们可以通过优化dict来提高这一步的效率。
第 3 步：按原样输出其余输入。
下面的 Python 代码实现了这个想法，如果使用更好的循环检测，可以做得非常快。当然，数据最好分块读取，不像下面那样。
from collections import deque
n, t = map(int, raw_input().split())
xs = deque(map(int, raw_input().split()))
dct = {}
cycles = True
while cycles:
while t > 0 and xs:
x = xs.popleft()
if x != n:
dct[n] = x
t -= 1
print n,
n -= 1
cycles = False
for k, v in dct.items():
visited = set()
cycle = False
while v in dct:
if v in visited:
cycle = True
break
visited.add(v)
v, buf = dct[v], v
dct[buf] = v
if cycle:
cycles = True
for i in visited:
del dct[i]
t += 1
else:
dct[k] = v
while xs:
x = xs.popleft()
print dct.get(x, x),
我一直在努力及时完成 this 关于 hackerrank 的练习。
但是由于超时，我的以下 Haskell 解决方案在测试用例 13 到 15 上失败。
我的Haskell解决方案
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
我发现的最佳解决方案是不断更新 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) {
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] + " ");
}
}
我的问题是
- 这个算法在Haskell中优雅而快速的实现是什么？
- 有没有比 Java 解决方案更快的方法来解决这个问题？
- 一般来说，在 Haskell 中，我应该如何优雅而高效地处理繁重的数组更新？
您可以对可变数组进行的一种优化是完全不使用它们。特别是，您链接到的问题有一个正确的折叠解决方案。
想法是折叠列表并贪婪地将具有最大值的项目向右交换并保持已经在 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
在上面，run 是给定 反向索引 i、当前映射 m 和剩余交换预算 k，解决列表的其余部分。通过 reverse index 我的意思是反向列表的索引：n, n - 1, ..., 1.
折叠函数go，通过更新传递给下一步。最后，我们使用初始参数 i = n、m = empty 和初始交换预算 k.
find 中的递归搜索可以通过维护反向映射来优化，但这已经比您发布的 java 代码执行得快得多。
编辑：以上解决方案，仍然为树访问支付对数成本。这是一个使用可变 STUArray and monadic fold foldM_ 的替代解决方案，它实际上比上面的执行速度更快：
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
不完全是 #2 的答案，但有一个左折叠解决方案需要一次在内存中加载最多 ~K 个值。
因为问题涉及排列，所以我们知道 1 到 N 将出现在输出中。如果 K > 0，至少前 K 项将是 N、N-1、... N-K，因为我们至少可以负担 K 次交换。此外，我们希望一些 (K/N) 位数字处于最佳位置。
这表明一个算法：
初始化地图/字典并将输入 xs 扫描为 zip xs [n, n-1..]。对于每个 (x, i)，如果 x \= i，我们 'decrement' K 并更新字典 s.t。 dct[i] = x。当 K == 0（没有交换）或我们 运行 没有输入（可以输出 {N, N-1, ... 1}）时，此过程终止。
接下来，如果我们还有更多 x <- xs，我们会查看每一个并打印 x 如果 x 不在我们的字典中，否则 dct[x]。
仅当我们的字典包含循环时，上述算法才能产生最佳排列。在这种情况下，我们使用 |cycle| 交换来移动绝对值 >= K 的元素。但这意味着我们将一个元素移到了它原来的位置！所以我们总是可以在每个周期保存一个交换（即增量 K）。
最后，这给出了内存效率算法。
第0步：得到N、K
第1步：读取输入排列，输出{N, N-1, ... N-K-E}, N <- N - K - E, K <- 0, 更新字典如上，
其中 E = 元素数 X 等于 N -（X 的索引）
第2步：从dict中删除并计算周期；让 cycles = 循环数；如果 cycles > 0，让 K <- |cycles|，转到第 1 步，
否则转到第3步。我们可以通过优化dict来提高这一步的效率。
第 3 步：按原样输出其余输入。
下面的 Python 代码实现了这个想法，如果使用更好的循环检测，可以做得非常快。当然，数据最好分块读取，不像下面那样。
from collections import deque
n, t = map(int, raw_input().split())
xs = deque(map(int, raw_input().split()))
dct = {}
cycles = True
while cycles:
while t > 0 and xs:
x = xs.popleft()
if x != n:
dct[n] = x
t -= 1
print n,
n -= 1
cycles = False
for k, v in dct.items():
visited = set()
cycle = False
while v in dct:
if v in visited:
cycle = True
break
visited.add(v)
v, buf = dct[v], v
dct[buf] = v
if cycle:
cycles = True
for i in visited:
del dct[i]
t += 1
else:
dct[k] = v
while xs:
x = xs.popleft()
print dct.get(x, x),