How to efficiently draw exactly N points on screen?

Question

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

@cricket_007 : good point, this was a leftover from an initial version. I've edited the code in my question. — static_rtti, Apr 02 '16 at 22:01

score 4 · Accepted Answer · answered Apr 02 '16 at 21:59

4

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.

answered Apr 02 '16 at 21:59

user2357112

260,549
28
431
505

Wonderful! I tried with a generator, but that I convinced myself that a partial shuffle didn't make sense for a generator. I didn't figure out there was a middle ground between a list and a generator. Your way of making a 2D range for a single dimensional one is also very nice. – static_rtti Apr 02 '16 at 22:03

score 2 · Answer 2 · answered Apr 02 '16 at 22:27

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.

Thanks, this looks like an interesting approach. Is it really faster than the accepted answer, though? The iterative mapping function looks expensive. — static_rtti, Apr 02 '16 at 22:57
The primary advantage is that it uses a whole lot less memory. It would be faster than the accepted answer when it track selected indices, but maybe a wee bit slower when it shuffles an array... until you get over a few million pixels and then it will be faster again, due to cache effects — Matt Timmermans, Apr 02 '16 at 23:57
It seems to me like with this answer, you'd just get the same random sample every time. There's no obvious place you'd plug in a seed or a key or anything. — user2357112, Apr 03 '16 at 09:36
@user2357112, You can mix a key or seed into one or more of the hashes if you like, or just start in a different place — Matt Timmermans, Apr 04 '16 at 11:45

score 0 · Answer 3 · answered Apr 02 '16 at 22:48

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/

How to efficiently draw exactly N points on screen?

3 Answers3

Linked