collision.py

import random
import itertools


def find_collision(rng):
    d = {}
    for iteration in itertools.count():
        nonce = rng()
        if nonce in d:
            return iteration
        d[nonce] = True
        if iteration % 1000000 == 0:
            print 'Nothing after %s' % (iteration,)


def avg_collision(rng, times):
    collisions = []
    min_collision = 100000000000000000000000
    max_collision = 0
    for _ in xrange(times):
        collision = find_collision(rng)
        min_collision = min(collision, min_collision)
        max_collision = max(collision, max_collision)
        print 'Collision at %d' % (collision,)
        collisions.append(collision)
    return sum(collisions)/len(collisions), min_collision, max_collision


if __name__ == '__main__':
    print 'Current method'
    avg_collision, min_collision, max_collision = avg_collision(lambda: random.randint(0, 100000000), 1000)
    print 'Collisions: avg %d, min %d, max %d' % (avg_collision, min_collision, max_collision)
    print 'Proposed method'
    avg_collision, min_collision, max_collision = avg_collision(lambda: ''.join(random.choice('abcdefghijklmnopqrstuvwxyz234567') for _ in xrange(10)), 3)
    print 'Collisions: avg %d, min %d, max %d' % (avg_collision, min_collision, max_collision)