python - random.sample 的时间复杂度

Question

在另一个线程中，我看到二叉堆加权随机样本的时间复杂度等于 O(n * log(m))，其中 n 是选择数，m 是可供选择的节点数。

我想知道 Python 将其用作 random.sample 的未加权随机样本的时间复杂度。时间复杂度是简单的 O(n) 还是完全不同？

Answer 1

Python 源代码:random.py (第 267 行)。

这里是相关的部分:

   315             selected = set()
   316             selected_add = selected.add
   317             for i in range(k):
   318                 j = randbelow(n)
   319                 while j in selected:
   320                     j = randbelow(n)
   321                 selected_add(j)
   322                 result[i] = population[j]

它基本上是“掷骰子”随机索引到population。如果它得到一个已经在集合 selected 中的索引，它会重新滚动。冲洗、起泡并重复 k 次(其中 k 是您要求的 sample 数。)

请求的样本数量似乎是 O(n)。有一些针对小集的优化，但重点是上面的主循环。

---

编辑:

我相信第 305-313 行是一个特例，当请求的样本数量 k 占总人口 n 的很大一部分时。我们不是从整个种群中随机选择元素(如果我们与已经选择的元素发生碰撞则重新滚动)，而是明确维护一个我们尚未选择的元素列表。我们保证每次都能获得一个新元素，但代价是我们必须维护列表。

如果我的解释有误，请随时在下方发表评论。

   303         result = [None] * k
   304         setsize = 21        # size of a small set minus size of an empty list
   305         if k > 5:
   306             setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
   307         if n <= setsize:
   308             # An n-length list is smaller than a k-length set
   309             pool = list(population)
   310             for i in range(k):         # invariant:  non-selected at [0,n-i)
   311                 j = randbelow(n-i)
   312                 result[i] = pool[j]
   313                 pool[j] = pool[n-i-1]   # move non-selected item into vacancy
   314         else:
   315             selected = set()
   316             selected_add = selected.add
   317             for i in range(k):
   318                 j = randbelow(n)
   319                 while j in selected:
   320                     j = randbelow(n)
   321                 selected_add(j)
   322                 result[i] = population[j]
   323         return result