如果您有 65536 个随机英语单词，每个单词的长度为 1-32，您需要计算外观并根据字典或外观排名进行排序，您如何构建数据以及使用哪种排序技术来最快地处理它？
mzk
问问题
615 次
10 回答
17
说真的，65,000 个单词是一个微不足道的排序问题。除非您必须每分钟重新排序多次，否则我建议您只使用qsort()语言内置的。毕竟，这就是它的目的。
我建议对 alpha 顺序使用一个简单的 char 指针数组。为了维护频率顺序，您可以使用以下结构：
typedef struct {
char *word; // points to one of the strings.
int frequency; // counts the number of occurrences.
} tFreq;
在另一个数组中，您可以在创建或修改按 alpha 排序的指针数组时完全填充该数组（请参阅下文，了解为什么这个看似低效的过程是合适的）。
作为速度示例，请考虑以下代码：
#include <stdio.h>
#define MAXWDS 66000
static char *words[MAXWDS];
static int compFn (const void *p1, const void *p2) {
return strcmp (*((const char **)p1), *((const char **)p2));
}
int main() {
char *pWord;
int i, j, sz;
time_t t0, t1;
srand (time (0));
for (i = 0; i < MAXWDS; i++) {
sz = rand() % 32 + 1;
pWord = words[i] = malloc (sz + 1);
for (j = 0; j < sz; j++)
pWord[j] = 'A' + (rand() % 26);
pWord[sz] = '\0';
}
t0 = time(0);
qsort (words, MAXWDS, sizeof (char*), compFn);
t1 = time(0);
printf ("Time taken for %7d elements was %2d second(s)\n", MAXWDS, t1 - t0);
return 0;
}
在 3GHz 双核 Intel 芯片上，以下是 MAXWDS 的几个选定值的输出：
MAXWDS Output
--------- ------
66,000 Time taken for 66000 elements was 0 second(s)
100,000 Time taken for 100000 elements was 0 second(s)
500,000 Time taken for 500000 elements was 0 second(s)
600,000 Time taken for 600000 elements was 1 second(s)
1,000,000 Time taken for 1000000 elements was 1 second(s)
2,000,000 Time taken for 2000000 elements was 2 second(s)
3,000,000 Time taken for 3000000 elements was 5 second(s)
4,000,000 Time taken for 4000000 elements was 7 second(s)
5,000,000 Time taken for 5000000 elements was 9 second(s)
6,000,000 Time taken for 6000000 elements was 10 second(s)
7,000,000 Time taken for 7000000 elements was 11 second(s)
9,999,999 Time taken for 9999999 elements was 21 second(s)
因此，如您所见，qsort 对于您正在谈论的数据集大小相当有效。
事实上，实现维护两个排序列表的整个过程，如下面的代码所示，向您展示了 66,000 个元素是多么微不足道。基本前提是：
- 根据需要修改 alpha 排序的字符串，然后对它们进行完整的 alpha 排序 (
t0 to t1)。 - 利用它们已排序的事实可以轻松地将它们转移到另一个数组，但每个单词只有一个元素，以及频率 (
t1 to t2)。 - 对该频率数组进行排序（
t2 to t3）。
以下代码显示了这是如何完成的。唯一有点棘手的地方是从 alpha 阵列到频率阵列的传输。
#include <stdio.h>
#define MAXWDS 66000
typedef struct {
char *word;
int frequency;
} tFreq;
static char *words[MAXWDS];
static tFreq freq[MAXWDS];
static int numFreq;
static int compFn (const void *p1, const void *p2) {
return strcmp (*((const char **)p1), *((const char **)p2));
}
static int compFn2 (const void *p1, const void *p2) {
return ((tFreq*)p2)->frequency - ((tFreq*)p1)->frequency;
}
int main() {
char *pWord;
int i, j, sz;
time_t t0, t1, t2, t3;
// Generate random words.
srand (time (0));
for (i = 0; i < MAXWDS; i++) {
sz = rand() % 32 + 1;
pWord = words[i] = malloc (sz + 1);
for (j = 0; j < sz; j++)
pWord[j] = 'A' + (rand() % 26);
pWord[sz] = '\0';
}
t0 = time(0);
// Alpha sort.
qsort (words, MAXWDS, sizeof (char*), compFn);
t1 = time(0);
// Pre-condition to simplify loop: make first word with zero frequency.
freq[0].word = words[0];
freq[0].frequency = 0;
// Transfer to frequency array.
for (i = numFreq = 0; i < MAXWDS; i++) {
// If new word, add it and set frequency to 0.
if (strcmp (freq[numFreq].word, words[i]) != 0) {
numFreq++;
freq[numFreq].word = words[i];
freq[numFreq].frequency = 0;
}
// Increment frequency (for old and new words).
freq[numFreq].frequency++;
}
numFreq++;
t2 = time(0);
// Sort frequency array.
qsort (freq, numFreq, sizeof (tFreq), compFn2);
t3 = time(0);
// Output stats.
printf ("Time taken for sorting %5d elements was %d seconds.\n",
MAXWDS, t1 - t0);
printf ("Time taken for transferring %5d elements was %d seconds.\n",
numFreq, t2 - t1);
printf ("Time taken for sorting %5d elements was %d seconds.\n",
numFreq, t3 - t2);
printf ("Time taken for everything %5s was %d seconds.\n\n",
"", t3 - t0);
for (i = 0; i < 28; i++) {
printf ("[%-15s] %5d\n", freq[i].word, freq[i].frequency);
}
return 0;
}
66,000 个随机字符串的输出是（前几个字符串在那里，因此您可以看到排序有效）：
Time taken for sorting 66000 elements was 0 seconds.
Time taken for transferring 62422 elements was 0 seconds.
Time taken for sorting 62422 elements was 0 seconds.
Time taken for everything was 0 seconds.
[Z ] 105
[H ] 97
[X ] 95
[P ] 90
[D ] 89
[K ] 87
[T ] 86
[J ] 85
[G ] 84
[F ] 83
[Q ] 83
[W ] 81
[V ] 81
[M ] 80
[I ] 79
[O ] 78
[A ] 78
[B ] 75
[U ] 74
[N ] 73
[C ] 73
[S ] 70
[Y ] 68
[L ] 65
[E ] 60
[R ] 59
[NQ ] 8
[XD ] 8
因此，即使您每次插入或删除值时都执行这些操作，它们也不会产生明显的影响（除非很明显，如果您每隔几秒钟执行一次以上，但您会考虑将改变效率）。
于 2009-06-16T07:49:19.273 回答
4
查看http://www.sorting-algorithms.com/以获得不同排序方法的良好视觉表示。
于 2009-06-16T08:30:09.580 回答
2
哦，天哪，这是一个措辞糟糕的家庭作业问题——导师应该比这更清楚。最后一部分是“以最快的速度处理它”。不幸的是，要确定一个算法需要多长时间执行是非常非常困难的。大 O 表示法没有帮助，因为它衡量的是复杂性，而不是速度（有关这方面的更多信息，请参阅 Raymond Chen 最近的博客条目）。唯一实用的方法是实现算法，运行它并测量所花费的时间。此外，输入数据会影响执行时间 - qsort 和二叉树对于已经排序的数据不是最优的。
你可以写一篇关于“最快”的整篇论文，但仍然没有得到具体的答案。
于 2009-06-16T09:39:52.360 回答
1
于 2009-06-16T07:49:57.213 回答
1
我会使用我的运行时库碰巧提供的任何排序算法。通常，sort() 使用快速排序。
不要担心排序算法的选择，直到你知道你的标准算法因为你已经测量过它运行得不够好。
于 2009-06-16T08:10:20.813 回答
0
合并排序应该可以很好地解决这个问题，并且很容易在 c 中工作。
于 2009-06-16T08:02:48.703 回答
0
您可以使用
struct elem { char *word, int frequency; } // pointer to 'string' word
struct elem dict[1<<16]; // number of words
使用标准 qsort 按单词或频率排序，或者如果您同时需要两个订单，请使用第二个数组。
于 2009-06-16T08:20:10.203 回答
0
选择排序算法取决于您拥有的数据量（65k 并不多）以及您选择的时间和内存之间的权衡。如果要快速检索数据，则必须使用更多内存。另一方面，如果您决定节省内存，您将无法快速找到记录。
算法的选择非常简单——使用你的语言库提供的任何东西，除非你有证据证明这还不够好。
您需要按两个标准对数据进行排序，因此您实际上需要两个排序数组。它们都应该是某种指针数组。
于 2009-06-16T08:30:33.603 回答
0
使用特里。这样，两个“排序”都将是图的简单遍历。
于 2009-06-16T08:50:31.790 回答