CODEWITHSUNDEEP
pythonalgorithm
static_rtti
static_rtti

Reputation: 56242

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.

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()

Any suggestions for a better algorithm?

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

Upvotes: 5

Views: 376

Answers (3)

Severin Pappadeux
Severin Pappadeux

Reputation: 20080

Well, you might want to consider sampling points with minimum distance between them, thus making them non-overlapping. Poisson disc sampling comes to mind. Description and Python code could be found here: http://devmag.org.za/2009/05/03/poisson-disk-sampling/

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59144

If you're going to be drawing so many points that you fill up the screen, then you probably don't want to make a list of them or remember all the ones you've drawn.

What you want to do is create a pseudo-random, invertible mapping between points. Call the mapping E(x,y). Then, you can generate all the points (x,y) in scan-line or some other order, and then for every point (x,y), you draw E(x,y) on screen. By making sure that the mapping is invertible, you ensure that every unique (x,y) maps onto a unique E(x,y), so every point you draw will be distinct.

One common way to make a function like E(x,y) is to use a Feistel structure: https://en.wikipedia.org/wiki/Feistel_cipher

This is used to make a lot of cryptographic ciphers like DES.

In your case, you can do this starting with a good integer hash function H(x), then given W = the screen width and H = the screen height, and N = the number of rounds to use (5ish will do), you can make your function like this (pseudocode, not python, sorry):

function E(x,y)
   for (i = 1 to N)
       x = (x+(H(y)%W)) % W;
       y = (y+(H(x)%H)) % H
   return (x,y)

Note that each step is easily invertible. If you want to undo y = (y+(H(x)%H)) % H, you can just do y = (y-(H(x)%H)) % H (this is pseudocode, so I can pretend the modulus operator works properly with negative numbers).

Even though the function is obviously invertible, because each step is invertible, the Feistel structure provides good mixing and your points will come out in a nice pseudorandom order if you use a good hash H.

Upvotes: 2

user2357112
user2357112

Reputation: 280291

Sample from a lazy sequence:

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

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.

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.

Upvotes: 4

Related Questions