Mat*_*man 24 functional-programming hashtable
有没有办法在纯函数式语言中有效地实现哈希表？似乎对哈希表的任何更改都需要创建原始哈希表的副本.我肯定错过了什么.散列表是非常重要的数据结构,如果没有它们,编程语言就会受到限制.
Jon*_*rop 20
有没有办法在纯函数式语言中有效地实现哈希表？
散列表是抽象"字典"或"关联数组"数据结构的具体实现.所以我认为你真的想问一下纯函数字典与命令式哈希表相比的效率.
似乎对哈希表的任何更改都需要创建原始哈希表的副本.
是的,哈希表本质上是必要的,没有直接的纯功能等价物.也许最相似的纯功能字典类型是散列特里,但由于分配和间接,它们比散列表慢得多.
我肯定错过了什么.散列表是非常重要的数据结构,如果没有它们,编程语言就会受到限制.
字典是一个非常重要的数据结构(尽管值得注意的是,在Perl使它们在20世纪90年代流行之前,它们在主流中很少见,因此人们编写了几十年而没有字典的好处).我同意哈希表也很重要,因为它们通常是迄今为止最有效的词典.
有许多纯功能词典:
平衡树(红黑,AVL,重量平衡,指树等),例如Map在OCaml和F#以及Data.MapHaskell中.
哈希尝试,例如PersistentHashMap在Clojure中.
但是,这些纯粹的功能字典都远不是一个体面的哈希表(如.NET慢Dictionary).
请注意Haskell基准测试将哈希表与纯功能词典进行比较,声称纯功能词典具有竞争性.正确的结论是Haskell的哈希表效率很低,几乎和纯功能词典一样慢.例如,如果您与.NET进行比较,您会发现.NET Dictionary可以比Haskell的哈希表快26倍!
我想要真正总结一下你在努力总结Haskell的性能,你需要测试更多的操作,使用非荒谬的键类型(兼作键,什么？),不要
-N8无缘无故地使用,并与之比较第三种语言,也包括其参数类型,如Java(在大多数情况下Java具有可接受的性能),以查看它是否是常见的装箱问题或GHC运行时的一些更严重的错误.这些基准测试是沿着这些方向进行的(和当前哈希表实现一样快〜2倍).
这正是我指的那种错误信息.在这个上下文中不要关注Haskell的哈希表,只要看一下最快的哈希表(即不是Haskell)和最快的纯功能词典的性能.
哈希表可以用类似于Haskell中的ST monad来实现,它基本上将IO动作包装在纯粹的功能界面中.它通过强制按顺序执行IO操作来实现,因此它保持引用透明性:您无法访问哈希表的旧"版本".
请参阅:hackage.haskell.org/package/hashtables
现有的答案都有很好的分享点,我想我只想再添加一个数据:比较一些不同的关联数据结构的性能.
测试包括顺序插入然后查找并添加数组的元素.这个测试并不是非常严格,不应该这样,它只是表明期待什么.
首先在Java中使用HashMap不同步的Map实现:
import java.util.Map;
import java.util.HashMap;
class HashTest {
public static void main (String[] args)
{
Map <Integer, Integer> map = new HashMap<Integer, Integer> ();
int n = Integer.parseInt (args [0]);
for (int i = 0; i < n; i++)
{
map.put (i, i);
}
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += map.get (i);
}
System.out.println ("" + sum);
}
}
然后使用Gregory Collins(它在hashtables包中)完成的最近哈希表工作的Haskell实现.这可以是纯粹的(通过STmonad)或不纯的IO,我在IO这里使用的版本:
{-# LANGUAGE ScopedTypeVariables, BangPatterns #-}
module Main where
import Control.Monad
import qualified Data.HashTable.IO as HashTable
import System.Environment
main :: IO ()
main = do
n <- read `fmap` head `fmap` getArgs
ht :: HashTable.BasicHashTable Int Int <- HashTable.new
mapM_ (\v -> HashTable.insert ht v v) [0 .. n - 1]
x <- foldM (\ !s i -> HashTable.lookup ht i >>=
maybe undefined (return . (s +)))
(0 :: Int) [0 .. n - 1]
print x
最后,使用HashMaphackage(来自hashmap包)的不可变实现:
module Main where
import Data.List (foldl')
import qualified Data.HashMap as HashMap
import System.Environment
main :: IO ()
main = do
n <- read `fmap` head `fmap` getArgs
let
hashmap =
foldl' (\ht v -> HashMap.insert v v ht)
HashMap.empty [0 :: Int .. n - 1]
let x = foldl' (\ s i -> hashmap HashMap.! i + s) 0 [0 .. n - 1]
print x
检查n = 10,000,000的性能,我发现总运行时间如下:
将其降低到n = 1,000,000,我们得到:
这很有趣有两个原因:
这似乎表明,在像Haskell和Java这样的语言盒装地图的键中看到了这个拳击的重大打击.不需要的语言,或者可以取消打开键和值的语言,可能会看到几倍的性能.
显然,这些实现并不是最快的,但我会说使用Java作为基线,它们至少可以接受/可用于许多目的(尽管可能更熟悉Java智慧的人可以说HashMap是否被认为是合理的).
我会注意到,与HashTable相比,Haskell HashMap占用了大量空间.
Haskell程序是使用GHC 7.0.3编译的-O2 -threaded,并且只+RTS -s运行运行时GC统计信息的标志.Java是使用OpenJDK 1.7编译的.