Library Checker - Associative Array に関するいろいろ

Last updated Jun 12, 2020

• Algorithm

[Library Checker - Associative Array]を解くに当たってのいろいろをまとめておきます.

Associative Arrayは, Mapとよく呼ばれるデータ構造です. キーとそれに対応する値の組を保持し, キーで検索して値を参照することができます.

Associative Arrayを実現するデータ構造は,

• Map型の平衡二分探索木(ただし, キーが比較可能であることが条件)
  • std::map
  • 自作
• HashMap
  • std::unordered_map
  • 自作(メインテーマ)

Submit Info #12076

これを基準にしていきます

Submit Info #12082

insert/eraseの非再帰AVL Treeを持ってません, すみません…
merge/splitの非再帰AVL Treeを無理やりMapにしたものです. 余分なデータとか, 探索をしているのでもっと早くなると思います.

Submit Info #12083

std::unordered_mapだとTLEします. unordered_map_killer_01にやられていますね.
これは, std::unordered_mapのhash衝突による速度低下をさせてみる - うさぎ小屋で紹介されているように, std::unordered_mapをそのまま使うとハッシュ衝突をより起こすケースでTLEになってしまいます. 対策としては,

• std::mapを使う
• hash関数をランダムに変える

です. hash関数については, 下に書きます.

Submit Info #9787

自作する際には, この 高速なハッシュテーブルを設計する | POSTDという記事を参考にしました. とてもわかりやすいので, 自作する, しないにしろ読んでおいて損はないです.

• オープンアドレス法: 衝突したら, テーブルの空いている別の場所を探す
• 2冪の制約: mod操作が早いので
• 線形探索法: 衝突したらインデックスをインクリメントしていって探索する
• ハッシュをメモしない

という方針で実装しました.

ハッシュ関数については, Gist - badboy/inthash.md Integer Hash Functionを参考にしました. ハッシュ関数の実装と解説が載っています. 解説は読み切れていません…

Submit Info #12087

ハッシュ関数を変えるとstd::unordered_mapでもACできましたが, 自作のほうがめっちゃ早いですね

自作HashMapを持っておくと, 他のデータ構造に後少し速さを求めたいときに使うことができたりするので便利です.
std::mapでACカウントだけしている人はぜひこの機会に書いてみてはいかがでしょうか.