如何在一个非常大的python字典中获取一个随机值

Question

给定一个包含数百万个条目的python dict,从中获取和删除随机(k,v)对的最有效方法是什么？

dict不断增长,并且经常调用随机删除函数.

python2引用最多的解决方案random_key = random.choice(the_dict.keys())太慢了,因为首先创建了所有键的列表.由于dict中有许多元素,因此该解决方案不起作用.

另一个提出的解决方案是the_dict.popitem(),但这不会返回真正的随机对象,而是取决于dict的内部排序.

第三种解决方案也是减速器:

 it = the_dict.iterkeys()

 for i in range (random.randint(0, len(the_dict)-1)):
     next(it)
 random_key = next(it)

在旁边remove_random(),有时the_dict.pop(x)需要特定密钥.因此,基于简单列表的二级索引不起作用.

用字典可以有效地解决这个问题吗？

Answer 1

一种解决方案是使用每个键到一个整数的双向映射,以允许通过使用random.randrange(0,N)随机选择一个密钥,从一个双向映射到密钥的整数范围中进行选择,其中N是键数.

添加新密钥只会将其分配给下一个更高的int.在删除键值对之前,删除键会将该键的int重新分配给分配了先前最高int的键.为清晰起见提供了Python代码.

Python代码:

def create(D): # O(len(D))
    # Create the bidirectional maps from the dictionary, D
    keys = D.keys()
    ints = range(len(keys)
    int_to_key = dict(zip(keys, ints)) 
    key_to_int = dict(zip(ints, keys))
    return (int_to_key, key_to_int)

def add(D, int_to_key, key_to_int, key, value): # O(1)
    # Add key-value pair (no extra work needed for simply changing the value)
    new_int = len(D)
    D[key] = value
    int_to_key[new_int] = key
    key_to_int[key] = new_int

def remove(D, int_to_key, key_to_int, key): # O(1)
    # Update the bidirectional maps then remove the key-value pair

    # Get the two ints and keys.
    key_int = key_to_int[key]
    swap_int = len(D) - 1 # Should be the highest int
    swap_key = int_to_key[swap_int]

    # Update the bidirectional maps so that key now has the highest int
    key_to_int[key], key_to_int[swap_key] = swap_int, key_int
    int_to_key[key_int], int_to_key[swap_int] = swap_key, key

    # Remove elements from dictionaries
    D.remove(key)
    key_to_int.remove(key)
    int_to_key.remove(key)

def random_key(D, int_to_key): # O(1)
    # Select a random key from the dictionary using the int_to_key map
    return int_to_key[random.randrange(0, len(D))]

def remove_random(D, int_to_key, key_to_int): # O(1)
    # Randomly remove a key from the dictionary via the bidirectional maps
    key = random_key(D, int_to_key)
    remove(D, int_to_key, key_to_int, key)

注意:在不使用上述相应功能的情况下从D添加/删除键将破坏双向映射.这意味着最好将其作为一个类来实现.