# MapReduce program for finding low value hashes

For class we were to make a MapReduce program in Python to find low value hashes of our name. I have completed the assignment but want to try and speed it up. The program currently takes about 45s to complete. I would like to see if there are any suggestions on speeding it up some.

The requirements are to find hashes of your name with 5 leading 0's when printed in hex. We are to try 40 million nonces. I did a few naive implementations before I finally settled on what is below. What I do is send a dict of 40 consecutive numbers to use as multipliers in the Map function. The multiplier represents the range of millions to go through. So when mult = 0 I will use the nonces 0-1mil, when mult = 23 use the nonces 23mil-24mil.

#!/usr/bin/env python
import mincemeat

def mapfn(k, v):
#Hash the string with the given nonce, if its good save it
import md5
#Create a md5 hash and fill it with out initial value
m = md5.new()
m.update("Kevin")
#Now, step through 1 million nonces with v as a multiplier
for i in range(v*1000000, ((v+1)*1000000), 1):
mPrime = m.copy()
mPrime.update(str(i))
hashOut = mPrime.hexdigest()
if(hashOut[:5] == '0' * 5):
yield hashOut, i
else:
pass #Hash trash!

def reducefn(k, vs):
return (k, vs)

if __name__ == "__main__":
#Import some useful code
import sys
import collections

#Build the data source, just a list 0-39
nonces = [i for i in range(0, 40)]
datasource = dict(enumerate(nonces))

#Setup the MapReduce server
s = mincemeat.Server()
s.mapfn = mapfn
s.reducefn = reducefn
s.datasource = datasource

#Get the results of the MapReduce

#List the good hashes
print "\nHashed on the string: Kevin\nResults..."
for i in range(0, len(results)):
key, value = results.popitem()
hashStr, nonce = value
print "Nonce: " + str(nonce[0]) + ", hash: " + str(hashStr)

• Have you tried using xrange() instead of range() for the loops inside mapfn? – alexwlchan Mar 23 '14 at 23:42
• I've done that, along with removing the ,1 from it too. It didn't reduce the time, it actually increased it by .2s. I will wait for @Josay to finish his question and see what else he has in mind. – KDecker Mar 24 '14 at 1:02
• Huh, interesting. Not a speed related note, but what’s the argument k to mapfn? It doesn’t seem to be used anywhere. – alexwlchan Mar 24 '14 at 1:07
• k and v are key and value pairs from the data source. For this program, the same value. The data source is a dict that looks like [0: 0, 1: 1 ...etc]. But say for a MapReduce that counts the word frequency of a text k would still be an index and v might be a single word or line in the text. – KDecker Mar 24 '14 at 1:42
• why don't you move import md5 out of the function? – m.wasowski Mar 24 '14 at 3:08

From PEP 8 :

Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants.

Edit : Ok, from your comment, it seems like this is a requirement for mincemeat.

The default value for the third argument of range is 1 so you don't need to provide it.

You shouldn't use magic numbers. Especially when they have so many digits and are so tedious to read/compare.

It makes the following snippet a bit awkward:

for i in range(v*1000000, ((v+1)*1000000), 1):


Just trying to understand how many iterations there will be is a bit of a pain. I'd much rather read :

nb_nounces = 1000000
for i in range(v*nb_nounces, (v+1)*nb_nounces):


There is no point in having :

    else:
pass


nonces = [i for i in range(0, 40)]
datasource = dict(enumerate(nonces))
s.datasource = datasource


can be much more concisely written :

s.datasource = {i:i for i in xrange(40)}


using dict comprehension and xrange.

for i in range(0, len(container)): is usually an antipattern in Python. This usually corresponds to something that can be written with straight-forward iteration. In your case, I guess (but I haven't tested), you could just do : for key,value in results.iteritems().

• Do you mean make my hard coded values of 40 and 1mil into constants? en.wikipedia.org/wiki/Magic_number_(programming) – KDecker Mar 24 '14 at 0:47