回答編集履歴
1
日本語を訂正orz
test
CHANGED
|
@@ -18,15 +18,15 @@
|
|
|
18
18
|
|
|
19
19
|
(A) ハッシュ値を求める計算量
|
|
20
20
|
|
|
21
|
-
(B) 2つの文字列の
|
|
21
|
+
(B) 2つの文字列の比較の計算量
|
|
22
22
|
|
|
23
23
|
|
|
24
24
|
|
|
25
|
-
を単純比較すれば1回当たりの(A),(B)の計算量では(B)の方が計算量が低いかも知れません。従って要素数が1とか2とかの文字列コレクションの中に特定の文字列が含まれているかを検索する場合はハッシュサーチを用いず、順サーチして求めた方が早い場合もあるでしょう。(実際世の中には「要素数がごく少数の場合は順サーチし、ある程度大きくなった場合にハッシュサーチに切り替える」といった凝ったライブラリーもあると思います。自分はPythonの実装には暗いため
|
|
25
|
+
を単純比較すれば1回当たりの(A),(B)の計算量では(B)の方が計算量が低いかも知れません。従って要素数が1とか2とかの文字列コレクションの中に特定の文字列が含まれているかを検索する場合はハッシュサーチを用いず、順サーチして求めた方が早い場合もあるでしょう。(実際世の中には「要素数がごく少数の場合は順サーチし、ある程度大きくなった場合にハッシュサーチに切り替える」といった凝ったライブラリーもあると思います。自分はPythonの実装には暗いため実装がどのようになっているか分かりませんが・・・)
|
|
26
26
|
|
|
27
27
|
|
|
28
28
|
|
|
29
|
-
一方、コレクションの中の要素数が一定以上多かったり、その中から何度も検索するような場合を考えてみてください。順サーチではコレクションの要素数の数Nに対して計算量のオーダーはO(N)になりますが、ハッシュアルゴリズムではO(1)になりますので
|
|
29
|
+
一方、コレクションの中の要素数が一定以上多かったり、その中から何度も検索するような場合を考えてみてください。順サーチではコレクションの要素数の数Nに対して計算量のオーダーはO(N)になりますが、ハッシュアルゴリズムではO(1)になりますので後者がはるかに高速になります。ちなみにハッシュ値の計算を同一のインスタンスに対して何度も行わなくてよいように、一度計算したらインスタンス内部に（ひそかに）記録されるような実装も一般的です(すみませんが、これについてもPythonの実装がそうなっているかどうかまでは自分は知りません)。
|
|
30
30
|
|
|
31
31
|
|
|
32
32
|
|
|
@@ -68,4 +68,4 @@
|
|
|
68
68
|
|
|
69
69
|
みたいなとんでもないポカをせずに済むのではないでしょうか・・・
|
|
70
70
|
|
|
71
|
-
「そんなことしないよ」と多くの方が思われると
|
|
71
|
+
「そんなことしないよ」と多くの方が思われることでしょう。しかし自分はこんな実装を過去にみたことがあります。おもわず「あわわ・・・」と思ってしまいました。
|