2019/12/30 今日したこと

Today I Did

  • AOJ の本をちまちま進める
  • Stack, Queue, 双方向連結リストという基本的なデータ構造の実装(例)を知った
  • 双方向連結リスト(Doubly Linked List)が結構面白かった。初めて自分で実装したと思う。
  • C++ のポインタの文法がわからなくて混乱したが、なんとかなった。 printf バンザイ。
    • nil->prev を一度も定義していないのに insert を実行すると nil->prev がちゃんと定義される理由がわからなかったが、初期化時に nil->next = nil と定義しているので nil->next->prev は最初のインサート時には nil->prev になる(nil->next = nil が成り立っているため)
  • 線形探索、二分探索、ハッシュ法を知る
  • ハッシュ法のキーの作り方にあんまり納得がいかなかったけど、たぶんキーの作り方はなんでもいい
    • とはいえキーだけで衝突が防げるならそれにこしたことはないから、いろんな情報を使ってキーを生成しているのだと思われる
  • 実際には衝突を防ぐことが大事で、互いに素であれば f_x: y |-> x * y が単射(に近いことが起こる)のででかい素数をとっておけばまぁ大丈夫ということなのだと思っている
  • C のサンプルを写経したので Golang でも書いてみた。だいたい実装同じだけど