two lists, faster comparison in python

Question

I'm writting python (2.7) script to compare two lists. These lists are created from files by reading their content. Files are just text files, no binary. File 1 contains only hashes (MD5 sum of some plaintext word), File 2 is hash:plain. Lists have different length (logicaly, I can have less 'cracked' entries than hashes) and both can't be sorted as I have to preserve order, but this is a next step of what I'm trying to achieve. So far my simple code looks like that:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import os

def ifexists(fname):
    if not os.path.isfile(fname):
        print('[-] %s must exist' % fname)
        sys.exit(1)

if len(sys.argv) < 2:
    print('[-] please provide CRACKED and HASHES files')
    sys.exit(1)

CRACKED=sys.argv[1]
HASHES=sys.argv[2]

sk_ifexists(CRACKED)
sk_ifexists(HASHES)

with open(CRACKED) as cracked, open(HASHES) as hashes:
    hashdata=hashes.readlines()
    crackdata=cracked.readlines()
    for c in crackdata:
        for z in hashdata:
            if c.strip().split(':', 1)[0] in z:
                print('found: ', c.strip().split(':', 1))

Basically, I have to replace hash found in HASHES list with matching line hash:plain found in CRACKED list. I'm iterating through CRACKED as it will be shorter every time. So my problem is that above code is very slow for longer lists. For example processing two text files with 60k lines is taking up to 15 minutes. What would be your suggestion to speed it up?

Answer 1

Store one of these files in a dictionary or set; that takes out a full loop and lookups are O(1) constant time on average.

For example, it looks like the crackdata file can easily be converted to a dictionary:

with open(CRACKED) as crackedfile:
    cracked = dict(map(str.strip, line.split(':')) for line in crackedfile if ':' in line)

and now you only have to loop over the other file once:

with open(HASHES) as hashes:
    for line in hashes:
        hash = line.strip()
        if hash in cracked:
            print('Found:', hash, 'which maps to', cracked[hash])