Find and process duplicates in list of lists

Question

I'm trying to merge counts for items (URLs) in the list:

[['foo',1], ['bar',3],['foo',4]]

I came up with a function, but it's slow when I run it with 50k entries. I'd appreciate if somebody could please review and suggest improvements.

def dedupe(data):
    ''' Finds duplicates in data and merges the counts '''
    result = []
    for row in data:
        url, count = row
        url_already_in_result = filter(lambda res_row: res_row[0] == url, result)
        if url_already_in_result:
            url_already_in_result[0][1] += count
        else:
            result.append(row)
    return result


def test_dedupe():
    data = [['foo',1], ['bar',3],['foo',4]]
    assert dedupe(data) == [['foo',5], ['bar',3]]

Answer 1

It looks like you could use collections.Counter. Although you may want to use it earlier in your code, when you create the list of pairs you pass to dedupe. As is, you could use the following in your code:

from collections import Counter

def dedupe(data):
    result = Counter()
    for row in data:
        result.update(dict([row]))
    return result.items()

>>> data = [['foo',1], ['bar',3],['foo',4]]
>>> dedupe(data)
[('foo', 5), ('bar', 3)]

Answer 2

Let's assume your list of lists is like this :

a = [[1,1], [2,2], [1,4], [2,3], [1,4]]
import itertools
#you can loop through all the lists and count as :
b = a
b.sort()
b = list(b for b,_ in itertools.groupby(b)) #removing duplicates
total = len(b) #counting total unique elements
for i in range(total):
    b[i].insert(3, a.count(b[i])) #count repetitions and inserting in list

The counts of elements would be inserted in the index 3 of respective lists.

Answer 3

Your main problem is lookups in data structure unfit for this case (list).

To find out count for foo you have to do O(n) operations. You are doing this for every entry in data so you'll have a lot of operations going on.

Instead, you should use data structure with faster lookups. In Python, it would be dict or its derivatives.

You could use collections.defaultdict with 0 as a default value so you don't have to check if your foo is in the dict already or not - you simply increment result['foo'].

In fact, this use case is so common that collections.Counter implements it and some more things, so you should probably get yourself familiar with it.

So, root of your problem is inappropriate data structure. Speaking of Python, you'd better use dict for your result instead of list - that will give you performance you need - and using Counter instead of raw dict will make things more readable and also DRY.