algorithm - 最佳排序算法

Question

从超过 1000 万个单词的列表中挑选出唯一单词的最佳算法是什么？在执行时间方面，我们需要最好的技术。

Answer 1

我记得有两种简单的方法：

1. 将所有项目添加到折叠重复项的数据结构中（通常是哈希，但您也可以尝试平衡树或特里树）。
2. 对列表进行排序，然后遍历它，复制出所有不等于前一个元素的元素。

粗略地说，根据通常的软糖，哈希表和特里树给你预期O(n)，平衡树和排序给你预期O(n log n)。解决方案不一定比针对您的特定数据O(n)的解决方案更快。O(n log n)

(1) 中的所有选项都可能具有为数据结构中的节点分配大量小内存的缺点，除非您使用专用分配器，否则这可能会很慢。因此，根据我的经验，在开始任何需要您编写重要代码的事情之前，对您真正关心的数据大小进行测试是值得的。

根据您使用的语言，其中一些方法可能比其他方法更容易测试。例如，在 Python 中，如果您有一个字符串列表，那么哈希表方法就是set(my_strings). 在 C 中，没有标准的哈希表，因此您要么编写一个哈希表，要么正在寻找一个库。

当然，易于编写对执行时间没有直接影响，因此，如果（如您所言）您的程序员时间无关紧要，重要的是执行速度，那么花几周时间熟悉最好的可用文献应该没有问题关于排序和哈希表。你会比我更能回答这个问题。

Answer 2

只需将它们添加到哈希中。恒定时间插入。我不相信你能比订购 n 做得更好。红黑树在小型数据集上可能更快（遍历树比计算散列更快），但您的数据集很大。

Answer 3

剧透：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct somehash {
        struct somehash *next;
        unsigned hash;
        char *mem;
        };

#define THE_SIZE (10*1000*1000)
struct somehash *table[THE_SIZE] = { NULL,};

struct somehash **some_find(char *str, unsigned len);
static unsigned some_hash(char *str, unsigned len);

int main (void)
{
char buffer[100];
struct somehash **pp;
size_t len;

while (fgets(buffer, sizeof buffer, stdin)) {
        len = strlen(buffer);
        pp = some_find(buffer, len);
        if (*pp) { /* found */
                fprintf(stderr, "Duplicate:%s", buffer);
                }
        else    {       /* not found: create one */
                fprintf(stdout, "%s", buffer);
                *pp = malloc(sizeof **pp);
                (*pp)->next = NULL;
                (*pp)->hash = some_hash(buffer,len);
                (*pp)->mem = malloc(1+len);
                memcpy((*pp)->mem , buffer,  1+len);
                }
        }
return 0;
}struct somehash **some_find(char *str, unsigned len)
{
unsigned hash;
unsigned short slot;
struct somehash **hnd;

hash = some_hash(str,len);
slot = hash % THE_SIZE;
for (hnd = &table[slot]; *hnd ; hnd = &(*hnd)->next ) {
        if ( (*hnd)->hash != hash) continue;
        if ( strcmp((*hnd)->mem , str) ) continue;
        break;
        }
return hnd;
}

static unsigned some_hash(char *str, unsigned len)
{
unsigned val;
unsigned idx;

if (!len) len = strlen(str);

val = 0;
for(idx=0; idx < len; idx++ )   {
        val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801;
        }
return val;
}