如何高效地在屏幕上精确绘制N个点？

这听起来是一个简单的问题，但我发现要获得良好的性能是非常棘手的。

我提出的第一个算法是随机绘制点，从一组中检查是否已绘制，否则绘制。如果我们只绘制几个点，那么这种方法效果很好，但当我们接近填满屏幕时，速度会灾难性地减慢。

我想出的最好的方法是构建像素列表，对其进行洗牌并选择第一个 n （我为此使用了 python 的 random.sample ）。它效果更好，但仍然有点慢，因为整个像素列表需要在内存中构建，这在绘制 5 个点时是非常过大的。这是我的Python代码：

#!/usr/bin/env python
""" drawn n random points on the screen """
import pygame
from pygame.locals import *
import sys
import random
from itertools import product

n = int(sys.argv[1])
s = pygame.display.set_mode()
sx, sy = s.get_size()

points = random.sample(list(product(range(sx), range(sy))), n)

for p in points:
    s.fill((255, 255, 255), pygame.Rect(*p, 1, 1))
pygame.display.flip()
while True:
    for event in pygame.event.get():
        if event.type == QUIT or event.type == KEYDOWN:
            sys.exit()

对于更好的算法有什么建议吗？

Edit:刚刚发现这个问题叫“油藏采样”。维基百科有很多很好的算法：https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling

来自惰性序列的样本：

points = [(i // sy, i % sy) for i in random.sample(xrange(sx*sy), n)]

random.sample将根据序列和样本的相对大小选择是否具体化序列并执行部分洗牌或选择随机元素并跟踪选定的索引。

请注意，它必须是实际的sequence，而不是迭代器，才能使其工作。与普遍看法相反，xrange（或Python 3range) 是一个实际的序列。发电机在这里不起作用。