25

我需要一个功能类似于集合（快速插入、删除和成员资格检查）但能够返回随机值的 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

有没有更好的实现，或者对这段代码有什么大的改进？

4

6 回答 6

20

我认为最好的方法是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()]
于 2012-09-25T17:25:46.443 回答
2

您可以采取的一种方法是派生一个新类，从该类set中使用派生自int.

然后您可以使用pop选择一个随机元素，如果它不是 salt 类型，则重新插入并返回它，但如果是 salt 类型，则插入一个新的、随机生成的 salt 对象（并 pop 选择一个新的目的）。

这将倾向于改变选择对象的顺序。平均而言，尝试次数将取决于加盐元素的比例，即摊销的 O(k) 性能。

于 2012-09-25T17:20:48.540 回答
1

我们不能实现一个新的类继承自set一些（hackish）修改，使我们能够以 O(1) 查找时间从列表中检索随机元素吗？顺便说一句，在 Python 2.x 上，您应该继承自object，即使用class randomSet(object). PEP8也是你需要考虑的 :-)

编辑：为了了解一些骇人听闻的解决方案可能有什么想法，这个线程值得一读： http: //python.6.n6.nabble.com/Get-item-from-set-td1530758.html

于 2012-09-25T17:02:18.693 回答
0

是的，我会以与您几乎相同的方式实现“有序集” - 并使用列表作为内部数据结构。

但是，我会直接从“set”继承，并且只跟踪内部列表中添加的项目（就像您所做的那样） - 并保留我不单独使用的方法。

每当集合通过特定于集合的操作（如 *_update 方法）更新时，可能会添加一个“同步”方法来更新内部列表。

如果使用“有序字典”不涵盖您的用例。（我刚刚发现尝试将 ordered_dict 键转换为常规集合并没有优化，因此如果您需要对数据进行集合操作，那么这不是一个选项）

于 2012-09-25T17:30:57.980 回答
0

如果您不介意只支持可比较的元素，那么您可以使用blist.sortedset.

于 2012-09-28T05:09:12.203 回答
0

这是一个从头开始的解决方案，它在恒定时间内添加和弹出。出于演示目的，我还包括了一些额外的集合函数。

from random import randint


class RandomSet(object):
  """
  Implements a set in which elements can be
  added and drawn uniformly and randomly in
  constant time.
  """

  def __init__(self, seq=None):
    self.dict = {}
    self.list = []
    if seq is not None:
      for x in seq:
        self.add(x)

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

  def pop(self, x=None):
    if x is None:
      i = randint(0,len(self.list)-1)
      x = self.list[i]
    else:
      i = self.dict[x]
    self.list[i] = self.list[-1]
    self.dict[self.list[-1]] = i
    self.list.pop()
    self.dict.pop(x)
    return x

  def __contains__(self, x):
    return x in self.dict

  def __iter__(self):
    return iter(self.list)

  def __repr__(self):
    return "{" + ", ".join(str(x) for x in self.list) + "}"

  def __len__(self):
    return len(self.list)
于 2017-07-12T00:15:57.890 回答