ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較） - プログラマはサイコロを振らない
ハッシュは遅いという意見があるようだが、実装や使い方を誤らなければ、基本的にツリーよりハッシュの方が速い。 （この記事は以前書いた「ハッシュは本当に遅いのか？いや、遅くない（反語）」を簡潔にまとめたものです） ハッシュとツリーの速度を比較した結果が次のグラフだ（ハッシュはパラメータを適切に設定（後述））。挿入、参照（検索）、削除の合計時間を測定した。（横軸は要素数、縦軸は時間、横軸は対数スケール） 「ハッシュは本当に速いのか?」の検証 速いはずのハッシュが二分木にはかないません。ハッシュは速いという常識をくつがえす結果となりました。 http://www.s34.co.jp/cpptechdoc/article/hash/:itle=ハッシュは本当に速いのか? Googleで「ハッシュ 速い」で検索すると上記のページが一番上に表示される（2008-08-04現在）。しかし、このページに掲載
ハッシュは本当に遅いのか？いや、遅くない（反語） - プログラマはサイコロを振らない
この記事を簡潔にまとめた記事「ハッシュは二分木（ツリー）より速い」を掲載しました。（2008-08-04） ハッシュと二分木（ツリー）*1では普通はハッシュの方が速いとされる（ハッシュは挿入、参照、削除の時間計算量がO(1)、二分木はO(log N)）。しかし、ハッシュは動作が複雑なため、実際はあまり二分木と速度が変わらないとも言われる。 それをC++で検証した記事を見つけた。結論は、二分木よりハッシュの方が遅いというものだ。 ハッシュは本当に速いのか? - S34 http://www.s34.co.jp/cpptechdoc/article/hash/ ハッシュは本当に遅いのか - 山に生きる http://d.hatena.ne.jp/pmoky/20050502/1114966341 では、JavaのHashSetとTreeSet（またはHashMapやTreeMap）でも同じこと
株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ
STLport のハッシュ・コンテナ 標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。 これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。 これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。 SGI(Silicon Graphics社)のSTL実装をベースに
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
