効率的なadd、remove、random.choiceのためのPythonデータ構造

Question

私はaddの新しい要素、既存の要素removeを持つ組み込みのPythonデータ構造を探しています。定刻。

私はsetがこれを行うことを望んでいましたが、AFAIKはPythonセットからランダム要素を選択する唯一の方法はO（n）時間かかるrandom.choice(list(my_set))です。

私は効率と簡単な配備が必要なので、私はPythonに組み込まれているソリューションを非常に好むでしょう。残念ながら、Pythonは組み込みのツリーデータ型を持たないようです。

Answer 1

Pythonにはビルトインのデータ構造がありません。これは3つの要件すべてを満たしています。

つまり、自分でツリーを実装するのはかなり簡単です。リスト上で行う操作のみであるため

import random 

class ListDict(object): 
    def __init__(self): 
     self.item_to_position = {} 
     self.items = [] 

    def add_item(self, item): 
     if item in self.item_to_position: 
      return 
     self.items.append(item) 
     self.item_to_position[item] = len(self.items)-1 

    def remove_item(self, item): 
     position = self.item_to_position.pop(item) 
     last_item = self.items.pop() 
     if position != len(self.items): 
      self.items[position] = last_item 
      self.item_to_position[last_item] = position 

    def choose_random_item(self): 
     return random.choice(self.items) 

：

---

別のオプションはまた、その項目のリストを保持セットが効果的であるものを作成するために、リストと辞書を組み合わせることであろう.pop()と.append()のように、（ほとんどのPythonの実装では）一定以上の時間を費やすべきではありません。