如何有效地在屏幕上精确绘制N个点？ [英] How to efficiently draw exactly N points on screen?

问题描述

这听起来像是一个简单的问题，但我发现要获得良好的性能就很难了。

This sounds like an easy question, but I find it surprisingly tricky to get right with good performance.

我想到的第一个算法是绘制随机点，从集合中检查是否已绘制，否则绘制。如果我们只画几个点，这很好用，但是当我们接近填充屏幕时，它会灾难性地减慢速度。

The first algorithm I've come up with is to draw points randomly, check from a set if it's already been drawn, and draw it otherwise. This works fine if we are drawing few points but slows down catastrophically as we approach filling the screen.

我想到的最好的方法是构建像素列表，随机播放然后选择第一个n（为此我使用了python的random.sample）。它的效果更好，但仍然有点慢，因为需要在内存中构造整个像素列表，这在绘制5点时非常过分。这是我的python代码：

The best I came up with is to construct the list of pixels, shuffle it and pick the first n (I used python's random.sample for that). It works better, but is still a bit slow because the whole list of pixels needs to be constructed in memory, which is horribly overkill when drawing 5 points. Here's my python code:

#!/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()

任何建议更好的算法？

编辑：刚发现此问题称为储层采样。 Wikipedia有许多好的算法： https://en.wikipedia.org/wiki/Reservoir_sampling

Just found out this problem is called "reservoir sampling". Wikipedia has a number of good algorithms: https://en.wikipedia.org/wiki/Reservoir_sampling

推荐答案

从惰性序列中抽取的样本：

Sample from a lazy sequence:

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

random.sample 将选择是实现序列并执行部分混洗还是选择随机元素并跟踪所选索引

random.sample will choose whether to materialize the sequence and perform a partial shuffle or pick random elements and track selected indices, based on the relative sizes of the sequence and sample.

请注意，它确实必须是实际的序列，而不是迭代器，为此工作。与通常的看法相反， xrange （或Python 3 range ）是实际序列。发电机无法在这里工作。

Note that it does have to be an actual sequence, rather than an iterator, for this to work. Contrary to common belief, xrange (or Python 3 range) is an actual sequence. A generator wouldn't work here.

这篇关于如何有效地在屏幕上精确绘制N个点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！