数据结构名称：组合数组/链表 [英] Data structure name: combination array/linked list

问题描述

我已经提出了一个数据结构，它结合了链表的一些优点和固定大小数组的一些优点。对我来说似乎很明显，所以我希望有人想到它，并已经命名了。有人知道这叫什么：

拿一个小的固定大小的数组。如果要放入数组的元素数大于数组的大小，请在新旧数组之间添加一个新的数组以及任何你喜欢的指针。

因此你有：

 静态数组
 -------------- ----------- 
 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | 
 ------------------------- 
 
链接列表
 ---- --- -  ---- ---- ---- 
 | 1 | *  - > | 2 | *  - > | 3 | *  - > | 4 | *  - > | 5 | *  - > NULL 
 ---- ---- ---- ---- ---- 
 
我的东西：
 -------- ---- ------------ 
 | 1 | 2 | 3 | 4 | 5 | *  - > | 6 | 7 | 8 | 9 | a | *  - NULL 
 ------------ ------------ 
  

编辑：为了参考，该算法提供了非常差的最坏情况添加/删除性能，并没有更好的平均情况。我的场景的最大优点是读取操作的缓存性能得到改善。

编辑优惠：Antal S-Z的答案非常完整，经过深入研究，我想为其提供一个赏金。显然，Stack Overflow并没有让我接受一个答案，只要我提供了一个赏金，所以我必须等待（诚然，我有意滥用意图赏金系统，虽然这是一个奖励的人的一个优秀的名义回答）。当然，如果某人设法提供更好的答案，更多的权力给他们，他们肯定会得到赏金！

编辑重名称：我不会对您所呼吁的 感兴趣，除非你这样称呼，因为这是该主题的权威。如果这是你想出的名字，我不感兴趣。我想要的是我可以在教科书和谷歌中查找的名称。 （另外，这里有一个提示：Antal的答案是我正在寻找的，如果你的答案不是unrolled linked list，而没有一个非常很好的理由，那只是一个简单的错误。）

解决方案

它被称为 展开的链接列表 。似乎有几个优点，一个在速度和一个在空间。首先，如果每个节点中的元素数量适当地大小（例如，，至多一个高速缓存行的大小），则从改进的存储器位置获得明显更好的缓存性能。其次，由于您有O（ n / m ）链接，其中 n 是展开的链接列表中的元素数量， m 是可以存储在任何节点中的元素数量，还可以节省可观量的空间，如果每个元素都很小，这是特别明显的。构建展开的链表时，显然实现将尝试通常在节点中留下空间;当您尝试插入一个完整节点时，您将一半的元素移出。因此，最多一个节点将不到一半。根据我可以找到的内容（我自己也没有做任何分析），如果随机插入东西，节点往往要大约四分之三完整，如果操作往往在列表的末尾，那么节点往往会更加完整。

正如其他人（包括维基百科）所说，您可能想查看跳过列表。跳过列表是一个漂亮的概率数据结构，用于存储带有O（log n ）的有序数据，用于插入，删除和查找预期的运行时间。它由链表的塔实现，每层具有较少的元素。在底部，有一个普通的链表，具有所有元素。在每个连续的层中，有较少的元素，通过一个因子

（通常为1/2或1/4）。它的构建方式如下。每次将元素添加到列表中时，它将被插入到底行中的适当位置（这使用查找操作，也可以快速进行）。然后，以概率 p ，将其插入到上方​​链接的列表中的适当位置，如果需要则创建该列表;如果它被放置在较高的列表中，那么它将再次再次出现在上面，概率为 p 。要查询此数据结构中的某些内容，请始终查看顶部的行车道，并查看是否可以找到。如果你看到的元素太大，你会下降到下一个最低的车道，然后重新开始。这有点像二进制搜索。维基百科解释很好，并有很好的图表。当然，内存使用情况会变得更糟，而且您不会有改进的缓存性能，但通常会更快。

参考

• 展开的链接列表， http://en.wikipedia.org/wiki/Unrolled_linked_list


• 展开的链接列表， http://blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx


• 跳过列表， http：// en。 wikipedia.org/wiki/Skip_list


• 我的算法类中的跳过列表演讲。

I have come up with a data structure that combines some of the advantages of linked lists with some of the advantages of fixed-size arrays. It seems very obvious to me, and so I'd expect someone to have thought of it and named it already. Does anyone know what this is called:

Take a small fixed-size array. If the number of elements you want to put in your array is greater than the size of the array, add a new array and whatever pointers you like between the old and the new.

Thus you have:

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
————————————  ————————————

Edit: For reference, this algorithm provides pretty poor worst-case addition/deletion performance, and not much better average-case. The big advantage for my scenario is the improved cache performance for read operations.

Edit re bounty: Antal S-Z's answer was so complete and well-researched that I wanted to provide em with a bounty for it. Apparently Stack Overflow doesn't let me accept an answer as soon as I've offered a bounty, so I'll have to wait (admittedly I am abusing the intention bounty system somewhat, although it's in the name of rewarding someone for an excellent answer). Of course, if someone does manage to provide a better answer, more power to them, and they can most certainly have the bounty instead!

Edit re names: I'm not interested in what you'd call it, unless you'd call it that because that's what authorities on the subject would call it. If it's a name you just came up with, I'm not interested. What I want is a name that I can look up in text books and with Google. (Also, here's a tip: Antal's answer is what I was looking for. If your answer isn't "unrolled linked list" without a very good reason, it's just plain wrong.)

解决方案

It's called an unrolled linked list. There appear to be a couple of advantages, one in speed and one in space. First, if the number of elements in each node is appropriately sized (e.g., at most the size of one cache line), you get noticeably better cache performance from the improved memory locality. Second, since you have O(n/m) links, where n is the number of elements in the unrolled linked list and m is the number of elements you can store in any node, you can also save an appreciable amount of space, which is particularly noticeable if each element is small. When constructing unrolled linked lists, apparently implementations will try to generally leave space in the nodes; when you try to insert in a full node, you move half the elements out. Thus, at most one node will be less than half full. And according to what I can find (I haven't done any analysis myself), if you insert things randomly, nodes tend to actually be about three-quarters full, or even fuller if operations tend to be at the end of the list.

And as everyone else (including Wikipedia) is saying, you might want to check out skip lists. Skip lists are a nifty probabilistic data structure used to store ordered data with O(log n) expected running time for insert, delete, and find. It's implemented by a "tower" of linked lists, each layer having fewer elements the higher up it is. On the bottom, there's an ordinary linked list, having all the elements. At each successive layer, there are fewer elements, by a factor of p (usually 1/2 or 1/4). The way it's built is as follows. Each time an element is added to the list, it's inserted into the appropriate place in the bottom row (this uses the "find" operation, which can also be made fast). Then, with probability p, it's inserted into the appropriate place in the linked list "above" it, creating that list if it needs to; if it was placed in a higher list, then it will again appear above with probability p. To query something in this data structure, you always check the top lane, and see if you can find it. If the element you see is too large, you drop to the next lowest lane and start looking again. It's sort of like a binary search. Wikipedia explains it very well, and with nice diagrams. The memory usage is going to be worse, of course, and you're not going to have the improved cache performance, but it is generally going to be faster.

References

• "Unrolled Linked List", http://en.wikipedia.org/wiki/Unrolled_linked_list
• "Unrolled Linked Lists", http://blogs.msdn.com/b/devdev/archive/2005/08/22/454887.aspx
• "Skip List", http://en.wikipedia.org/wiki/Skip_list
• The skip list lecture(s) from my algorithms class.

这篇关于数据结构名称：组合数组/链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！