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

Question

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

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

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

我在想:我是不是漏掉了什么？我可以更好地利用 N 提前知道的事实吗？或者是否可以根据我的需要调整 HashMap ？

---

编辑 一个额外的前提条件是输入序列排序不当并且键的频率大致相同。

Answer 1

STL 实现在性能方面通常并不完美(请不要圣战)。

如果您知道唯一元素数量 (N) 的有保证且合理的上限，那么您可以轻松实现您自己的大小为 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 倍速度提升吗？

注意:加速在另一个编译器/机器上可能完全不同。如果您的类型 X 不是 POD，您可能需要做一些修改。