随机采样一个 python 集而不转换为列表

Question

问题

我花了很多时间阅读有关在 python 中获取随机样本的各种答案，random.sample 似乎是自然而最常见的选择，但我正在尝试抽样来自 python set 对象，并希望能够高效地完成它。

由于 python 中非常好的和高效的集合功能（交叉点、差异等），我正在使用集合。就我的目的而言，集合是一种非常有效的数据结构，而列表则不是。我有一个算法情况，我在一个集合中有 N 个元素，并且可能需要为集合的每个采样占用任意大小的 N 个子样本。该集合的每个子采样都不是完全相同的集合，并且由我必须生成子样本的每个元素的属性定义。下面是一些模糊的代码，展示了算法的复杂性：

main_set = set(...) # Values sourced from elsewhere.
capacity = 20

for element in list:
    potential_values = main_set - element.set # Exclude values already in element
    sample_size = capacity - len(element.set) # Num needed to fill the set to capacity
    new_vals = sample(potential_values, sample_size) # <- insert sampling idea here

    element.set = element.set | new_vals # Union of sample and element set

根据我在网上收集的信息和一些测试，random.sample 似乎将 set 转换为 list 对象。 main_set - element.set、potential_values 的大小几乎总是远大于 element.set 的大小，因此如果必须在每次采样时将 potential_values 转换为列表，则算法将受到影响性能非常好。

那么，对于如何使用集合有效地执行此操作，有没有人有任何建议或想法？我感谢任何关于此事的意见，在任何人跳到 'premature optimization' 例程之前，我非常清楚这将要执行的规模以及 O(n) 和 O(n) 之间的区别^2) 相当可观。

澄清编辑：

我特别不关心所提供的任何sample()方法的输出。我从 potential_values 中提取的实际样本与 potential_values 的大小相比小。相反，所有建议的 sample() 方法都需要类似列表的输入才能工作，这意味着 potential_values 必须首先转换为可索引类型，这是我想要避免的。

我现在还意识到我以一种非常模糊的方式提出了大 O 表示法，可能不应该这样做。当我说我想避免 O(n^2) 时，我的意思是我想避免在循环内添加另一个 O(n) 操作。正如有人向我指出的那样，main_set - element.set 与 list(main_set) 具有相同的时间复杂度，因此它已经是 O(n^2)。添加 list 转换使整个算法更像 O(2n^2)，但其中的 none 非常重要。

Answer 1

你可以使用 heapq.nlargest 它可以接受任何可迭代对象并为其提供一个随机键来选择，例如：

import random, heapq

sample = heapq.nlargest(sample_size, your_set, key=lambda L: random.random())

注意 - 这会给你一个 list 对象，所以你需要在必要时转换它...

Answer 2

在 IPython 中快速尝试计时表明使用 heapq.nlargest 不一定比您现有的方法更好，请根据实际数据的特点适当调整：

import random
import heapq

set_size = 100000
sample_size = 1000

def sample_heapq(your_set, sample_size):
    sample = heapq.nlargest(sample_size, your_set, key = lambda e: random.random())
    return sample

def sample_original(your_set, sample_size):
    sample = random.sample(your_set, sample_size)
    return sample

eg_set = set(range(sample_size))

运行这些通过 timeit:

%timeit sample_heapq(eg_set, sample_size)
1000 loops, best of 3: 523 µs per loop

%timeit sample_original(eg_set, sample_size)
1000 loops, best of 3: 479 µs per loop

Answer 3

正如@user2357112 所建议的，这是我原始问题中代码的拒绝采样版本，它有效地从源集中采样 n 个元素，因为我只从 main_set 中采样尚未存在的值elements.set。

main_set = set(...) # Values sourced from elsewhere.
capacity = 20
listed_set = list(main_set) # initially convert set to list so we can sample
for element in list:
    while len(element.set) < capacity
        item = random.choice(listed_set)
        element.set.add(item) # Sets cannot contain duplicates, no conditional required

虽然这没有回答如何直接从 python 中的 set 进行采样的问题，但它确实有效地解决了我的算法试图做的事情。如果一段时间后，没有人想出直接从集合中采样或比这更有效的方法，我可能会将其标记为答案。感谢 @user2357112 的想法！

正如@LieRyan 指出的那样，如果 element.set 与 main_set 重叠很大一部分，该算法将无法从 random.choice() 中获取非重叠项。因此，如果我们期望重叠度很高，例如 50%，那么只需使用 main_set - element.set 获取两个集合之间的唯一项，并将其转换为列表，将比此方法快得多。本质上，该算法适用于 main_set 与 element.set 几乎没有重叠的情况（占 main_set 的百分比）。

Answer 4

取决于你对随机的定义。

只是一些元素，我不在乎是哪个：

[s.copy().pop() for i in range(count)]  # with replacement

copy = s.copy()
[copy.pop() for i in range(count)]  # without replacement

具有良好[伪]随机分布的元素：

copy = list(s)
random.sample(copy, count)

可重复的伪随机分布：

copy = sorted(s)
# random.seed(...)
random.sample(copy, count)

可重复伪随机，假设，运行时开销更少：

heapq.nlargest(...)  # per Jon or Marius

讨论：

set.pop() 已经删除并且 returns 任意元素，但是如果对象散列值在集合中相同，则这是完全可以预测的，例如如果每次都是相同的一组数字，如果每次设置不同也可以接受
set.copy() 是 O(N)
sorted();list.sort() 是 O(NlogN) 摊销的，可能因为集合是由散列随机化的
heapq.nlargest 可能是 O(N) 每个 Median of Medians，Python 实现是一个恒定大小的二进制堆，使其成为 O(N*log(n))，因为 N 元素是通过大小为 n 的堆筛过滤。请注意，sing key= 会增加显着的线性开销，因此 O(C*N*log(n))，您的域将决定是否 C*log(n) <?> logN

随机采样一个 python 集而不转换为列表

Randomly Sample a python Set without converting to list

python

random

set

问题

澄清编辑：