代码之家 › 专栏 › 技术社区 › cjs

使用vlist的哈希表

complexity-theory hashtable functional-programming haskell data-structures

5

cjs · 技术社区 · 16 年前

此外,从我看来,这种数据结构虽然可能具有与哈希表相同的大-O复杂性,但它会慢一些,因为它会进行额外的查找。有谁愿意详细分析到底有多慢,最好包括缓存行为?在没有碰撞或多次碰撞的情况下,两者之间的性能关系如何变化?

2 回复 | 直到 16 年前

1

4

Norman Ramsey 16 年前

我看了一眼这篇论文非常

2

1

Edward Kmett 16 年前

Hrmm本文提出的数据结构似乎存在一些问题。

即兴,第一次提到的天真的vlist似乎需要唯一的引用,以便获得任何接近所提议的时间保证。你失去了大部分人分享尾巴的能力。您可以共享列表后面的小节点,但当您将某些内容放到仍处于活动状态的vlist的cdr上时,您将不得不复制最大的vlist节点。这个费用与复制整个清单的费用成正比。

在后面提到的2d修改中,它再次变为常量,但它是一个相当大的常量,因为您最终至少复制了一个页面列表(或者更糟的是,vlist)的头部和列表中的第一个页面。