2011-03-26から1日間の記事一覧
keyword ハッシュテーブル C++ 問題概要 N( 解法 前の記事にしたがってそのまま実装する。メモリ制限が64MBのとき確保できる32bitの配列のサイズは2^23が目安。安全を取って今回はサイズを2^22とした。このとき、特定のひとつのハッシュ値が衝突する確率はN/…
衝突の問題さえ回避すれば非常に優秀なデータ構造である。 弱点はメモリを大量に消費すること。メモリの局所化とは対極であること。for_eachみたいなことができない。STLにない(tr1とかextとか__gnu_cxxとかはさておき)等。 そもそもsetやmapと計算量がlog程…