Python设置具有弹出随机元素的能力

Question

我需要一个Python(2.7)对象,其功能类似于集合(快速插入,删除和成员资格检查),但能够返回随机值.以前在stackoverflow上提出的问题有以下答案:

import random
random.sample(mySet, 1)

但是对于大型集合来说这是非常慢的(它在O(n)时间内运行).

其他解决方案不够随机(它们依赖于python集的内部表示,这会产生一些非随机的结果):

for e in mySet:
    break
# e is now an element from mySet

我编写了自己的基本类,它具有恒定的时间查找,删除和随机值.

class randomSet:
    def __init__(self):
        self.dict = {}
        self.list = []

    def add(self, item):
        if item not in self.dict:
            self.dict[item] = len(self.list)
            self.list.append(item)

    def addIterable(self, item):
        for a in item:
            self.add(a)

    def delete(self, item):
        if item in self.dict:
            index = self.dict[item]
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                del self.list[index]
            else:
                self.list[index] = self.list.pop()
                self.dict[self.list[index]] = index
                del self.dict[item]

    def getRandom(self):
        if self.list:
            return self.list[random.randomint(0,len(self.list)-1)]

    def popRandom(self):
        if self.list:
            index = random.randint(0,len(self.list)-1)
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                return self.list.pop()
            returnValue = self.list[index]
            self.list[index] = self.list.pop()
            self.dict[self.list[index]] = index
            del self.dict[returnValue]
            return returnValue

有没有更好的实现,或对此代码进行任何重大改进？

Answer 1

我认为最好的方法是使用MutableSet抽象基类collections.从继承MutableSet,然后定义add,discard,__len__, __iter__,和__contains__; 也可以重写__init__为可选地接受序列,就像set构造函数一样.MutableSet提供set基于这些方法的所有其他方法的内置定义.这样你就可以set便宜地获得完整的界面.(如果你这样做,addIterable就会以你的名义为你定义extend.)

discard在标准set界面中看起来就像你在delete这里所说的那样.所以重命名delete为discard.此外,popRandom您可以popRandom像这样定义,而不是使用单独的方法:

def popRandom(self):
    item = self.getRandom()
    self.discard(item)
    return item

这样您就不必维护两个单独的项目删除方法.

最后,在项目删除方法中(delete现在,discard根据标准设置界面),您不需要if语句.而不是测试是否index == len(self.list) - 1只是将列表中的最终项与要弹出的列表的索引处的项交换,并对反向索引字典进行必要的更改.然后弹出列表中的最后一项并将其从字典中删除.无论是否有效index == len(self.list) - 1:

def discard(self, item):
    if item in self.dict:
        index = self.dict[item]
        self.list[index], self.list[-1] = self.list[-1], self.list[index]
        self.dict[self.list[index]] = index
        del self.list[-1]                    # or in one line:
        del self.dict[item]                  # del self.dict[self.list.pop()]