Um random.sample rápido
No post sobre a simulação do totoloto utilizei a função sample do módulo random para sortear um conjunto de elementos. O módulo random tem uma outra função geradora de números inteiros interessante, a getrandbits. Esta função é bastante mais rápida que randint e ambas acabam por ser utilizadas na função sample. Assim pus-me a pensar se poderia ser possível escrever uma função mais rápida com uma abordagem simples. A primeira tentativa foi a seguinte:
from random import getrandbits
from math import log2, ceil
def better_sample(n, k):
if k>n:
return {}
out = set()
nbits = ceil(log2(n))
for i in range(k):
c = getrandbits(nbits)
while c in out or c >= n:
c = getrandbits(nbits)
out.add(c)
return out
Os primeiros testes revelam um ganho de desempenho significativo (metade do tempo gasto), pelo que será algo a explorar noutras aplicações. As função não é exatamente equivalente, mas o princípio pretendido é válido.