用少量重复键对巨大的数组进行排序

Question

我想对一个巨大的数组进行排序，比如 10^8 个 X 类型的条目，最多 N 个不同的键，其中 N 是 ~10^2。因为我不知道元素的范围或间距，所以计数排序不是一个选项。所以到目前为止我最好的猜测是使用哈希映射来计算这样的计数

std::unordered_map< X, unsigned > counts;
for (auto x : input)
    counts[x]++;

这工作正常，比 3 向快速排序快 4 倍，但我是一个紧张的人，它仍然不够快。

我在想：我是不是漏掉了什么？我可以更好地利用预先知道 N 的事实吗？或者是否可以根据我的需要调整哈希映射？

EDIT另外一个前提条件是输入序列排序不好，key出现频率差不多

Answer 1

我希望将项目存储在排序的向量中，因为大约 100 个键意味着插入到向量中只会在 10^6 个条目中出现 1 个。查找将是处理器高效的 bsearch in vector

Answer 2

STL 实现在性能方面通常并不完美（请不要大打出手）。

如果您知道唯一元素数量 (N) 的有保证且合理的上限，那么您可以轻松实现自己的散列 table，大小为 2^s >> N。以下是我通常自己做的：

int size = 1;
while (size < 3 * N) size <<= 1;
//Note: at least 3X size factor, size = power of two
//count = -1 means empty entry
std::vector<std::pair<X, int>> table(size, make_pair(X(), -1));
auto GetHash = [size](X val) -> int { return std::hash<X>()(val) & (size-1); };

for (auto x : input) {
  int cell = GetHash(x);
  bool ok = false;
  for (; table[cell].second >= 0; cell = (cell + 1) & (size-1)) {
    if (table[cell].first == x) { //match found -> stop
      ok = true;
      break;
    }
  }
  if (!ok) {             //match not found -> add entry on free place
    table[cell].first = x;
    table[cell].second = 0;
  }
  table[cell].second++;  //increment counter
}

在 MSVC2013 上，与您的代码相比，它将时间从 0.62 秒缩短到 0.52 秒，因为 int 用作类型 X .

另外，我们可以选择更快的散列函数。但是请注意，哈希函数的选择在很大程度上取决于输入的属性。我们取 Knuth's multiplicative hash:

auto GetHash = [size](X val) -> int { return (val*2654435761) & (size-1); };

它进一步将时间缩短到 0.34 秒。

作为结论：您真的想重新实现标准数据结构以实现 2 倍速度提升吗？

注意：另一个 compiler/machine 上的加速可能完全不同。如果您的类型 X 不是 POD，您可能需要做一些修改。

Answer 3

计数排序确实最好，但由于未知范围或间距而不适用。

似乎很容易与 fork-join 并行化，例如boost::thread.

您也可以尝试更高效的手动哈希图。 Unorded_map 通常使用链表来对抗潜在的坏散列函数。如果哈希表不适合 L1 缓存，链表的内存开销可能会影响性能。 Closed Hashing 可能会占用更少的内存。一些优化提示：

具有线性探测且不支持删除的封闭哈希
用于移位而不是模运算的两个大小哈希表的幂（除法需要多个周期并且每个内核只有一个硬件除法器）
低 LoadFactor（通过大小的条目）以最大程度地减少冲突。这是内存使用和冲突次数之间的权衡。应避免超过 0.5 的 LoadFactor。哈希表大小为 256 似乎适合 100 个条目。
便宜的哈希函数。您还没有显示 X 的类型，因此也许更便宜的散列函数可以胜过更多的冲突。

用少量重复键对巨大的数组进行排序

sort huge array with small number of repeating keys

sorting

algorithm

performance

stdvector

c++11