無償のプログラミング入門講座CS50xをやってみる Week5

全体(7.5h)

早いもので全体の半分が終わりました。また、C言語での課題提出も今週で終わりのようです。来週からはC言語よりも慣れているPythonなので楽にできるかもしれないです。

先週の反省を生かして平日に動画を見進めたり、昼休みにノートの見直しをしたりしました。問題数も少なかったので、今週は、比較的楽に終わらせることができました。

レクチャー動画(2.5h)

平日の夜に何度かに分けて観て終わったのは木曜でした。BSTへの値の挿入はO(log n)、ハッシュテーブルについて調べたくなったけど、Pset5で実装するみたいだからその時の楽しみにしておこうと思った。FIFO（フィフォ）、LIFO（ライフォ）について概念的には知ってたけど、PushとPopはスタックに紐づく概念だったのはちゃんと理解していなかった。

Lab 5 - inheritance(0.5h)

３世代分の血液型の遺伝をシュミレートする問題。再帰関数を使うのでちょっと戸惑うけどほとんどのコードは提供されているので、実際は20行ほど書けば完了する簡単な問題。ポインタが指す構造体のプロパティにアクセスする「->」ですが、PHPであったことがある気がする。

Problem Set 5 - Speller(4.5h)

ハッシュテーブルの追加とメモリ解放、ハッシュ関数を実装して、14万個を超える単語をハッシュテーブルに保存して与えられた文章に登場する単語がハッシュテーブルに存在してるか判定する問題

与えられるテキストに『LA LA LAND』が含まれていて、懐かしくさでちょっと読んでしまいました。

ハッシュ関数はネット上にある素敵なものを引っ張ってきてもいいとのことだったんですが、今回は自分で実装してみました。以下のような感じです。

// Hashes word to a number
unsigned int hash(const char *word)
{
   // prepare value
   unsigned int hash_value = 0;
   char c1 = tolower(word[0]);
   char c2 = tolower(word[1]);
   char c3 = tolower(word[2]);

   //calclate hash
   if (isalpha(c1))
   {
       hash_value += 784 * (c1 - 95);
   }
   else if (c1 == '\'')
   {
       hash_value += 784 * 1;
   }

   if (c2 != '\0')
   {
       if (isalpha(c2))
       {
           hash_value += 28 * (c2 - 95);
       }
       else if (c2 == '\'')
       {
           hash_value += 28 * 1;
       }
       if (c3 != '\0')
       {
           if (isalpha(c3))
           {
               hash_value += 1 * (c3 - 95);
           }
           else if (c3 == '\'')
           {
               hash_value += 1 * 1;
           }
       }
   }
   return hash_value;
}

今回出てくる文字は、アルファベットと「'」だけなので、26+1(')+1(null)=28種類、それを頭3文字で分類するので21,952種類のハッシュ値が出力されます。

スタッフの実行結果と比較すると、検索は私のコードの方が遅く、メモリの解放は私の方が早い、トータルでは私のコードの方が遅いので、ハッシュ値はもっと大きくしても、検索にかかる時間を短くした方が良さそうです。

コードの作成自体は大きく戸惑うところはなかったのですが、連結リストのメモリを解放するコードは動画では解説があるのに、ノートには記載されていないので動画を見ながら書き起こしました。

スコア

先週分