logo标签列表

如何高效绘制屏幕上的N个点？

pythonalgorithm
5
这似乎是一个简单的问题，但我发现它很难做到性能好。
我想到的第一个算法是随机绘制点，从集合中检查它是否已经被绘制过，否则就绘制它。如果我们只绘制少量的点，这个算法效果很好，但当我们接近填充屏幕时，速度会急剧减慢。
我想到的最好的算法是构建像素列表，随机打乱并选择前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
1
乍一看，(x, y) for (x, y) in 似乎不是必须的。 - OneCricketeer
@cricket_007：好观点，这是初始版本中剩下的。我已经编辑了我的问题中的代码。 - static_rtti
3个回答
4

懒序列的示例：

points = [(i // sy, i % sy) for i in random.sample(xrange(sx*sy), n)]
random.sample函数根据序列和样本大小的相对大小，选择是否实例化序列并执行部分洗牌或选择随机元素并跟踪选定的索引。
请注意，为了使其工作，必须是实际的序列而不是迭代器。与常见的误解相反，xrange (或Python 3中的range)是实际的序列。生成器在此处无法工作。
太棒了！我曾尝试使用生成器，但我确信部分洗牌对于生成器来说没有意义。我没有想到在列表和生成器之间有一个折中方案。您将单维度的范围转换为二维范围的方法也非常好。 - static_rtti
2
如果你要画很多点，以至于屏幕被填满，那么你可能不想将它们列成列表或记住你已经画过的所有点。
你需要做的是创建一个伪随机、可逆的点映射。称之为E(x,y)。然后，您可以按扫描线或其他顺序生成所有点(x,y)，然后对于每个点(x,y)，在屏幕上绘制E(x,y)。通过确保映射是可逆的，您确保每个独特的(x,y)都映射到一个唯一的E(x,y)，因此您绘制的每个点都将是不同的。
制作类似E(x,y)这样的函数的常见方法是使用Feistel结构: https://en.wikipedia.org/wiki/Feistel_cipher 这被用来制作许多加密密码，如DES。
在您的情况下，您可以从一个好的整数哈希函数 H(x) 开始，然后给定 W = 屏幕宽度，H = 屏幕高度和 N = 要使用的轮数（大约为 5），您可以像这样制作您的函数（伪代码，不是 Python，抱歉）：
function E(x,y)
   for (i = 1 to N)
       x = (x+(H(y)%W)) % W;
       y = (y+(H(x)%H)) % H
   return (x,y)

请注意，每个步骤都很容易被反转。如果您想撤消y = (y+(H(x)%H)) % H，您只需执行y = (y-(H(x)%H)) % H（这是伪代码，所以我可以假装模数运算符在负数上正常工作）。
尽管该函数显然是可逆的，因为每个步骤都是可逆的，但Feistel结构提供了良好的混合，如果您使用良好的哈希H，则您的点将以漂亮的伪随机顺序出现。
谢谢，这看起来是一种有趣的方法。但它真的比被接受的答案更快吗？迭代映射函数看起来很消耗资源。 - static_rtti
主要的优势在于它使用了更少的内存。当跟踪所选索引时，它比接受的答案更快，但当它洗牌一个数组时可能会稍微慢一点...直到你处理几百万像素，然后由于缓存效应，它将再次变得更快。 - Matt Timmermans
在我看来，使用这个答案似乎每次都会得到相同的随机样本。没有明显的地方可以插入种子或密钥等内容。 - user2357112
1
@user2357112，如果您愿意，可以将密钥或种子混合到一个或多个哈希中，或者从不同的位置开始。 - Matt Timmermans
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接