Как эффективно нарисовать ровно 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()
Есть предложения по улучшению алгоритма?
Редактировать: только что обнаружил, что эта проблема называется "отбор проб из пласта". В Википедии есть несколько хороших алгоритмов: https://en.wikipedia.org/wiki/Reservoir_sampling
3 ответа
Образец из ленивой последовательности:
points = [(i // sy, i % sy) for i in random.sample(xrange(sx*sy), n)]
random.sample выберет, следует ли материализовать последовательность и выполнить частичное перемешивание или выбрать случайные элементы и отслеживать выбранные индексы, основываясь на относительных размерах последовательности и выборки.
Обратите внимание, что это должно быть действительной последовательностью, а не итератором, чтобы это работало. Вопреки общему мнению, xrange (или Python 3 range) является фактической последовательностью. Генератор не будет работать здесь.
Если вы собираетесь рисовать так много точек, что заполняете экран, то вам, вероятно, не нужно составлять их список или помнить все те, которые вы нарисовали.
Вы хотите создать псевдослучайное, обратимое отображение между точками. Позвоните в карту E(x,y), Затем вы можете сгенерировать все точки (x,y) в строке развертки или в каком-то другом порядке, а затем для каждой точки (x,y), ты рисуешь E(x,y) на экране. Убедившись, что отображение обратимо, вы гарантируете, что каждый уникальный (x,y) карты на уникальный E(x,y)Таким образом, каждая точка, которую вы рисуете, будет отличаться.
Один из распространенных способов сделать такую функцию, как E(x,y) использовать структуру Фейстеля: https://en.wikipedia.org/wiki/Feistel_cipher
Это используется для создания множества криптографических шифров, таких как DES.
В вашем случае вы можете сделать это, начиная с хорошей целочисленной хеш-функции H(x)затем W = ширина экрана и H = высота экрана, и N = количество раундов, которые нужно использовать (подойдет 5ish), вы можете настроить свою функцию следующим образом (псевдокод, а не 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 (это псевдокод, поэтому я могу притворяться, что оператор модуля правильно работает с отрицательными числами).
Несмотря на то, что функция явно обратима, поскольку каждый шаг обратим, структура Фейстеля обеспечивает хорошее микширование, и ваши точки будут отображаться в хорошем псевдослучайном порядке, если вы используете хороший хэш H.
Что ж, вы можете рассмотреть точки выборки с минимальным расстоянием между ними, чтобы они не перекрывались. Образец диска Пуассона приходит на ум. Описание и код Python можно найти здесь: http://devmag.org.za/2009/05/03/poisson-disk-sampling/