Fastest way to count combinations of values from two lists/arrays

Question

I have a file with mostly 0 and 1. For each line I would like to compare it against all others (without the redundancy) and count the different combinations. It is slightly more complicated as there are also "N" in the matrix when there is missing data. For example if the two lines are:

line1 = "0 0 1 0 1"
line2 = "0 1 1 0 1"

Then I would like to create a two by two table like this:

    0   1 
 0| 2 | 1 |
 1| 0 | 2 |

At the moment I am doing something like this:

line1_list = line1.split()
line2_list = line2.split()

To get the counts I have tried two options. The first if using a for loop:

tab_dict = defaultdict(int)
for i in xrange(0,len(line1_list)):
    key = line1_list[i]+"-"+line2_list[i]
    tab_dict[key] += 1

And the second is using a combination of map and zip:

tab_dict = Counter(map(lambda x:x[0]+"-"+x[1],zip(line1_list,line2_list)))

The first option seems to be the fastest but I was wondering if there is a faster way because the matrix I have is very big and it will take a long time to run. I have tried to look for libraries to do this but have not found anything yet.

Answer 1

I would drop construction of string and just do:

from itertools import izip

line1 = "0 0 1 0 1"
line2 = "0 1 1 0 1"

line1_list = line1.split()
line2_list = line2.split()

tab_dict = Counter(izip(line1_list, line2_list))

construction of tuple if faster than string, you remove unneeded operation, and making a table from a tuple of two if pretty much the same as making it from a complex string key, I would say that making it out of tuple of (x,y) is more logical.

Answer 2

Whenever you do string addition, you should ask yourself if it is really necessary, because Python has to allocate a new string whenever you do that (which means in your case, one new string with x[0]+"-", then another new string for (x[0]+"-")+x[1], which can then be saved. Usually you would remedy this by accumulating the values in a list (which does not have this problem because it is mutable) and then str.join them at the end.

So, at least get rid of the separator to speed things up a bit. It will not hurt you, since your values are only 1 and 0, so no disambiguation between e.g. 12-1 and 1-21 is needed (right?).

I would propose a mix of your two methods, for readability:

from collections import Counter
from itertools import izip

def get_combinations(list_1, list_2):
    for t in izip(list_1, list_2):
        yield "".join(t)

line1 = "0 0 1 0 1"
line2 = "0 1 1 0 1"

line1_list = line1.split()
line2_list = line2.split()

tab_dict = Counter(get_combinations(line1_list, line2_list))

This uses a generator to replace your lambda and uses str.join instead of string addition.

You could also have a look if line1.replace(" ", "") is faster than line1.split, because this function only needs an iterable so it can directly deal with a string:

from collections import Counter
from itertools import izip

def get_combinations(list_1, list_2):
    for t in izip(list_1, list_2):
        yield "".join(t)

line1 = "0 0 1 0 1"
line2 = "0 1 1 0 1"

line1_list = line1.replace(" ", "")
line2_list = line2.replace(" ", "")

tab_dict = Counter(get_combinations(line1_list, line2_list))

Alternatively, you can leave out the str.replace and just del tab_dict[" "] at the end:

from collections import Counter
from itertools import izip

def get_combinations(list_1, list_2):
    for t in izip(list_1, list_2):
        yield "".join(t)

line1 = "0 0 1 0 1"
line2 = "0 1 1 0 1"

tab_dict = Counter(get_combinations(line1_list, line2_list))
del tab_dict["  "]