如何优化我的哈希表以减少现实世界的运行时间？

Question

下面是我的一段程序，它使用哈希表将文件（字典）加载到内存中。该词典每行仅包含 1 个单词。但是这个过程花费了太多时间。我该如何优化它？？

 bool load(const char* dictionary)
{
    // TODO
    int k;
    FILE* fp = fopen(dictionary,"r");
    if(fp == NULL)
        return false;

    for(int i=0; i<26; i++)
    {
        hashtable[i] = NULL;
    }

    while(true)
    {
        if(feof(fp))
            return true;

        node* n = malloc(sizeof(node));

        n->pointer = NULL;

        fscanf(fp,"%s",n->word);

        if(isalpha(n->word[0]))
        {
            k = hashfunction(n->word);
        }

        else return true;

        if(hashtable[k] == NULL)
        {
            hashtable[k] = n;
            total_words++;
        }

        else
        {
            node* traverse = hashtable[k];
            while(true)
            {
                if(traverse->pointer == NULL)
                {
                    traverse->pointer = n;
                    total_words++;
                    break;
                }
                traverse = traverse->pointer;
            }
        }

    }
   return false; 
}

Answer 1

摆脱潜在的功能问题，然后担心性能。

A) for(int i=0; i<26; i++)可能是错误的，hashtable[]定义没有贴出来。用这么小的fixedtable.

对于性能来说肯定是不明智的

B) "%s" 和 gets() 一样安全——两者都不好。使用 fgets().

而不是 fscanf(fp,"%s",n->word);

C) 检查 fscanf()/fgets() 中的 return 值而不是 if(feof(fp))。

D) isalpha(n->word[0]) --> isalpha((unsigned char) n->word[0]) 处理负值 char。

E) 检查内存分配失败。

F) 根据未发布的代码，可能还存在其他问题。

然后形成一个简单的测试用例，并使用有效的最少代码，考虑在 codereview.stackexchange.com 上发帖以寻求性能改进。

Answer 2

您假设文件中的所有单词都是不同的。这对字典来说是一个合理的假设，但它是糟糕的防御性编程。你应该总是假设输入是为了得到你，这意味着你不能真的假设它。

不过，在这种情况下，您可能会争辩说哈希表中重复的单词不会阻止它工作；他们只是稍微放慢速度。由于错误输入不会导致错误、未定义的行为或其他灾难，因此记录参考词唯一的要求是勉强可以接受的。

无论如何，如果您实际上没有检查重复项，则无需为每次插入遍历整个哈希桶。如果您在桶的开头而不是末尾插入新条目，则可以避免扫描，如果桶很大，扫描可能会产生明显的加速。

当然，那个优化只能在加载字典的时候使用。一旦初始化完成，它不会帮助您使用哈希表，并且很少值得对启动代码进行超级优化。

如何优化我的哈希表以减少现实世界的运行时间？

How to optimize my hashtable to reduce real world running time?

c

time

hashtable

如何优化我的哈希表以减少现实世界的 运行 时间？

How to optimize my hashtable to reduce real world running time?

c

time

hashtable

如何优化我的哈希表以减少现实世界的运行时间？