标签: unordered-containers

数据

首先,让我们生成一些输入,以便我们有具体的数据来讨论:

python -c 'for f in xrange(4000000):  print f' > input.txt

这将生成一个input.txt包含0到3999999之间的数字的文件,每个文件都在自己的行上.这意味着我们应该有一个包含4,000,000行的文件,最多可添加30,888,890字节,大约29 MiB.

一切都作为清单

是的,让我们将所有内容加载到内存中[Text]:

import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL

main :: IO ()
main = do
hs <- (runResourceT
          $ CB.sourceFile "input.txt"
         $$ CT.decode CT.utf8
         =$ CT.lines
         =$ CL.fold (\b a -> a `seq` b `seq` a:b) [])
print $ head hs

并运行它:

[1 of 1] …

在处理哈希映射时,我已经看到了一些处理哈希冲突的策略,但我们提出了一些不同的东西.我想知道这是否是新事物.

只有散列和将要散列的数据结构可以使用时,此版本的散列映射才有效.(hashable在Haskell中就是这种情况,我们建议实现这种方法.)

我们的想法是,不是在哈希映射的每个单元格中存储列表或数组,而是存储递归哈希映射.这个递归哈希映射的唯一区别是你使用不同的盐.这样,哈希映射的一个级别上的哈希冲突很可能不是下一级别的哈希冲突.因此,插入这样的哈希映射不再是O(此哈希上的冲突数),而是O(这种冲突在递归时发生的级别数),这很可能更好.

可以在此处找到更详细的说明和实现:

https://github.com/tibbe/unordered-containers/pull/217/files/58af4519ace34c5f7d3c1359907ff75e27b9cdb8#diff-ba23e0f18c79cb873ac5375367524cfaR114

我一直在尝试确保使用ghc-heap-view包及其提供的utils的Haskell程序的内存模型的严格性，当我发现HashMap插入序列中的s似乎不在NF中时， 。我尝试打印堆树，的确显示出一些问题。然后，我尝试了另一种插入元素的方式（使用union和singleton），但这次严格了。

有人可以解释为什么会这样，并建议我是否可以做些什么来使insert行为与其他方法相同？

这是我的测试代码：

module Main where

import           Control.Exception           (evaluate)
import           Data.Foldable
import           Data.HashMap.Strict         (HashMap)
import qualified Data.HashMap.Strict         as HM
import           GHC.HeapView

test1 :: HashMap Int Int
test1 = foldl' (\m v -> HM.insert v v m) HM.empty [0..5]

test2 :: HashMap Int Int
test2 = foldl' (\m v -> HM.union (HM.singleton v v) m) HM.empty [0..5]

main :: IO ()
main = do
  putStrLn "HeapTree for test1"
  t1 <- evaluate test1 …