Iterate list to map entries in Python

Question

I have two files, namely:

File1:

CL1 AA  XX  YY  ZZ  SS \n
CL2 3_b AA

File2:

AA  string1
AA  string2
3_b string3

My expected output is:

CL1 AA  string1
CL1 AA  string2
CL2 3_b string3
CL2 AA  string1
CL2 AA  string2

For this I wrote a following code:

import numpy as np
print("Reading Files...")
header = open('File1', 'r')
cl = header.readlines()
infile = np.genfromtxt('File2', dtype='str', skip_header=1)
new_array = []

for j in range(len(infile)):
    for row in cl:
        element = row.split("\t")
        ele_size = len(element)
        for i in range(0, ele_size):
            if np.core.defchararray.equal(infile[j,0], element[i]):
                clust = element[0]
                match1 = infile[j,0]
                match2 = infile[j,1]
                combo = "\t".join([clust, match1, match2])
                new_array.append(combo)

np.savetxt('output.txt',new_array, fmt='%s', delimiter='\t')

This generates the output I desire. But since the file has some 700000 lines in file2 and some 65000 clusters, it takes a huge time to iterate. Can anyone suggest an efficient way to parse it?

Is it possible to keep first file as a list and the second file as a dictionary, and then iterate over key values?

Answer 1

Your code does loop 700 000 multiplied by 65 000 multiplied by the number of elements in each cluster. That is a lot of iterations, and not very useful.

The better approach would be to read the smaller file into memory, and then read the larger file line by line. In addition as you iterate over each row in the smaller file, matching each of the keys, it makes sense to switch from a dict with cluster as key, and the different keys as values, to actually using the keys as keys, and list all the clusters it belongs to.

This approach would leave the lower memory footprint, but should be rather efficient to work with. Here is some code to start you off with. You might need to adjust a little related to splitting on space or tabs, but I get your wanted output using this.

from collections import defaultdict

def build_cluster_dict(filename):
    """Return a dict of keys with all the cluster the key exists in."""

    result = defaultdict(list)
    with open(filename) as infile:
        for line  in infile:
            elements = line.strip().split()

            cluster = elements[0]
            for key in elements[1:]:
                result[key].append(cluster)

    return result


def build_output(cluster_dict, filename, output_filename):

    with open(filename) as infile, open(output_filename, 'w') as outfile:
        for line in infile:
            key, text = line.strip().split()

            if key in cluster_dict:
                for cluster in cluster_dict[key]:
                    outfile.write('{}\t{}\t{}\n'.format(cluster, key, text))


def main():

    cluster_dict = build_cluster_dict("cluster.txt")

    print (cluster_dict)

    build_output(cluster_dict, "file2.txt", "output.txt")

if __name__ == '__main__':
    main()

Note that I've left out the use of numpy, as I don't see the need for it in this context. I've also used a double with statement to open both the in- and out-file at the same time in the same context. I left the print (cluster_dict) in there just to see the intermediate list it generates. For your test files this gave the following output (somewhat formatted):

defaultdict(<type 'list'>, 
            {'AA': ['CL1', 'CL2'], 
             'SS': ['CL1'], 
             'YY': ['CL1'], 
             'XX': ['CL1'],
             '3_b': ['CL2'],
             'ZZ': ['CL1']})

Addendum: Locate erroneous input line

In comments OP said their was a problem in the key, text line, and to detect this these lines:

       for line in infile:
           key, text = line.strip().split()

can be replaced with:

        for line_number, line in enumerate(infile):
            try:
                key, text = line.strip().split()
            except ValueError:
                print("Error on line {}: {}".format(line_number, line))
                ## Option a) Use empty text
                #key = line.strip()
                #text = ""
                # Option b) Continue with next line
                continue

This code will catch the error situation, and as it stands it will display an error message with the offending line. I've set it to use option b), that is continue with next line. If you want to use an empty string and write the output to file file, uncomment option a), and comment out option b).

Answer 2

Yes, I do not know why you are using numpy for file reading this way.

These loops are very inefficient. Though I am sure there are more efficient ways than this, here is something try that will hopefully cut down a lot of your time.

The current way you are looping if there is 700,000 lines in one file and 65,000 in the other then you are looking at 65,000 ^ 700,000 iterations! Where as this way you will get 700,000 + 65,000 iterations.

First note, reading the entire file into a list is not that efficient, a file object has an iterator that will iterate each line and is much more Pythonic.

file2Dict = {}
with open('File2') as file2:
    for line in file2:
        line_split = line.split()
        file2Dict.setdefault(line_split[0], []).append(line_split[1])

with open('File1') as file1:
    with open('output', 'w') as outputFile:
        for line in file1:
            line_split = line.split()
            first = line_split[0]
            # start at second position
            for item in line_split[1:]:
                try:
                    match = file2Dict[item]
                except KeyError:
                     continue # error?
                out_lines = ['%s\t%s\t%s' % (first, item, m) for m in match]
                outputFile.write('\n'.join(out_lines))

using the 'with' context is safer to make sure your files are closed if there is an error. Notice that I am working with one line at a time and consumes less memory. I am sure there are other ways using text parsing libraries and other custom file readers, but this is something quick and i haven't tested it but should describe the flow.

Note, split() by defaults spits white space including tabs. Much safer if you change from tabs to spaces later

Also you should think what would happen if there is some data missing and they can't be matched up. Should it error or just continue? See the try except block.