Мне нужен объект 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
Есть ли какие-либо улучшения для этого или какие-либо большие улучшения в этом коде?