Speeding up script for processing three huge files

Question

I have three huge files I need to process in order to rearrange the data contained within.

The first file is a list of English example sentences (468,785 lines long). A typical line from this file looks like this:

120033#eng#Creativity is an important aspect for the development of human.

The second file is a list which tells me the ID of the equivalent sentences (7,243,419 lines) in the third file. A typical line from the second file looks like this:

1#77

This tells me that the English sentence with ID "1" in the first file matches a translation with ID "77" in the third file.

The third file contains a list of the translated sentences (2,945,676 lines). A typical line from this file looks like this:

1#cmn#我們試試看！

Here is the script I am using to get each line from file one, find which sentences it links to in file 2 and then get the matching sentence from file 3:

with open("eng_lines.txt") as f:
    eng_lines = f.readlines()
with open("all_lines.txt") as f:
    all_lines = f.readlines()
with open("all_links.txt") as f:
    all_links = f.readlines()
for ln,line in enumerate(eng_lines):
    print ln,len(eng_lines)
    with open("matches.txt", "a") as matches:
        matches.write(line+"\n")
        hash = line.index("#")
        sentence_idA = line[:hash]
        for line2 in all_links:
            hash = line2.index("#")
            link_a = line2[:hash]
            link_b = line2[hash+1:].strip()
            if (link_a==sentence_idA):
                for line3 in all_lines:
                    hash = line3.index("#")
                    sentence_idB = line3[:hash]
                    if (sentence_idB==link_b):
                        matches.write(line3+"\n")

This process is going to take a LONG time (about a year given that each iteration is currently taking about a minute to process on my i7 PC).

Answer 1

A major problem with your code is that you're doing very long linear searches to find matches-- worse, you're doing those in a nested fashion.

Instead, you should take advantage of Python dictionaries, which have very fast lookups. Something like this:

---

def read_sentences(filename):
    with open(filename) as fp:
        data = {line[:line.index("#")]: line for line in fp}
    return data

eng_lines = read_sentences("eng_lines.txt")
all_lines = read_sentences("all_lines.txt")

with open("all_links.txt") as fp:
    all_links = dict(line.rstrip().split("#") for line in fp)

with open("matches2.txt", "w") as fp_matches:
    for idcode in sorted(eng_lines, key=int):
        print "working on", idcode
        if idcode in all_links:
            fp_matches.write(eng_lines[idcode] + "\n")
            fp_matches.write(all_lines[all_links[idcode]] + "\n")
        else:
            print "warning: could not match eng_line", idcode

---

builds dictionaries for both eng_lines and all_lines, using the id as the key and the line as the value. It also builds a dictionary all_links to store the connection between the id values in eng_lines and all_lines. On some test data I mocked up, it produces a file looking like yours:

1#eng#This is example sentence number 1

995072#cmn#This should really be in Mandarin 995072

2#eng#This is example sentence number 2

1732074#cmn#This should really be in Mandarin 1732074

in about ten to twenty seconds on a dataset of your size.

Answer 2

The problem is all those nested for-loops, combined with repeated expensive operations such as opening the matches file and parsing the same text repeatedly.

The main improvement will come by replacing your nested for loops with an efficient lookup using a dict. Both your second and third files require lookup using the ID numbers as keys. You should read them just once during startup, and store all the key:value mappings in dictionaries. If you have multiple values with the same key (it seems like you may in the second file), you can consider using a defaultdict(list) meaning a dictionary where the values are always lists which can be appended to even if they don't exist yet. So for example:

links = defaultdict(list)
with open("all_links.txt") as f:
    for line in f:
        eng, other = line.split('#')
        links[eng].append(other)

Then you have a mapping where you can look up an ID from the first file and directly and efficiently get all the IDs to look for the in the third file. A similar technique can be used with the third file as well.

Answer 3

I'm not sure what's on those files, but it seems that you are trying to generate all permutations of something. Generally, this is extremely slow by nature and only naive algorithms attempt to do so. Like @Smac89 mentioned in the comments, reading matches.txt outside the loop should help, but honestly I don't think it will help much. You problem is in your algorithm, by generating such an enormous amount of permutations, and not specifically in your I/O methodology.

In case you are not familiar with it, I recommend reading a bit about asymptotic analysis, perhaps starting with the more specific subject of asymptotic notation. With this kind of analysis you can usually infer whether a given algorithm, for any given input, can respond in what is usually called "useful time" - that is, not take an year - which, in your case, it seems it can't.

Answer 4

Avoid print if you don't need it, print requires a lot of time (compared to 'basic' operations). If you want to save the result, use a file.

Do not open the matches.txt file in the loop, totally useless

Use the concurrent execution (multiprocessing package) to take advantage of your I7 (can be very difficult, probably not the best solution if you don't know how to do)

Take a look at Python Time Complexity and choose the appropriate data structure (dict can be interesting if the following can be applied)

If there is only one translation (so the ID is used only one time in each files) :

1. You can remove the lines (in the link file and the translation file) after founding the translated sentence. The next searches will be faster because the program will only search in the useful sentences
2. Stop directly after finding the good sentence

Eventually (if the program is not enough fast) use a JIT compiler like Pypy