実世界の実行時間を短縮するためにハッシュテーブルを最適化するにはどうすればよいですか？

Question

以下は、ハッシュテーブルを使ってファイル（辞書）をメモリにロードする私のプログラムの一部です。辞書には、1行に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[]定義が投稿されていません。このような小規模の固定テーブルを使用することは、パフォーマンスにとっては賢明ではありません。

B）"%s"は、gets()と同じくらい安全です。どちらも悪いです。 fscanf(fp,"%s",n->word);の代わりにfgets()を使用してください。

C）if(feof(fp))の代わりに、fscanf()/fgets()の戻り値を確認してください。

D）isalpha(n->word[0]) - >isalpha((unsigned char) n->word[0])負の値に対処するには、charの値を使用します。

E）メモリ割り当ての失敗を確認します。

F）他の問題は、未送信のコードによっても発生することがあります。

単純なテストケースを作成し、最小のコードがで動作することを確認し、パフォーマンス改善を求めるためにcodereview.stackexchange.comに投稿することを検討してください。

Answer 2

ファイル内のすべての単語が異なることを前提としています。それは辞書の合理的な前提ですが、それは悪い防御プログラミングです。入力はあなたを得るために外に出ていると常に仮定すべきです。つまり、あなたは本当にそれについて何も仮定することはできません。

しかし、この場合、ハッシュテーブル内の繰り返しの単語が機能しないと主張できます。彼らはちょうどそれをわずかに遅くする。誤った入力はバグ、未定義の動作、または他の災害を引き起こさないので、参照語が一意であるという要件を文書化することはわずかに許容可能である。

実際に重複をチェックしていない場合、挿入するたびにハッシュバケット全体を移動する必要はありません。新しいエントリをバケットの最後に挿入するのではなく、バケットの先頭に挿入すると、スキャンが回避され、バケットが大きい場合には大幅に高速化されます。

もちろん、その最適化は辞書の読み込み時にのみ使用できます。初期化が完了すると、ハッシュテーブルを使用するのに役立つことはなく、スタートアップコードをハイパー最適化する価値はほとんどありません。