私のハッシュアルゴリズムをより速く作る方法

Question

私の質問はCS50、pset5のタスクと関連しています。それについて知らない人のために、私は説明しようとします。非常に特別なものはありません。私はちょうど20キロ以上の単語を含んでいる辞書ファイル（前に書かれた、そのファイルのすべての単語が大文字である）を摂取する関数を作成する必要があり、何とかそれらを並べ替えます。私はハッシュテーブルを構築するシンプルで素朴なアルゴリズムを作りました。ハッシュテーブルは、最初の文字に応じて単語を並べ替えます。 CS50ですべての小切手を渡したので、私のプログラムはうまくいきます。しかしコースのものと比較すると、それは遅すぎる。人事の実行時間は0.1秒ですが、私の場合は5.0秒〜7.0秒です。このコードを改善してより速くするにはどうすればよいですか？あるいは、私はすべてを完全に変えるべきですか？私は最適化の経験がないので、ちょうど学習を始めたからです。皆さんのおかげで勉強するのはすばらしいことです。=）事前に感謝します！

// 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

問題は、あなたのハッシュ関数にあなたのサイズでもではありませんハッシュテーブルでは、それはあなたのリスト管理にあります：対応するリストに単語を追加する方法は、O（N ）の複雑さを持っています。

ところで、あなたのハッシュ関数は、ハッシュには使用されず、ディスパッチ用に使用されます。 テーブルは、各単語の最初の文字のみで並び、同じ頭文字の単語を同じ順序に保ちます。辞書を完全にソートするつもりなら、各リストをソートする必要があります。

リストに追加して構文解析フェーズの最後にリストを反転することで、同じセマンティクスを維持しながら、パフォーマンスを大幅に向上させることができます。 2万言葉を辞書については

、以下のコードは、（CS50サイトで予想通り）50回高速化を実行します：

#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(); 
    } 
} 

がfgets()単純にfscanf()を変更限界性能の向上を提供するかもしれません辞書形式に対するより限定的なセマンティクスを犠牲にして、

Answer 2

問題はハッシュ関数ではありません。あなたのハッシュテーブルが小さすぎるということです。

物事の音から、あなたは2万語を超える約26のハッシュバケットを持っています。これは、各バケットに750〜1000語の間に配置されます。 （たとえば、使用しているハッシュ関数が統一されていない場合は、xまたはqで始まる単語はほとんどありません）。

ハッシュテーブルを1000エントリに拡張してみてください）、各バケットに約20のエントリーがあるように。これを行うには新しいハッシュ関数が必要です。何かがうまくいくでしょうが、うまくいくためには、テーブルのサイズまでの値を生成する必要があります。 （それが1000に達することはほとんどないだろうとして、例えば、すべての文字の値は動作しません一緒に追加）