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

Answer 1

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.