me_*_*and 19 language-agnostic algorithm data-structures
我提出了一种数据结构,它结合了链表的一些优点和固定大小数组的一些优点.这对我来说似乎非常明显,所以我希望有人能够想到它并将其命名.有谁知道这是什么叫:
拿一个小的固定大小的阵列.如果要放入数组中的元素数量大于数组的大小,请添加一个新数组以及旧方和新方之间的任何指针.
因此你有:
Static array
—————————————————————————
|1|2|3|4|5|6|7|8|9|a|b|c|
—————————————————————————
Linked list
———— ———— ———— ———— ————
|1|*->|2|*->|3|*->|4|*->|5|*->NULL
———— ———— ———— ———— ————
My thing:
———————————— ————————————
|1|2|3|4|5|*->|6|7|8|9|a|*->NULL
———————————— ————————————
编辑:作为参考,该算法提供相当差的最坏情况添加/删除性能,并且平均情况不是更好.我的方案的一大优势是提高了读取操作的缓存性能.
编辑赏金:Antal SZ的答案是如此完整和精心研究,我想为他们提供赏金.显然Stack Overflow不让我接受答案,一旦我提供赏金,所以我将不得不等待(诚然,我有点滥用意图赏金系统,虽然这是为了奖励某人的优秀回答).当然,如果有人确实能够提供更好的答案,给他们更多的权力,他们肯定会获得赏金!
编辑重新命名:我对你称之为什么并不感兴趣,除非你这么称呼它,因为那是主题上的权威人士所称的.如果这是你想出的名字,我不感兴趣.我想要的是一个名字,我可以在教科书和谷歌中查找.(另外,这里有一个技巧:安塔尔的答案是什么,我一直在寻找.如果你的答案是没有"展开链接列表"没有.很充分的理由,这是完全错误的.)
Ant*_*sky 24
它被称为展开链表.似乎有一些优势,一个是速度,一个是空间.首先,如果每个节点中的元素数量大小合适(例如,最多只有一个缓存行的大小),则从改进的内存位置可以获得明显更好的缓存性能.其次,因为你有O(n/m)个链接,其中n是展开的链表中的元素数量 m是您可以在任何节点中存储的元素数量,您还可以节省大量的空间,如果每个元素都很小,这一点尤为明显.在构建展开的链表时,显然实现会尝试在节点中留出空间; 当您尝试插入完整节点时,将一半元素移出.因此,最多一个节点将小于半满.根据我能找到的东西(我自己没有做过任何分析),如果你随机插入东西,节点往往实际上大约四分之三满,或者如果操作往往在列表的末尾则更加丰富.
正如其他人(包括维基百科)所说,您可能想查看跳过列表.跳过列表是一种漂亮的概率数据结构,用于存储具有插入,删除和查找的O(log n)预期运行时间的有序数据.它由链表的"塔"实现,每个层的元素越少,它就越高.在底部,有一个普通的链表,包含所有元素.在每个连续的层,有更少的元素,系数为p(通常为1/2或1/4).它的构建方式如下.每次将一个元素添加到列表中时,它都会插入到底行的适当位置(这使用"查找"操作,也可以快速进行).然后,概率为p,它被插入到"上面"链接列表中的适当位置,如果需要则创建该列表; 如果它被放置在更高的列表中,那么它将再次以概率p出现在上面.要查询此数据结构中的内容,请始终检查顶部通道,并查看是否可以找到它.如果您看到的元素太大,则会下降到下一个最低的泳道并再次开始查看.这有点像二元搜索.维基百科很好地解释了它,并且有很好的图表.当然,内存使用情况会更糟,并且您不会获得改进的缓存性能,但通常会更快.