如何用Python在O(1)的字典中获得随机密钥?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (74)

我需要一个支持FAST插入和删除(键,值)对的数据结构,以及“获取随机密钥”,它与字典中的random.choice(dict.keys())具有相同的功能。我在互联网上搜索过,大多数人似乎对random.choice(dict.keys())方法感到满意,尽管它是线性时间。

我意识到可以更快实现这一点:

  • 我可以使用调整大小的哈希表。如果我认为密钥与时隙的比例在1和2之间,那么我可以选择随机索引,直到我点击一个非空插槽。期待中,我只看1到2个键。
  • 我可以使用AVL树在保证最坏情况O(log n)的情况下获得这些操作,并增加rank。

虽然有没有简单的方法可以在Python中实现这一点?好像应该有!

提问于
用户回答回答于

这是一个有些复杂的方法:

  • 为每个键分配一个索引,并用字典中的值存储它。
  • 保留一个表示下一个索引的整数(我们称之为next_index)。
  • 保留已删除索引(间隙)的链接列表。
  • 保留一个字典将索引映射到键。
  • 添加密钥时,请检查链接列表中第一个索引的使用(并除去)作为索引,或者如果列表为空,则使用并增加next_index。然后将键,值和索引添加到字典(dictionary[key] = (index, value))中,并将键添加到索引键字典(indexdict[index] = key)中。
  • 删除密钥时,从字典中获取索引,从字典中删除密钥,从索引到密钥字典中删除索引,然后将索引插入链表的前面。
  • 要得到一个随机密钥,可以使用类似的东西获得一个随机整数random.randrange(0, next_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]
用户回答回答于

这可能与上面列出的具体用例没有特别的关系,但这是我在寻找一种方法来很好地获得字典中“任何”键的方法时遇到的问题。

如果你不需要一个真正的随机选择,但只需要一些任意键,以下是我找到的两个简单选项:

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

第二个是真正有用的,只有当你很乐意使用字典中的键+值,并且由于突变(s)不会像算法上的高效:

key, value = d.popitem()     # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
    d[key] = value

扫码关注云+社区

领取腾讯云代金券