相关疑难解决方法(0)

将非负数Integer转换为其数字列表通常如下所示:

import Data.Char

digits :: Integer -> [Int]
digits = (map digitToInt) . show

我试图找到一种更直接的方式来执行任务,而不涉及字符串转换,但我无法想出更快的东西.

到目前为止我一直在尝试的事情:

基线:

digits :: Int -> [Int]
digits = (map digitToInt) . show

从StackOverflow上的另一个问题得到这个:

digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)

试着自己动手:

digits3 :: Int -> [Int]
digits3 = reverse . revDigits3

revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
               (0, digit) -> [digit]
               (rest, …

我现在已经实现了另一个 SHA3​​候选者,即Grøstl.这仍然在进行中(非常如此),但目前224位版本通过了所有KAT.所以现在我想知道性能(再次: - >).这次的不同之处在于,我选择更接近地镜像(优化的)C实现,即我创建了一个从C到Haskell的端口.优化的C版本使用表查找来实现该算法.此外,代码主要基于更新包含64位字的数组.因此,我选择在Haskell中使用可变的无盒载体.

我的Grøstl代码可以在这里找到:https://github.com/hakoja/SHA3/blob/master/Data/Digest/GroestlMutable.hs

该算法的简短描述:它是一个Merkle-Damgård构造,只要有512位的消息块,就迭代一个压缩函数(在我的代码中为f512M).压缩函数非常简单:它只运行两个不同的独立512位排列P和Q(我的代码中的permP和permQ)并组合它们的输出.它的这些排列是由查找表实现的.

Q1)困扰我的第一件事是使用可变向量使我的代码看起来非常难看.这是我第一次在Haskell中编写任何主要的可变代码,所以我真的不知道如何改进它.关于如何更好地构建monadic代码的任何提示都将受到欢迎.

Q2)第二是表现.实际上它并不太糟糕,因为目前Haskell代码只慢了3倍.使用GHC-7.2.1并编译如下:

ghc -O2 -Odph -fllvm -optlo-O3 -optlo-loop-reduce -optlo-loop-deletion

Haskell代码使用60秒.输入约为1GB,而C版本使用21-22s.但有一些我觉得奇怪的事情:

(1)如果我尝试内联rnd512QM,代码需要4倍的时间,但如果我内联rnd512PM没有任何反应!为什么会这样？这两个功能几乎相同!

(2)这可能更难.我一直在尝试并行执行两个排列.但目前无济于事.这是我尝试过的一个例子:

f512 h m = V.force outP `par` (V.force outQ `pseq` (V.zipWith3 xor3 h outP outQ))
   where xor3 x1 x2 x3 = x1 `xor` x2 `xor` x3
         inP = V.zipWith xor h m
         outP = permP inP
         outQ = permQ m …