Python集具有弹出随机元素的功能 [英] Python set with the ability to pop a random element
问题描述
我需要一个功能类似于集合(快速插入，删除和成员资格检查)但能够返回随机值的Python(2.7)对象.先前在stackoverflow上提出的问题有如下答案:
I am in need of a Python (2.7) object that functions like a set (fast insertion, deletion, and membership checking) but has the ability to return a random value. Previous questions asked on stackoverflow have answers that are things like:
import random
random.sample(mySet, 1)
但是对于大型集合而言，这相当慢(它以O(n)时间运行).
But this is quite slow for large sets (it runs in O(n) time).
其他解决方案不够随机(它们取决于python集的内部表示，这会产生一些非常不随机的结果):
Other solutions aren't random enough (they depend on the internal representation of python sets, which produces some results which are very non-random):
for e in mySet:
break
# e is now an element from mySet
我编写了自己的基本类，该类具有恒定的时间查找，删除和随机值.
I coded my own rudimentary class which has constant time lookup, deletion, and random values.
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
对此是否有更好的实现，或对此代码有任何重大改进?
Are there any better implementations for this, or any big improvements to be made to this code?
推荐答案
I think the best way to do this would be to use the MutableSet abstract base class in collections. Inherit from MutableSet, and then define add, discard, __len__, __iter__, and __contains__; also rewrite __init__ to optionally accept a sequence, just like the set constructor does. MutableSet provides built-in definitions of all other set methods based on those methods. That way you get the full set interface cheaply. (And if you do this, addIterable is defined for you, under the name extend.)
discard似乎就是您在此处称为delete的名称.因此，将delete重命名为discard.另外，除了拥有单独的popRandom方法之外，您还可以像这样定义popRandom:
discard in the standard set interface appears to be what you have called delete here. So rename delete to discard. Also, instead of having a separate popRandom method, you could just define popRandom like so:
def popRandom(self):
item = self.getRandom()
self.discard(item)
return item
这样，您不必维护两种单独的项目删除方法.
That way you don't have to maintain two separate item removal methods.
最后，在项目删除方法(根据标准set接口，现在为delete，现在为discard)中，不需要if语句.无需测试是否index == len(self.list) - 1，只需将列表中的最后一项与要弹出的列表的索引处的项交换，然后对反向索引字典进行必要的更改.然后从列表中弹出最后一项，并将其从字典中删除.无论是否index == len(self.list) - 1，它都可以工作:
Finally, in your item removal method (delete now, discard according to the standard set interface), you don't need an if statement. Instead of testing whether index == len(self.list) - 1, simply swap the final item in the list with the item at the index of the list to be popped, and make the necessary change to the reverse-indexing dictionary. Then pop the last item from the list and remove it from the dictionary. This works whether index == len(self.list) - 1 or not:
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()]
这篇关于Python集具有弹出随机元素的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
