logo标签列表

针对大量数字的最有效排序算法

algorithmlistsortingperformancenumbers
9
我正在处理一个大型项目，这里不再赘述。这个项目中的一部分是从一份非常庞大的文本文档（至少约有50,000个单词（不重复））中提取每个唯一单词，并按使用频率从高到低进行排序（前三个可能是“a”、“an”和“the”）。
我的问题当然是，哪种排序算法最好？我看过计数排序，我很喜欢它，但我担心值的范围相对于唯一单词的数量来说太大了。
您有什么建议吗？
1
你正在使用什么编程语言？有些语言内置了某些处理程序（例如LINQ）。 - Eric
无论如何，这些信息现在足够了，我今天工作了太多小时，我得等到明晚才能处理它。 - aterimperator
9个回答
14

首先，您需要一个单词 -> 数量的映射表。 50000个词不多，可以轻松地放在内存中，所以没有什么可担心的。在C++中，您可以使用标准STL std :: map。

然后，一旦您有了映射表，就可以将所有映射表键复制到向量中。

接下来，使用自定义比较运算符对此向量进行排序：而不是比较单词，请比较映射表中的数量。（不要担心具体的排序算法-您的数组不是很大，因此任何标准库排序都适用于您。）

3
所有程序员都需要至少基本了解排序算法。+1 链接。 - Matthew Vines
2
1

请查看链接。以图像方式呈现了不同算法的工作原理，这将给你一些提示！

排序算法

1
我更喜欢这个：http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html - Tom Leys
这两者都表明shell是最好的选择。 - aterimperator
1
截至2013年03月18日，回答中的链接和Tom Leys的评论中的链接均已失效。 - Olfan
1

假设两个单词出现的次数相同，那么你可以比快速排序获得更好的性能，只要无论以哪种顺序输出它们都没有关系。

第一步：创建一个哈希映射，将单词作为键值，频率作为相关值。在解析文件时，您将填充此哈希映射。在执行此操作时，请确保跟踪遇到的最高频率。此步骤的复杂度为O(n)。

第二步：创建一个列表，其条目数等于第一步中的最高频率。此列表中每个插槽的索引将保存具有与索引相等的频率计数的单词列表。例如，文档中出现3次的单词将进入list[3]。遍历哈希映射并将单词插入列表中的适当位置。此步骤的复杂度为O(n)。

第三步：反向遍历列表并输出所有单词。此步骤的复杂度为O(n)。

总体而言，此算法将在O(n)时间内完成您的任务，而不是快速排序所需的O(nlogn)。

3
第一步的时间复杂度为O(n*m)，其中n是输入中单词的数量，m是唯一单词的数量。第二步使用O(m)内存，并以随机访问模式执行 - 对缓存来说很糟糕。如果第三步用于传递到另一个代码段中，则需要分配o（n）内存。所有这些意味着您的代码将具有较差的内存性能，这将主导任何明显的代码改进。 - Tom Leys
如果你使用了一个非常高效的哈希函数，那么第一步可能只需要O(m)的时间复杂度，如果你非常幸运并且没有哈希冲突的话。 - Tom Leys
1
在我测试过的几乎所有情况下，快速排序对我来说效果最好。然而，我有两个案例是梳排序表现最佳。可能是因为代码很简短，或者由于数据排序方式的某些怪异之处。
每当我的个人资料中出现排序时，我都会尝试主要的排序算法。我从未遇到过比快速排序和梳排序都更好的算法。
这可能是一个晚回复。但我完全同意你的观点。梳排序确实非常快。令人惊讶的是，梳排序是冒泡排序的一种轻微变体，而冒泡排序则非常慢。我找不到任何关于梳排序复杂度分析的参考资料。维基百科说平均复杂度为n^2/2^p。但没有详细说明如何实现。 - arunmoezhi
0

你也可以尝试实现数字树，也称为Trie。这里是link。

0
0

对于大型数据集，您可以使用信息检索中所谓的“基于排序的索引”，但对于50,000个单词，您可以采用以下方法：

  • 将整个文件读入缓冲区。
  • 解析缓冲区并构建一个令牌向量，其中 struct token { char *term, int termlen; } 。 term 是指向缓冲区中单词的指针。
  • 按术语（字典序）对表进行排序。
  • 设置 entrynum = 0，遍历术语向量，当术语是新的时，在向量中存储它： struct { char *term; int frequency; } 在索引 entrynum 设置频率为1并增加条目数，否则增加频率。
  • 按频率降序排序向量。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接