logo标签列表

以下约束条件下最佳的数据结构是什么？

performancelanguage-agnosticoptimizationdata-structures
6
以下是所需数据结构的一些限制。看起来常见的数据结构（我将在下面提到我考虑过的那些）都不太适合这些限制。有人能建议一个我可能没有想到的吗？
  1. 我需要能够通过无符号整数键进行查找。
  2. 要存储的项目是用户定义的结构体。
  3. 这些索引通常是稀疏的，通常极其稀疏。普通数组不行。
  4. 每个索引的频率分布是非均匀的，小索引比大索引更常见。
  5. N通常很小，可能不超过5或10，但我不想过于依赖它，因为它偶尔可能会更大。
  6. 常数项非常重要。当N很小时，我需要非常快的查找速度。我已经尝试了通用哈希表，并且实证上，即使N=1，意味着没有冲突，它们也太慢了，可能是由于涉及的间接寻址量。但是，我对利用其他约束条件的专门哈希表的建议持开放态度。
  7. 插入时间并不重要，只要检索时间快就可以了。即使插入时间为O(N)，也足够好。
  8. 空间效率并不是非常重要，尽管它足够重要以不仅仅使用常规数组。
像非常具体的约束条件一样，会产生有趣且可能非常有用的答案。 你所使用的语言是否假定边界检查可能会有所不同。如果你在某些版本的.Net上，带有非原始结构的方法将无法内联，并影响一些事情。 - ShuggyCoUk
10个回答
4
当N很小时，一个简单的数组或者带有键值对负载的单向链表非常高效。即使在N变大时不是最佳选择。
你可以获得O(N)的查找时间，这意味着查找需要k * N时间。O(1)的查找只需要恒定的K时间。因此，在N < K/k时，使用O(N)可以获得更好的性能。这里的k非常小，所以你可以获得有趣的N值。请记住，Big O符号仅描述大的N值的行为，而不是你想要的。对于小表格来说，这非常重要。
void *lookup(int key_to_lookup)
{
  int n = 0;
  while (table_key[n] != key_to_lookup)
    n++;
  return table_data[n];
}

很难击败。

对您的哈希表、平衡树和简单数组/链表进行基准测试，并查看它们在哪些N值上开始更好。然后，您就会知道哪种方法更适合您。

我差点忘了：将经常访问的键保留在数组的开头。根据您的描述，这意味着保持排序。

3

这些建议假设使用现代CPU，具有：

  • 快速高效的缓存
  • 与时钟速度相比更慢的内存延迟
  • 合理的分支预测（最新台式机/服务器处理器真是太神奇了）

我建议采用混合结构可能比单一结构更好。

使用简单的基于数组的键值对，访问时间为O(N)，但常数因子非常低，缓存行为非常好。这个初始结构应该很小（可能不超过16个，可能是8个值），以避免超过一个缓存行。遗憾的是，这是一个需要自己调整的参数。

一旦超过这个数字，你会想要回到一个具有更好O(N)性能的结构，我建议首先尝试一个不错的哈希表，因为这将在16-几千范围内可能是合理的，并且如果你倾向于更频繁地查找相似的值，它们往往会保持在更快的缓存中。

如果你同时进行删除和插入操作，必须注意不要在两种状态之间来回折腾。要求计数收缩到半数的截止点以防止这种情况发生，但请记住，任何确定性的交叉行为都会受到最坏情况下的输入影响。如果你试图防御恶意输入数据，则可能会出现问题。如果是这样，使用决策中的随机因素可以保护它。不过你可能不关心这个，因为你没有提到它。

如果你愿意，可以尝试使初始主数组排序，以允许二进制搜索，这是O(log(N))的，但搜索代码更复杂。我认为简单的数组遍历实际上会打败它，但你需要为不同的N值进行基准测试，它可能允许你更长时间地使用主数组，但我认为这是缓存行大小而不是O(N)行为的函数。

其他选项包括：

  • 将所有键值<256的值视为特殊处理，并将它们存储在一个字节->结构对的数组中，从而节省键的空间（并在切换到辅助结构时可能允许它们留在那里），但由于需要即时解压缩数组到本机字长，因此可能表现不佳。
  • 使用类似trie的结构，每次对键执行一个字节。我怀疑这种复杂性在实践中表现不佳。

再次重申kmkaplan的非常好的建议。彻底进行基准测试，避免微基准测试。在这种分析中，真实数字可能会与理论有惊人的不同...

2

哈希表查找速度已经非常快了：

唯一与普通数组查找不同的是计算哈希值，如果你的哈希函数足够好或者在插入期间花费足够的时间生成最优哈希函数（这将使插入时间为O(N)），那么基本上就是一个数组查找。

基本上，因为可能会发生（除非使用最优哈希函数）必须重新哈希或遵循非常小的链接列表的情况。

由于用于哈希表的大多数哈希函数都是k*c_1 % c_2，所以在相当稀疏和/或最优哈希表中与数组查找的区别包括一个间接寻址、两个乘法、一个减法和一个除法（使用CPU能力的有效模数实现可能通过一个减法和一个乘法来减少）以及数组查找。

它根本不可能再快了。

抱歉，但他特别提到了常数因子和哈希表实际上可能非常慢，因为它们需要检查哈希和相等性，如果哈希质量差会严重退化，不允许使用特定于域的知识，如此处所示，并且可能具有较差的缓存行为。 - ShuggyCoUk
如果哈希函数不好，会导致性能下降严重，不能使用特定领域的知识。如果在你明确知道要大量使用无符号整数的小子集的情况下哈希函数表现不佳，那么你可能选择了错误的哈希函数？ - danielschemmel
设计适用于特定数据分布的良好哈希函数是困难的（我们去购物吧）。由于分布域非常紧密，正常的雪崩卡方测试并不是一个很好的指标。 - ShuggyCoUk
哦，而且具有合理负载因子的哈希表总是会浪费一些空间。在小集合中，这可能意味着填充一个高速缓存行或两个高速缓存行之间的差异。这可能会压倒性地影响性能指标... - ShuggyCoUk
1
你可以尝试将两者的优点结合起来：如果键值很小，就将它放入类似于数组的数据结构中，该数据结构不会变得比预定义的最大键值更大。如果键值很大，则将其放入散列表中。
1
我能看到的唯一解释是哈希函数过于复杂。我倾向于采用两阶段方法：
1）对于小键，使用简单的指针数组。没有哈希或其他任何东西。
2）对于大于您分配的表大小的键：
如何使用非常简单的哈希函数来扩展聚集的键：
左侧顺序5位（假设为32位整数。如果是64位，则再添加一位）是实际包含数据的位数，其余部分仅是原始密钥的总和（丢弃进位），被切成您用于此目的的多少位的块并相加。
请注意，有效位数可以部分预先计算-构建一个64k高位值表。如果高位字不为零，则将其用作表的索引并添加16，否则使用低位字作为索引。对于64位整数，您显然必须使用4个步骤而不是两个。
1
您可以考虑使用Judy Arrays：

Judy是一个C库，提供了一种先进的核心技术，实现了一种稀疏动态数组。使用null指针简单地声明Judy数组。只有在填充Judy数组时才会消耗内存，但如果需要，它可以增长以利用所有可用内存...Judy可以取代许多常见的数据结构，如数组、稀疏数组、哈希表、B树、二叉树、线性列表、跳表、其他排序和搜索算法以及计数函数。

请注意，这些功能在完全利用时相当依赖于某些语言特性，尤其是指针（空的Judy数组是一个空指针）。 - ShuggyCoUk
我还没有找到任何关于x86 CPU的最近严肃性能分析，原始调优是在具有不同缓存实现的HP CPU上完成的。较旧的分析：http://www.nothings.org/computer/judy/ - ShuggyCoUk
顺便说一句，我同意Judy数组可能不像广告中所宣称的那样有效，但它们确实（号称）满足许多要求，所以如果其他方法都不起作用的话，或许值得一试。 - Jacob Gabrielson
0
我会考虑使用处理哈希冲突的自平衡二叉树实现哈希表，而不是简单的链式结构。这样做可以获得 O(1) 的均摊查找时间和最坏情况下 O(logN) 的查找时间。由于您的键分布不均匀，很可能在索引较低的位置会发生冲突，此时使用树形结构的查找将非常有益。
为什么这是可能的呢？至少使用TRS1哈希映射，您可以指定自己的哈希函数。 - danielschemmel
由于它们是整数键，我假设使用一个简单的哈希函数（如取模）。使用更复杂的哈希函数可能会解决问题。 - tvanfosson
我的假设也基于他声称具有的哈希表经验。 - tvanfosson
如果他使用的是低值占主导地位的分布，那么像 k % (mapsize*2) 这样非常简单的函数实际上应该表现得非常好？这将基本上将哈希映射更改为数组索引，其中高键值被弹回到标准范围。 - danielschemmel
0
如果您的N通常很小，可以尝试使用二次探测的开放地址哈希表，而不是分离链接。如果您遇到罕见的N超载情况，需要从初始大小32重新分配到更大的宽度。如果整个结构适合几个高速缓存行，则线性探测或布谷鸟哈希将为您提供良好的性能。
老实说，即使是标准哈希表也给您带来了如此糟糕的性能，我感到惊讶。也许您可以对其进行分析，看看是什么使其变得如此缓慢--如果是哈希函数本身，请使用简单的哈希函数，例如2的幂模数（例如，key &（N-1），其中N已知为2 ^ x），这将有利于以0为中心的分布。如果是追踪分离链的dcache miss，编写一个实现，在桶中将前四个元素存储在桶本身中，以便您至少可以快速获取它们。 N = 1有多慢？
我会在桶链中存储结构体的指针，而不是结构体本身：如果结构体很大，则遍历它们的链将有许多高速缓存未命中。另一方面，您可以在单个高速缓存行上放置约16个键/指针对，并且仅在找到正确元素时支付未命中的代价。
0

这里有一个哈希函数的一般想法。你说插入可能很昂贵。

使用简单的模数将键（整数）进行哈希，每个哈希表实例都存储一个模数

如果插入会导致冲突，请重新优化哈希表，通过计算在合理范围内每个模数中会发生多少次冲突，例如，您的映射元素数量通过某个常数倍增加。

显然，如果最小化分配，则插入实际上变得非常昂贵，约为O（n ^ 2），但您可能能够通过单个整数除法和单个指针间接引用来实现查找，并且因为您在插入时计算了最坏情况的查找，所以您知道它是什么。

0

我建议在这里使用跳表。如果你喜欢的话，java.util.concurrent包有一个很好的实现。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接