python - 如果 Ri > T 得到验证，则为每个元素 i 添加到列表 L 中的机会均等

Question

用下面的简单算法，如果测试if Ri > T:然后我们在 L 中得到或多或少 30 个元素，在 U 中得到 70 个元素，这没问题，因为 T 的值设置为 0.7。

现在，如果我想添加一个约束条件:除放入 L 的元素 i 是 Ri > T 的元素这一事实之外，我还希望 L 包含的内容不超过 B=20(即，我希望最后，当 i=n 时，L 的大小将或多或少 B=20)。

但问题是，如果我替换测试 if Ri > T:通过 if Ri > T and len(L) < B: ，那么放入 L 中的元素更有可能位于我们浏览的第一个元素 i 中(也就是说，例如元素 i = 87 永远不会有机会出现在 L 中)。但我希望从 i = 1 到 n 的所有元素都有平等的机会出现在 L 中(而不是只对第一个元素有利)。

注意:Ri > T的条件将元素放入 L 中，不应从我的代码中删除。这对我来说很重要:只有在时间 i $Ri$ 高于 T 的元素才允许在 L 中；并且 len(L) 不应超过 B(或多或少)。

import random

T = 0.7 # or any value T in ]0,1[
n = 100 # or any value n > B
B = 20 # or any value B < n

L = []
U = []

for i in range(1,n+1):
   xi = input("please give a new data x")
   Ri = 1. - random.random() # normally it is Ri = 1. - Proba(xi) depending on xi, but lets simplify using random() ...
   if Ri > T:
      Pay 1 euro and buy yi the label of xi
      L.append((xi, yi))
   else:
      U.append(xi)


print len(L), L
print
print len(U), U

Answer 1

我倾向于同意建议这没有尽可能详细说明的评论。不过，如果我没看错的话，你可以使用一种 reservoir sampling :

def some_accept(value_stream, p, max_num_to_accept):
    accepted = []
    passed = (v for v in value_stream if random.random() < p)
    for i, value in enumerate(passed):
        if len(accepted) < max_num_to_accept:
            accepted.append(value)
        else:
            replace_i = random.randint(0, i)
            if replace_i < max_num_to_accept:
                accepted[replace_i] = value
    return accepted

给出

>>> some_accept(range(100), 0.7, 10)
[34, 26, 30, 16, 22, 38, 32, 86, 33, 12]
>>> some_accept(range(100), 0.05, 10)
[16, 17, 83, 95]

现在，这可能会违反您关于 L 的“成本”条件，因为我们可能会“添加”超过 10 个元素，但我认为每次我替换一个元素时您d 必须还一枚硬币。

对频率分布的快速健全性检查看起来没问题(很容易出现差一错误导致偏差):

import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111)
for i in range(100):
    s = sum((Counter(some_accept(range(10), 0.25, 4)) for i in range(10**3)), Counter())
    x, y = zip(*sorted(s.items()))
    ax.plot(x,y)

plt.savefig("test.png")

给予