python - 在不转换为列表的情况下随机采样 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 必须是在每次采样时转换为一个列表，该算法将极大地影响性能。

那么对于如何使用集合有效地执行此操作，有没有人有任何建议或想法？我感谢任何关于此事的意见，在任何人跳到“过早优化”例程之前，我非常清楚这将要执行的规模以及 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)，但这些都不重要。

Answer 1

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

import random, heapq

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

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