对于许多相同的键,最有效的排序算法？

Question

在给定以下内容的情况下,将相同项目组合在一个数组中的最有效算法是什么:

1. 几乎所有项目都重复了几次.
2. 这些项目不一定是整数或其他同样简单的东西.键的范围甚至没有明确定义,更不用说小了.实际上,键可以是任意结构.这排除了最简单的计数排序形式.
3. 我们关心渐近和非渐近属性,并且n有时可能很小.但是,当n很小时,性能仍然很重要,因为在数百万个小数据集的循环中,这个函数可能被称为数百万次.这排除了任何昂贵的散列函数或使用需要执行大量内存分配的复杂数据结构.
4. 只要将所有相同的项目组合在一起,就可以按任意顺序对数据进行排序.

如果这是令人困惑的,这是一个例子,假设这样的函数被命名为groupIdentical:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

但是,作为提醒,我们不能假设数据是作为整数组成的.

编辑:谢谢你的回答.哈希的主要问题是哈希表经常执行内存分配.我最终做的是编写自己的哈希表,使用我周围的区域分配器来解决这个问题.效果很好.

Answer 1

我认为你可以只是散列对象,因为真正的顺序并不重要,只有分组.相同的对象最终将分组在同一个存储桶中.这假设您感兴趣的每个类型都有自己的哈希函数,或者您可以定义自己的哈希函数并重载它(将每个类型作为参数传递给不同的哈希码函数定义).

为了避免数据类型之间的冲突(因此,对于一个示例,字符串不会在同一个存储桶中作为双精度存档),您需要将数据类型编码为散列.因此,例如,如果您有32位散列,则前5位可能会对数据类型进行编码,因此您可以在同一散列映射中使用32种不同类型.

编辑:我只想补充一点,我建议自定义哈希映射的原因是因为我不知道有哪一个暴露了足够的内部实现,以便从每个桶中获取值.可能有这样的实现,我不知道.有很多我不知道的事情.:)