Skip to content

Instantly share code, notes, and snippets.

@mmalone

mmalone/collision.py

Created April 24, 2010 22:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mmalone/378010 to your computer and use it in GitHub Desktop.
Save mmalone/378010 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment