具有弹出随机元素能力的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

这段代码是否有更好的实现方式或者可以做出大幅度的改进？

- GrantS

---

为什么你不直接使用列表，在需要进行集合操作时将其转换为集合？… - Joran Beasley

这样可以让您在不影响性能的情况下交替添加元素和选择元素。您的实际场景是否真的遵循这种模式？如果您可以将所有元素的添加都集中在一起，那么您可以先使用 set，然后在获取随机元素之前将其转换为 list。 - Steven Rumbalski

@GrantS：你的意思是说列表创建很慢吗？那只需要做一次。这并不比在你的类中创建列表和字典要慢。 - Steven Rumbalski

如果您正在使用Python 2.x，请为了众人的利益继承自“object”，或者使用其他新式基类。不要使用旧式类（通过不声明超类）。否则，您可能会遇到难以调试的严重问题。 - jsbueno

@StevenRumbalski 顺便提一下，虽然这与原始问题无关，但使用 foo.items()、foo.keys()（相当于 list(foo)）或 foo.values() 更加简洁，而且每个方法都有一个“iter”版本可用于循环（生成迭代器而不是列表，因此速度稍快）（例如 foo.iterkeys()）。 - Izkata

Answer 1

我认为最好的方法是使用collections中的MutableSet抽象基类。继承MutableSet，然后定义add、discard、__len__、__iter__和 __contains__方法；还要重写__init__以可选地接受序列，就像set构造函数一样。MutableSet根据这些方法提供了所有其他set方法的内置定义。这样做可以便宜地获得完整的set接口。(如果您这样做，addIterable将以extend的名称为您定义。)

标准的set接口中的discard似乎就是您在这里称为delete的内容。因此请将delete重命名为discard。此外，您可以像下面这样定义popRandom而不需要单独定义一个方法：

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

这样，您就不必维护两种单独的项目删除方法。

最后，在您的项目删除方法中（现在是delete，根据标准设置接口是discard），您不需要if语句。而是将列表中的最后一个项目与要弹出的列表索引处的项目交换，并对反向索引字典进行必要的更改。然后从列表中弹出最后一个项目并从字典中删除它。这适用于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()]

- senderle

---

如果可以的话，我会给加2分。这么少的代价就能得到一个集合接口，真是太好了。而且优化实现的建议也非常棒。 - Steven Rumbalski

如果这是楼主使用的解决方案，我会非常有兴趣看到T(setsize)图表，其中包括默认集合上的O(N)查找解决方案和此解决方案，其中T表示查找所需的时间。 - Dr. Jan-Philip Gehrcke

Answer 2

您可以采用一种方法，从set派生一个新类，在该类中使用来自int派生类型的随机对象进行盐处理。

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

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

- Marcin

---

+1，对这个想法表示赞同，但我想知道是否测试过某种形式的实现。我不确定盐值设置是否会那么有效。 - jsbueno

@jsbueno 插入顺序已知会影响集合迭代的顺序，但是我猜这也取决于所使用的哈希方案的细节。 - Marcin

Answer 3

这里有一个从零开始的解决方案，可以在常数时间内添加和弹出。我还包括了一些额外的集合函数，以便演示。

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)

- markrogersjr

---

pop方法中存在错误：如果x！= None，则未定义i。 - Carlos Pinzón

Answer 4

我们不能从set继承一个新类并进行一些（hackish）修改，使我们能够在O（1）查找时间内检索列表中的随机元素吗？顺便说一下，在Python 2.x中，您应该从object继承，即使用class randomSet(object)。另外PEP8是您需要考虑的内容 :-)

编辑： 要获取有关hackish解决方案可能能够实现什么想法的一些想法，请阅读此线程： http://python.6.n6.nabble.com/Get-item-from-set-td1530758.html

- Dr. Jan-Philip Gehrcke

---

如果你的类没有其他基类并且你不使用 Python3，那么你应该始终明确地从 object 继承。 - l4mpi

为什么我要从set中继承？唯一可行的方法是使用指向列表中值索引的字典。它根本不使用集合，因此我不知道继承自set会有什么帮助。编辑：等等，我可能明白你的意思了。这里我的字典用途完全是不必要的吗？ - GrantS

不。从set继承会很低效，因为random.sample需要遍历整个集合，使其成为O(n)。 - Steven Rumbalski

@GrantS：我并不是说你应该让你的randomSet继承自set。我想到的是一种完全不同的解决方案，它基于set，但通过某种方式来“黑掉”set以便访问随机项。现在，我发现没有明显的方法可以在不遍历集合的情况下实现这一点。 - Dr. Jan-Philip Gehrcke

@martineau：谢谢您的批评 :) 我已经编辑了答案。我知道这几乎是空话。 - Dr. Jan-Philip Gehrcke

Answer 5

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

然而，我会直接从“set”继承，并在内部列表中跟踪添加的项目（就像您一样）-并保留我不使用的方法。

也许添加一个“同步”方法，在通过set特定操作更新集合时更新内部列表，例如*_update方法。

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

- jsbueno

Answer 6

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

- Neil G