Memory efficiency benchmark

sample.py

import sys
import random
import math


def sample1(randbelow, n, k):
    # Array-based shuffle algorithm (used by Python)
    pool = list(range(n))
    for i in range(n, n-k, -1):
        j = randbelow(i)
        yield pool[j]
        pool[j] = pool[i-1]
    global size
    size = sys.getsizeof(pool)
    # BLUE

def sample3(randbelow, n, k):
    # The same, but with a hashtable: only `pool[i] != i` are stored
    pool = {}
    for i in range(n, n-k, -1):
        j = randbelow(i)
        yield pool.get(j, j)
        pool[j] = pool.get(i-1, i-1)
    global size
    size = sys.getsizeof(pool)
    # RED

def sample2(randbelow, n, k):
    # Simple random sample (used by Python)
    selected = set()
    for i in range(k):
        j = randbelow(n)
        while j in selected:
            j = randbelow(n)
        selected.add(j)
        yield j
    global size
    size = sys.getsizeof(selected)
    # GREEN


from PyQt5.QtGui import QImage

mn = 100000
m = 1.25
sz = int(math.log(mn, m))

img = QImage(sz, sz, QImage.Format_ARGB32)
img.fill(0)

n = 2
y = 0
while n <= mn:
    print(round(n))
    k = 2
    x = 0
    while k <= n:
        sizes = []
        for i, f in enumerate([sample1, sample2, sample3]):
            s = list(f(random.Random(4562456227).randrange, round(n), round(k)))
            #assert round(k) == len(s) == len(set(s))
            sizes.append((size, i))
        sizes.sort()
        c1 = min(255, round((1 - sizes[0][0]/sizes[1][0])*256*4))
        c2 = min(255, round((1 - sizes[1][0]/sizes[2][0])*256*1))
        c1 <<= (0, 8, 16)[sizes[0][1]]
        c2 <<= (0, 8, 16)[sizes[1][1]]
        if k > n/5:
            c1 = c2 = 0
        img.setPixel(x, sz-1-y, c1+c2+0xff000000)
        k *= m
        x += 1
    y += 1
    n *= m

img.save('out.png')