辞書の空のキーを選択しますか？

Question

私は辞書に値を追加しています。私は自由にそれらをポップしています。ディクショナリ・キーは、テーブルの行番号のように、追加されて増分される整数です。

example = {1: data1, 
      2: data2, 
      3: data3, 
      4: data4, 
      5: data5} 

2を削除したとします。今では辞書に新しい要素を追加する場合、6の代わりに2を追加します。この問題のその他の詳細は次のとおりです。

• これは、私が望ましくない線形検索によって行うことができます。
• これは、removedのセットを維持することによって行うことができます。これは、メモリにない場合には時間の複雑さの項で線形探索よりも実行可能である。

私の質問は、これは簡単に実装できますが、問題の組み込みタイプですか？

Answer 1

削除されたキーを保存したいと思うようですが、その中には多くのものがありますが、ランダムな時間にそれらの中で最小のものをポップしたい場合があります。

これはheapq priority heap structureには完璧だと思われます。任意のアイテムを追加し、最小のものをポップするのは簡単です。それらはそれぞれO（log（n））時間で実行されます。ここで、nは以前に削除されたアイテムの保存数です。

キーを削除したり再追加する頻度や削除されたアイテムの最大数/通常数について知っていれば、より良いものを見つけることができます。しかし、heapqは一般的な用途に最適です。

あなたの「削除されたセット」のアイデアは最小のアイテムを見つけるための線形時間であるため、その操作が頻繁に行われるとheapqが優れています。

Answer 2

これは、すでに推奨されている@Rory Daultonのようにheapqモジュールを使用したちょっとした例です。これは、削除された項目のインデックスの優先度キューをfreeという名前のリストに維持します。新しいアイテムが追加されると、可能な限りそれらを再利用します。

空きインデックスがない場合でもアイテムを追加できるようにするため、使用されていない最高のインデックスを別の変数next-indexで追跡します。この値は再利用するインデックスがなく、まったく使用されていない新しいものが必要な場合に使用します。

import heapq 

example = {1: 'data1', 
      2: 'data2', 
      3: 'data3', 
      4: 'data4', 
      5: 'data5'} 

free = [] 
next_index = max(example.keys()) + 1 

def remove_item(d, index): 
    del d[index] 
    heapq.heappush(free, index) 

def add_item(d, data): 
    global next_index 

    try: 
     index = heapq.heappop(free) 
    except IndexError: 
     index = next_index 
     next_index += 1 
    d[index] = data 

remove_item(example, 2) 
remove_item(example, 5) 

add_item(example, 'data6') 
add_item(example, 'data7') 
add_item(example, 'data8') 

print(example) 

出力：dictのサブクラスで応答@rorydaulton後

{1: 'data1', 2: 'data6', 3: 'data3', 4: 'data4', 5: 'data7', 6: 'data8'} 

Answer 3

：

import heapq 

class Table(dict): 

    def __init__(self, *args, **kwargs): 
     self.removed = [] 
     self.last = 0 
     super(Table, self).__init__(*args, **kwargs) 

    def _get_next_key(self): 
     if len(self.removed)==0: 
      self.last += 1 
      key = self.last 
     else: 
      key = heapq.heappop(self.removed) 
     return key 

    def additem(self, value): 
     key = self._get_next_key() 
     self[key] = value 
     return key 

    def delitem(self, key): 
     super(Table, self).__delitem__(key) 
     heapq.heappush(self.removed, key) 

次に、あなたの代わりに完全にキーを削除するの

>>> t = Table() 
>>> t.additem(43) 
>>> t.additem(55) 
>>> t.additem(46) 
>>> t 
{1: 43, 2: 55, 3: 46} 
>>> t.delitem(2) 
>>> t.additem(1234567) 
>>> t 
{1: 43, 2: 1234567, 3: 43}