如何在屏幕上有效地绘制N个点？

Question

这听起来像一个简单的问题,但我发现以良好的性能获得正确性令人惊讶.

我提出的第一个算法是随机绘制点,从集合中检查是否已经绘制,否则绘制它.如果我们绘制几个点但是当我们接近填充屏幕时灾难性地减慢,这可以正常工作.

我想出的最好的是构造像素列表,将其洗牌并选择第一个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()

有关更好算法的任何建议吗？

编辑:刚发现这个问题被称为"水库采样".维基百科有许多好的算法:https://en.wikipedia.org/wiki/Reservoir_sampling

Answer 1

来自惰性序列的样本：

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

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

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