10

经典的 O(1) 随机访问数据结构是数组。但是数组依赖于使用的编程语言来支持有保证的连续内存分配（因为数组依赖于能够获取基的简单偏移量来查找任何元素）。

这意味着语言必须具有关于内存是否连续的语义，而不是将其作为实现细节。因此，可能需要一个具有 O(1) 随机访问但不依赖于连续存储的数据结构。

有这样的事吗？

4

11 回答 11

6

如何将键的长度限制为某个常量 K（例如，4 个字节，以便您可以使用 32 位整数作为索引）。那么查找时间将是 O(K)，即 O(1) 与非连续内存。对我来说似乎很合理。

回想一下我们的复杂度类，不要忘记每个大 O 都有一个常数因子，即 O(n) + C，这种方法肯定会有比实际数组大得多的 C。

编辑：实际上，现在我考虑一下，它是 O(K*A) 其中 A 是“字母”的大小。每个节点必须有一个最多包含 A 个子节点的列表，该列表必须是一个链表，以保持实现不连续。但是 A 仍然是常数，所以它仍然是 O(1)。

于 2009-01-18T20:15:01.523 回答
4

In practice, for small datasets using contiguous storage is not a problem, and for large datasets O(log(n)) is just as good as O(1); the constant factor is rather more important.

In fact, For REALLY large datasets, O(root3(n)) random access is the best you can get in a 3-dimensional physical universe.

Edit: Assuming log10 and the O(log(n)) algorithm being twice as fast as the O(1) one at a million elements, it will take a trillion elements for them to become even, and a quintillion for the O(1) algorithm to become twice as fast - rather more than even the biggest databases on earth have.

All current and foreseeable storage technologies require a certain physical space (let's call it v) to store each element of data. In a 3-dimensional universe, this means for n elements there is a minimum distance of root3(n*v*3/4/pi) between at least some of the elements and the place that does the lookup, because that's the radius of a sphere of volume n*v. And then, the speed of light gives a physical lower boundary of root3(n*v*3/4/pi)/c for the access time to those elements - and that's O(root3(n)), no matter what fancy algorithm you use.

于 2009-01-18T21:01:52.660 回答
3

哈希表？

编辑：一个数组是O(1)查找的，因为a[i]它只是*(a+i). 换句话说，要获得O(1)，您需要一个指向每个元素的直接指针或一个易于计算的指针（以及您将要查找的内存用于您的程序的良好感觉）。在没有指向每个元素的指针的情况下，如果没有连续的内存，就不可能有一个易于计算的指针（并且知道内存是为您保留的）。

当然，有一个 Hashtable 实现是合理的（如果很糟糕），其中每个查找的内存地址只是*(a + hash(i))没有在数组中完成，即如果你有这种控制，则在指定的内存位置动态创建。关键是最有效的实现将是一个底层数组，但是在其他地方进行点击以进行 WTF 实现仍然可以让您进行恒定时间查找当然是合理的。

Edit2：我的观点是，数组依赖于连续内存，因为它是语法糖，但是 Hashtable 选择数组是因为它是最好的实现方法，而不是因为它是必需的。当然，我必须阅读 DailyWTF 太多，因为我想象重载 C++ 的数组索引运算符也可以在没有连续内存的情况下以相同的方式执行此操作..

于 2009-01-18T19:55:14.527 回答
3

除了哈希表，您还可以有一个两级数组数组：

  • 将前 10,000 个元素存储在第一个子数组中
  • 将下一个 10,000 个元素存储在下一个子数组中
  • 等等
于 2009-01-18T20:03:37.413 回答
3

因此，可能需要一个具有 O(1) 随机访问但不依赖于连续存储的数据结构。

有这样的事吗？

不，那里没有。证明草图：

如果您对连续块大小有限制，那么显然您必须使用间接来获取数据项。具有有限块大小的固定间接深度只能得到一个固定大小的图（尽管它的大小随深度呈指数增长），因此随着数据集的增长，间接深度将增长（仅对数，但不是 O(1) ）。

于 2009-01-19T14:20:43.157 回答
2

Aside from the obvious nested structures to finite depth noted by others, I'm not aware of a data structure with the properties you describe. I share others' opinions that with a well-designed logarithmic data structure, you can have non-contiguous memory with fast access times to any data that will fit in main memory.

I am aware of an interesting and closely related data structure:

  • Cedar ropes are immutable strings that provide logarithmic rather than constant-time access, but they do provide a constant-time concatenation operation and efficient insertion of characters. The paper is copyrighted but there is a Wikipedia explanation.

This data structure is efficient enough that you can represent the entire contents of a large file using it, and the implementation is clever enough to keep bits on disk unless you need them.

于 2009-01-18T21:29:22.777 回答
1

当然，您在这里谈论的不是连续的内存存储，而是索引包含数据结构的能力。通常在内部将动态数组或列表实现为指针数组，其中包含内存中其他位置每个元素的实际内容。这样做的原因有很多——尤其是它使每个条目的大小都不同。正如其他人指出的那样，大多数哈希表实现也依赖于索引。我想不出一种方法来实现不依赖于索引的 O(1) 算法，但这至少意味着索引的连续内存。

于 2009-01-18T20:18:44.700 回答
0

一些伪 O(1) 答案-

VList是 O(1) 访问（平均而言），并且不需要整个数据是连续的，尽管它确实需要在小块中连续存储。其他基于数值表示的数据结构也摊销 O(1)。

数字表示应用与基数排序相同的“作弊” ，产生 O(k) 访问结构 - 如果索引有另一个上限，例如它是 64 位 int，那么每个级别的二叉树对应于索引中的某个位需要一个恒定的时间。当然，对于可以与结构一起使用的任何 N，常数 k 都大于 lnN，因此它不太可能是性能改进（如果 k 仅比 lnN 大一点，并且实现基数排序更好地利用了平台）。

如果你使用堆实现中常见的二叉树表示，你最终会回到一个数组。

于 2009-01-21T09:20:49.283 回答
0

A bit of a curiosity: the hash trie saves space by interleaving in memory the key-arrays of trie nodes that happen not to collide. That is, if node 1 has keys A,B,D while node 2 has keys C,X,Y,Z, for example, then you can use the same contiguous storage for both nodes at once. It's generalized to different offsets and an arbitrary number of nodes; Knuth used this in his most-common-words program in Literate Programming.

So this gives O(1) access to the keys of any given node, without reserving contiguous storage to it, albeit using contiguous storage for all nodes collectively.

于 2009-01-18T21:46:39.357 回答
0

分布式哈希映射具有这样的属性。好吧，实际上，不完全是，基本上哈希函数会告诉您要查看的存储桶，在那里您可能需要依赖传统的哈希映射。它并不能完全满足您的要求，因为包含存储区域/节点的列表（在分布式场景中）通常是哈希映射（本质上使其成为哈希表的哈希表），尽管您可以使用其他一些算法，例如，如果存储区域的数量是已知的。

编辑：
忘了一点花絮，你可能想为不同的级别使用不同的哈希函数，否则你最终会在每个存储区域内得到很多相似的哈希值。

于 2009-01-18T19:56:26.583 回答
0

可以不为整个数据分配内存块，而仅为数据片段的引用数组分配内存块。这带来了必要的连续内存长度的急剧减少。

另一种选择，如果元素可以用键标识并且这些键可以唯一地映射到可用的内存位置，则可以不将所有对象连续放置，在它们之间留出空间。这需要控制内存分配，因此当您必须为第一优先对象使用该内存位置时，您仍然可以分配空闲内存并将第二优先对象重新定位到其他地方。但是，它们在子维度中仍然是连续的。

我可以命名一个常见的数据结构来回答您的问题吗？不。

于 2009-01-18T20:23:29.930 回答