2

I've got a list like

listOfLists = [['key2', 1], ['key1', 2], ['key2', 2], ['key1', 1]]

The first item of an inner list is the key. The second item of an inner list is the value.

I want to get an output [['key1', 1], ['key2', 1]] which gives the list that its value is the smallest of the lists that has the same key and the output group by the key (my English is poor so just use the concept of Sql Syntax)

I've written some code like this:

listOfLists = [['key2', 1], ['key1', 2], ['key2', 2], ['key1', 1]]
listOfLists.sort()    #this will sort by key, and then ascending by value
output = []
for index, l in enumerate(listOfLists):
    if index == 0:
        output.append(l)
    if l[0] == listOfLists[index - 1][0]:
        #has the same key, and the value is larger, discard
        continue
    else:
        output.append(l)

this seems not smart enough is there any simpler way to do this work?

3 Answers 3

5

How about using a dictionary (no need to sort the data)?

>>> listOfLists = [['key2', 1], ['key1', 2], ['key2', 2], ['key1', 1]]
>>> d = {}
>>> for k,v in listOfLists:
    d.setdefault(k, []).append(v)

>>> d = {k:min(v) for k,v in d.items()}
>>> d
{'key2': 1, 'key1': 1}

You can convert to a list if you want

3
  • Good answer - +1. Alternately you could use collections.defaultdict to simplify a little bit more :-) Sep 19, 2012 at 1:47
  • @SeanVieira I don't like to use defaultdict for simple cases because it may confuse beginners by not raising KeyError when used as a normal dict... But, of course, the syntax is better
    – JBernardo
    Sep 19, 2012 at 1:52
  • the solution is good but python2.6 doesn't support dictionary comprehensions Sep 19, 2012 at 3:22
3

O(N log N) solution

You can just use the dict constructor for this. It is O(N log N) because of the sorting step

>>> dict(sorted(listOfLists, reverse=True))
{'key2': 1, 'key1': 1}

To see why this works, look at the result of sorted

>>> sorted(listOfLists, reverse=True)
[['key2', 2], ['key2', 1], ['key1', 2], ['key1', 1]]

The dict constructor will replace each key as it traverses the list and sorted has pushed the minimum for each key to the end of the sublist for that key

O(N) solution

>>> d = {}
>>> for k, v in listOfLists:
...  d[k] = min(d.get(k, v), v)
... 
>>> d
{'key2': 1, 'key1': 1}
2
  • You can avoid one dictionary lookup with d[k] = min(d.get(k, inf), v) where inf = float('inf'). But it would probably be less readable (and would not work for things other then numbers).
    – JBernardo
    Sep 19, 2012 at 4:05
  • @JBernardo, Good idea. min(d.get(k, v), v) works perfectly well too Sep 19, 2012 at 4:07
2

The itertools module has a very useful groupby function that is probably exactly what you need:

from itertools import groupby

listOfLists.sort()

for key, subgroup in groupby(listOfLists, lambda item: item[0]):
    print key, min(subgroup)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.