如何更快地使我的哈希算法

Question

我的问题与CS50,pset5的任务有关.对于那些不了解的人,我会试着解释一下.没什么特别的.我只需要创建将输入字典文件的函数(之前写过,该文件中的所有单词都是大写的),其中包含超过20K的单词,并以某种方式对它们进行排序.我已经制作了简单而天真的算法,构建了哈希表,根据他们的第一个字母对单词进行排序.我已经通过CS50的所有检查,所以我的程序运行良好.但与课程相比 - 它太慢了.执行人员的时间是0.1秒,但对于我的 - 5.0s - 7.0s.我可以在此代码中改进哪些内容以加快速度？或者我应该彻底改变一切吗？我没有优化经验,因为刚开始学习.从你们任何人那里学习会很棒=)在此先感谢!

// Some constant values, which are declared before the function
#define LENGTH  46
#define ALPHALENGTH  26
/* Definition of node struct. Nothing special, in fact =) */
typedef struct node {
    char word[LENGTH +1];
    struct node *next;
} node;

node *hashTable[ALPHALENGTH];

bool load(const char *dictionary) { 
    FILE *f = fopen(dictionary, "r");

    if (f == NULL) {
        return false;
    }

    char word[LENGTH + 1];    
    int hash = 0;

    for (int i = 0; i < ALPHALENGTH; i++) {
        hashTable[i] = NULL;
    }

    // 46 - is LENGTH, but for some reason it is impossible 
    // to put variable`s name between quotation marks
    while (fscanf(f, "%46s", word) == 1) {
        // make every letter lowercase to get result from 0 - 25
        hash = tolower(word[0]) - 'a';
        node *new_node = malloc(sizeof(node));
        strcpy(new_node->word, word);

        // check if element is first in the list
        if (hashTable[hash] == NULL) {
            new_node->next = NULL;
            hashTable[hash] = new_node;
        } else {
            node *ptr = hashTable[hash];

            do {
                if (ptr->next == NULL) {
                    break;
                }
                ptr = ptr->next;
            } while (true);

            ptr->next = new_node;
            new_node->next = NULL;
        }
    }

    fclose(f);

    return true;
}

Answer 1

你的问题不是你的哈希函数; 这是你的哈希表太小了.

从事物的声音来看,你有大约26个哈希桶,超过20,000个单词.这在每个桶中放置750到1000个单词.(在某些情况下可能更多,因为你使用的哈希函数并不统一.例如,很少有单词开头x或者q.)

尝试将哈希表扩展为1000个条目(例如),这样每个桶中大约有20个条目.你需要一个新的哈希函数来做到这一点; 任何事情都可行,但为了更好地工作,需要生成最大到表大小的值.(例如,将所有字母的值加在一起将不起作用,因为它几乎不会达到1000.)

Answer 2

问题不在于您的哈希函数，也不在于哈希表的大小，而在于您的列表管理：将单词附加到相应列表的方法的复杂度为O(N ² )。

顺便说一句，您的哈希函数不是用于哈希，而是用于调度。您仅根据每个单词的第一个字母对表进行排序，使具有相同首字母的单词保持相同的顺序。如果您打算对字典进行完全排序，您仍然需要对每个列表进行排序。

通过在列表前面添加并在解析阶段结束时反转列表，您可以显着提高性能，同时保持相同的语义。

对于包含 2 万个单词的字典，下面的代码运行速度快了50 倍（正如 CS50 网站所预期的那样）：

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

#define LENGTH  46
#define ALPHALENGTH  26
typedef struct node {
    struct node *next;
    char word[LENGTH +1];
} node;

node *hashTable[ALPHALENGTH];

bool load(const char *dictionary) {
    FILE *f = fopen(dictionary, "r");

    if (f == NULL) {
        return false;
    }

    char word[LENGTH + 1];
    int hash = 0;

    for (int i = 0; i < ALPHALENGTH; i++) {
        hashTable[i] = NULL;
    }

    while (fscanf(f, "%46s", word) == 1) {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
            return false;
        // make every letter lowercase to get result from 0 - 25
        hash = tolower(word[0]) - 'a';
        strcpy(new_node->word, word);
        /* prepending to the list */
        new_node->next = hashTable[hash];
        hashTable[hash] = new_node;
    }

    for (int i = 0; i < ALPHALENGTH; i++) {
        node *n, *prev, *next;
        /* reverse list */
        for (prev = NULL, n = hashTable[i]; n != NULL; ) {
            next = n->next;
            n->next = prev;
            prev = n;
            n = next;
        }
        hashTable[i] = prev;
    }

    fclose(f);

    return true;
}

void save(void) {
    for (int i = 0; i < ALPHALENGTH; i++) {
        for (node *n = hashTable[i]; n != NULL; n = n->next) {
            puts(n->word);
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc > 1) {
        if (load(argv[1]))
            save();
    }
}

将 更改fscanf()为更简单的fgets()可能会带来边际性能改进，但代价是字典格式的语义更加严格。