我偶然发现了Haskell和FP,并对这些可能性感到震惊.我内心的旧数学书呆子可以毫不费力地为实际有用的目的编写天真的代码.然而,尽管所有的阅读,我仍然很难理解如何不打出一些令人惊讶的性能瓶颈.
因此,我使用简单的实现编写了非常短的代码片段,然后尝试进行少量更改以查看性能如何响应.这里有一个我真的无法理解的例子......我写了这个函数,找到了约瑟夫斯问题的解决方案,目的是有一个天真的列表实现.
m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"
whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers
根据RTS,后者运行时间为190毫秒,生产率为63%.
然后我想要尝试的第一件事是删除(长度士兵-1)并用递减的整数替换它.
运行时间最长可达900毫秒,生产率降至16%,并且使用的内存比上述简单代码多47倍!所以我添加了严格的评估,强制使用Int类型,尝试删除全局变量等等,但没有多大帮助.我只是无法理解这种放缓.
m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"
whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` …performance haskell functional-programming lazy-evaluation josephus
在第一次看到它之后四年回到Haskell.我总是对表现力感到惊讶,并且因为我无法预测空间/时间表现而感到困惑.
作为一个热身,我开始翻译我用C++编写的一个小玩具程序.这是关于Scrabble的"作弊".您输入您的游戏,它会输出您可能会玩的单词,单独使用您的信件或通过在董事会上交叉信件.
整个事情围绕着一个在启动时预加载的字典.然后将这些单词与其字谜一起存储为地图中的列表.键是排序字母的字符串.一个例子会说得更清楚:
Key : "AEHPS" Value : ["HEAPS","PHASE","SHAPE"]
C++版本一次一个地读取字典的~320000个单词,总共大约200ms.生成的数据结构是存储在a中的哈希映射array<99991, vector<string>>,占用大约12兆字节的内存.
Haskell版本在大约5秒内读取相同的字典,程序堆大小膨胀到400兆字节!我在改变的值类型Data.Map从[String]以[ByteString]节省一些内存,并带来了程序内存消耗下降到大约290兆字节.这仍然是我的C++版本的24倍.这不仅仅是"开销",即使Data.Map是树而不是数组.
所以我认为我做错了什么.
整个模块在这里可见:(不建议使用的链接)
我想我的麻烦与Data.Map逐步建立的方式有关,在以前的版本中增长？或者与数据结构本身？或者是其他东西 ？
我会尝试其他的解决方案,如Data.HashMap,或填补了Data.Map用fromListWith.不过,我想对这里发生的事情有所了解.非常感谢任何见解!
简短回答:
使用Data.Map.Strict,强制评估值元素,并将键存储为ByteStrings也使得将内存占用量分成近3的奇迹.结果是100Meg,这只是std::multimap<std::string, std::string>C++ 标准的两倍.相同的数据集.虽然没有加速.Git已更新.
非常感谢所有贡献者,这里有一些有趣的内容!