來自字符串列表的Haskell數組

所以我有一個字符串列表，任務是計算每個字符串在該列表中能夠滿足的次數。我使用貼圖：來自字符串列表的Haskell數組

freqMap = M.fromListWith (+) [(c, 1) | c <- subs]

，只是排序：

frequency list = map (\l -> (length l, head l)) $ group (sort list)

但是這一切都爲我的任務太慢 - 原始列表是非常大的。我聽說，使用無箱陣列可以非常快。喜歡的整數列表：

histogram bounds xs = accumArray (+) 0 bounds [(x, 1) | x <- xs]

由於字符串不是九類的成員，問題是：是否有可能建立從字符串列表數組？

2017-10-15 Triostrong

感謝您的回覆！我試過甚至只計算每個字符串的實例（沒有長度）： freqMap = M.fromListWith（+）[（c，1）| c < - subs] 但它看起來性能仍然與group.sort版本相同。分析還顯示，大部分時間都花在排序或freqMap評估上。 – Triostrong

您是否嘗試過使用['Data.HashMap']（https://hackage.haskell.org/package/unordered-containers-0.2.8.0/docs/Data-HashMap-Lazy.html#t:HashMap）？可以加快速度。 – hnefatl

謝謝！ HashMap比其他變體工作得更好。雖然它仍然不是取消裝箱的數組，而是一棵樹，但我想，它將花費太多內存來將每個可能的哈希值編入索引。 – Triostrong

Data.HashMap（lazy/strict）是香草haskell地圖的更快版本 - 如果瓶頸主要是更新/查找速度，使用它們可能會加速您的操作。

最好的部分是，你可以保持你已經寫好的乾淨的方法，而不必寫（通常是醜陋的）與數組交互的代碼。

2017-10-15 21:56:57 hnefatl

感謝您的建議，現在排序不是我的瓶頸。在計數階段我有大約50％的改善。 – Triostrong

回答