2

ハッシュ表のチェインほうで双方向リストのほうが優れている点はありますでしょうか?

有名な教科書のMIT教科書アルゴリズムイントロダクション第3版のP213の図11.3の解説文。
ハッシュ表をチェイン法で実装してる解説で疑問点があったので質問します。

「連結リストは一方向、あるいは双方向であり、図は削除が高速にできる双方向連結リストである」という記述があります。

一方向でも双方向でも実装ができるのはわかるのですが、「双方向のほうが削除が高速にできる」という記述の根拠がわかりません。

双方向だとprevがあるから逆にたどれるというのはわかりますが、削除の際にリストをたどる方向は最初の要素から一方向に外に向かってというイメージなので逆方向にたどれるメリットを感じません。削除が高速にできるというのもわかりません。

ちなみに英語版でも同様の解説でした。

双方向のほうが削除が高速にできるという記述の根拠を教えてください。もしこの記述や私の解釈がおかしければチェイン法における単方向、双方向リストのそれぞれのメリット・デメリットを教えてほしいです。

1
  • 1
    英語版Stack Overflowでの類似質問です (今手元にアルゴリズムイントロダクションが無いのでリンクだけ...): Hashtable with doubly linked lists?
    – nekketsuuu
    Commented 2019年6月6日 12:15

1 件の回答 1

4

双方向リストの削除という場合キーや位置を指定しての削除と、ノードそのものを指定しての削除とで考え方が違います。

キーや位置を指定して削除する場合、そのノードを見つけるために順にたどっていく必要があるので、単方向リストで prev を発見するのと変わりません。おそらくAkiyama Naoさんが想定してるのはこちら。
一方ノードそのものを指定する場合、双方向リストではそのノード自身や prev, next をリストを辿って見つける必要がないので単方向リストより高速です。

別の言い方をすれば、
Delete(Hash, Key) であれば単方向でも双方向でも大差ありませんが、
Delete(Hash, Node) であれば双方向のほうが早くなります。

型名等を省略した疑似コードではそこの部分がわかりづらくなってるので、注意深く見てみてください。


C#の双方向リストに関するドキュメントですが、比較しやすく記載されていたので参考に貼っておきます。
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.linkedlist-1.remove?view=netframework-4.8
ノードを指定して削除する場合の計算量はO(1)、値を指定して削除する場合O(n)となっています。

3
  • なるほど、ありがとうございます。 いただいた説明や英語版の質問を読んで以下のように理解しました。 - 双方向を使って、削除の対象がノード自体のときは、prev, nextのノードを探索する必要なくつなぎ替えることができるのでO(1) - ハッシュ表のキーを指定して削除するなら、単方向も双方向もO(N) ただ、そもそもハッシュ表に入ってるノードが手元にあってにあって、 それを使って削除するシーンってそんなにあるんですかね。 大体はキーを指定して削除するような。。。 たとえば、 delete user_hash[user_id] なオペレーションするときって、まずはuser_hash[user_id]のノードをO(N)で探索しますよね。 そのあとでO(1)で削除。 もし user = user_hash[user_id] で一度ノードを取得しておいてそのあとで、いろいろごにょごにょやって、その後で delete user とかならO(1)で削除できて今回の有用性が大変理解できます。 Commented 2019年6月7日 3:09
  • まぁ双方向のほうが多少メモリ使うけど、ノードが特定できてたら双方向のほうがO(1)で削除できて速いというメリットが教示できるから 単方向よりは素直にこれ使ったほうがいいでしょ、ということですかね。 Commented 2019年6月7日 3:11
  • 実際の有用性という意味で見ると、双方向リストにすることにそれほどメリットはないと思います。一つはおっしゃられるように、そんな使い方そうそうしないだろうという点で、 もう一つは単方向リストでも削除は検索と同じ計算量ででき、たいていはそれで充分という点です(うまく実装すれば平均O(1)。ただしその場合でも最悪O(N)なので双方向リストを使うことで最悪O(1)に改善できる)。
    – yudedako
    Commented 2019年6月7日 5:23

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。