20

我需要一个支持快速插入和删除（键，值）对的数据结构，以及“获取随机键”，它与字典的 random.choice(dict.keys()) 执行相同的操作。我在互联网上搜索过，尽管它是线性时间，但大多数人似乎对 random.choice(dict.keys()) 方法感到满意。

我知道更快地实现这一点是可能的：

  • 我可以使用调整大小的哈希表。如果我保持键与槽的比率在 1 和 2 之间，那么我可以选择随机索引，直到遇到非空槽。我只看 1 到 2 个键，期待。
  • 我可以使用 AVL 树在保证最坏情况 O(log n) 的情况下获得这些操作，并增加等级。

不过，有什么简单的方法可以在 Python 中实现这一点吗？好像应该有！

4

5 回答 5

5

这可能与上面列出的特定用例并不特别相关，但这是我在寻找一种很好地掌握字典中“任何”键的方法时遇到的问题。

如果您不需要真正的随机选择，而只需要一些任意键，那么我找到了两个简单的选项：

key = next(iter(d))    # may be a little expensive, but presumably O(1)

仅当您乐于使用字典中的键+值时，第二个才真正有用，并且由于突变在算法上的效率不高：

key, value = d.popitem()     # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
    d[key] = value
于 2012-09-11T06:49:57.870 回答
4

[编辑：完全重写，但在这里保留完整的评论。]

下面是字典包装器的实现，其中 O(1) 获取/插入/删除，以及 O(1) 选择随机元素。

主要思想是我们想要一个 O(1) 但任意映射range(len(mapping))到键。这将让我们得到random.randrange(len(mapping))，并通过映射传递它。

在您意识到我们可以利用映射可以是任意的这一事实之前，这很难实现。实现 O(1) 时间硬边界的关键思想是：每当删除一个元素时，将其与最高的任意 id 元素交换，并更新任何指针。

class RandomChoiceDict(object):
    def __init__(self):
        self.mapping = {}  # wraps a dictionary
                           # e.g. {'a':'Alice', 'b':'Bob', 'c':'Carrie'}

        # the arbitrary mapping mentioned above
        self.idToKey = {}  # e.g. {0:'a', 1:'c' 2:'b'}, 
                           #      or {0:'b', 1:'a' 2:'c'}, etc.

        self.keyToId = {}  # needed to help delete elements

获取、设置和删除：

    def __getitem__(self, key):  # O(1)
        return self.mapping[key]

    def __setitem__(self, key, value):  # O(1)
        if key in self.mapping:
            self.mapping[key] = value
        else: # new item
            newId = len(self.mapping)

            self.mapping[key] = value

            # add it to the arbitrary bijection
            self.idToKey[newId] = key
            self.keyToId[key] = newId

    def __delitem__(self, key):  # O(1)
        del self.mapping[key]  # O(1) average case
                               # see http://wiki.python.org/moin/TimeComplexity

        emptyId = self.keyToId[key]
        largestId = len(self.mapping)  # about to be deleted
        largestIdKey = self.idToKey[largestId]  # going to store this in empty Id

        # swap deleted element with highest-id element in arbitrary map:
        self.idToKey[emptyId] = largestIdKey
        self.keyToId[largestIdKey] = emptyId

        del self.keyToId[key]
        del self.idToKey[largestId]

选择一个随机（键，元素）：

    def randomItem(self):  # O(1)
        r = random.randrange(len(self.mapping))
        k = self.idToKey[r]
        return (k, self.mapping[k])
于 2012-05-31T20:42:20.980 回答
3

这是一个有点复杂的方法：

  • 为每个键分配一个索引，将其与字典中的值一起存储。
  • 保留一个表示下一个索引的整数（我们称之为 next_index）。
  • 保留已删除索引（间隙）的链接列表。
  • 保留将索引映射到键的字典。
  • 添加键时，检查使用（并删除）链表中的第一个索引作为索引，或者如果列表为空，则使用并递增 next_index。然后将键、值和索引添加到字典 ( dictionary[key] = (index, value)) 并将键添加到索引到键的字典 ( indexdict[index] = key)。
  • 移除键时，从字典中获取索引，从字典中移除键，从索引到键的字典中移除索引，将索引插入到链表的最前面。
  • 要获取随机密钥，请使用类似random.randrange(0, next_index). 如果索引不在 key-to-index 字典中，请重试（这应该很少见）。

这是一个实现：

import random

class RandomDict(object):
    def __init__(self): # O(1)
        self.dictionary = {}
        self.indexdict = {}
        self.next_index = 0
        self.removed_indices = None
        self.len = 0

    def __len__(self): # might as well include this
        return self.len

    def __getitem__(self, key): # O(1)
        return self.dictionary[key][1]

    def __setitem__(self, key, value): # O(1)
        if key in self.dictionary: # O(1)
            self.dictionary[key][1] = value # O(1)
            return
        if self.removed_indices is None:
            index = self.next_index
            self.next_index += 1
        else:
            index = self.removed_indices[0]
            self.removed_indices = self.removed_indices[1]
        self.dictionary[key] = [index, value] # O(1)
        self.indexdict[index] = key # O(1)
        self.len += 1

    def __delitem__(self, key): # O(1)
        index = self.dictionary[key][0] # O(1)
        del self.dictionary[key] # O(1)
        del self.indexdict[index] # O(1)
        self.removed_indices = (index, self.removed_indices)
        self.len -= 1

    def random_key(self): # O(log(next_item/len))
        if self.len == 0: # which is usually close to O(1)
            raise KeyError
        while True:
            r = random.randrange(0, self.next_index)
            if r in self.indexdict:
                return self.indexdict[r]
于 2012-05-31T21:00:47.427 回答
1

要获得 O(1) 空间，您需要一个数组数据结构和一个将值存储在数组及其索引中的字典。

然后，在添加值时，您只需将它们推送到数组和字典中，并在数组中使用它的索引。

然后你可以随机访问，因为你使用的是数组数据结构。

删除值时，您会查看要在字典中删除的值的索引。然后用数组中的最后一个值替换数组中的那个值（确保它不是最后一个元素）和 pop() 数组中的最后一个值。之后，您使用已删除的值索引更新字典中替换值（数组中的最后一个值）的键。最后，您删除要删除的值的键和值，因为在字典中没有意义。

class RandomizedSet:

    def __init__(self):
        self.container = []
        self.indices = {}
       
        
    def insert(self, val: int) -> bool:
        if val in self.indices:
            return False
        
        self.indices[val] = len(self.container)
        self.container.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.indices:
            return False
        
        idxOfValueToRemove = self.indices[val]
        lastValue = self.container[-1]
        
        if idxOfValueToRemove < len(self.container)-1:
            self.container[idxOfValueToRemove] = lastValue
            self.indices[lastValue] = idxOfValueToRemove
    
        self.container.pop()
        
        del self.indices[val]
    
        return True
        
        
            

    def getRandom(self) -> int:
         return random.choice(list(self.container))
于 2021-10-22T10:21:25.310 回答
0

我有同样的问题并写了

https://github.com/robtandy/randomdict

我希望它对你有帮助！它提供对随机键、值或项目的 O(1) 访问。

于 2015-09-27T15:17:25.037 回答