2
\$\begingroup\$

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
    #The "blockheader" in Bitcoin terms
    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
    results = s.run_server(password="changeme")

    #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)
\$\endgroup\$
  • \$\begingroup\$ Have you tried using xrange() instead of range() for the loops inside mapfn? \$\endgroup\$ – alexwlchan Mar 23 '14 at 23:42
  • \$\begingroup\$ 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. \$\endgroup\$ – KDecker Mar 24 '14 at 1:02
  • \$\begingroup\$ Huh, interesting. Not a speed related note, but what’s the argument k to mapfn? It doesn’t seem to be used anywhere. \$\endgroup\$ – alexwlchan Mar 24 '14 at 1:07
  • \$\begingroup\$ 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. \$\endgroup\$ – KDecker Mar 24 '14 at 1:42
  • 1
    \$\begingroup\$ why don't you move import md5 out of the function? \$\endgroup\$ – m.wasowski Mar 24 '14 at 3:08
2
\$\begingroup\$

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().

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.