9

これが私の問題です。 のように動作するデータ構造が必要ですが、queue他のプロパティがいくつかあります。

  • 指定されたアイテムを簡単に削除できるはずですtag(このキュー内のすべてのアイテムには、tagそれらをグループ化する があります)
  • また、指定された 1 つのアイテムを削除できるようにする必要もありますkey(コレクションに追加されたすべてのアイテムには、そのような一意のキーがあります)。ここで、それが物事を単純化するなら、それがより速くなるならtag、私は削除することができます.key
  • このコレクションは並行環境で使用されるため、ロックの使用をできるだけ少なくすることは素晴らしいことです
  • キューの通常の FIFO プロパティを持つ必要があります。頭にないアイテムにアクセスする必要はありませんが、上記の削除動作が機能する必要があります。

私は C# を使用してこのソリューションを構築していますが、利用可能なコレクションが私のニーズを満たすとはほとんど信じていないため、アルゴリズムとデータ構造の定義にもっと興味があります。

論文、書籍、ブログ投稿、その他の参考文献は大歓迎です。

4

2 に答える 2

3

キュー部分に同時単一リンクリストを使用できるようです。キーによる削除の部分では、キュー内のノードを指す同時ハッシュ テーブル (ストライプ ロックは簡単に実行できます) を保持できます。

そのアプローチが失敗した場合は、データベース システムがこれを行う方法を調べてください。彼らはあなたが望むすべてを同時に行うことができます。データのプライマリ コピーを B ツリーに維持し、セカンダリ B ツリー インデックスを維持します。ロックには、同時ハッシュ テーブルを使用します。B ツリーには優れた同時実行性があります。これは、排他ロックの下でリーフを更新している間でも、B ツリーの上部を簡単に共有ロックできるためです。

于 2012-08-28T22:28:04.707 に答える
1

二重にマルチリンクされたリストと2つのハッシュテーブルを使用できると思います。

  • キューのリストの一部
  • タグでノードをグループ化するための別の部分
  • キーでノードにアクセスするための1つのハッシュテーブル
  • タグでノードにアクセスするための別のハッシュテーブル

Pythonの例（ごめんなさい...）

要素の挿入：

 items_table['item_key'] = new_item

 my_queue.tail.next = new_item
 new_item.previous = my_queue.tail
 my_queue.tail = new_item

 new_item.next_by_tag = tags_table['item_tag'] #head of tag's list
 tags_table['item_tag'].previous_by_tag = new_item
 tags_table['item_tag'] = new_item

キーによる要素の削除：

item = key_table['node_key']

item.next.previous = item.previous
item.previous.next = item.next

item.next_by_tag.previous_by_tag = item.previous_by_tag
item.previous_by_tag.next_by_tag = item.next_by_tag

del item

タグによる要素の削除：

def remove_elements_by_tag(tag_head):
    if tag_head == None:
        return
    else:
        remove_elements_by_tag(tag_head.next_by_tag)
        tag_head.next.previous = tag_head.previous
        tag_head.previous.next = tag_head.next

そんな感じ。それが役に立てば幸い。

于 2012-08-29T01:48:58.777 に答える