CODEWITHSUNDEEP
pythonperformancelist
Ben Longo
Ben Longo

Reputation: 171

Best way to find minimum x and y values in a list of pairs in python?

Given a list of data:

[[0, 0], [1, 0], [0, 1], [-1, 0], [0, -1], [1, -1], [2, 0], [1, 1], [0, 2]]

What is the fastest way in python to get the lowest X and Y in a pair. In this case [-1,-1].

Upvotes: 3

Views: 1194

Answers (3)

tobias_k
tobias_k

Reputation: 82899

Not sure it's the fastest, but it's probably the shortest and most 'pythonic':

>>> map(min, zip(*data))
[-1, -1]

Update: I did some timing analysis on this, too, using a list of 10000 random sublists and 100 iterations. Turns out it's a bit faster than Aशwini's itemgetter solution, but the ordinary for-loop is still the fastest:

0.400840   min_mapminzip
0.579334   min_itemgetter
0.292459   min_loop

That was for Python 2.x... with Python 3, where zip, map etc. are iterators, it's another story:

0.186229   min_mapminzip   # wrong result, see below
0.686008   min_itemgetter
0.336031   min_loop

Correction: I forgot to apply list in the cases where map is an iterator, thus creating the iterator but not doing any real work... Thanks to gnibbler and Aशwini for pointing this out! With list(map(...)), the execution times are pretty much the same as in Python 2.x, i.e. the plain old loop is still the fastest.

Update 2: Interestingly, the "map-min-zip" solution is faster only for relatively short lists -- 'short' as in about 10,000 items. For longer lists, about 100,000 and more, the "itemgetter" solution becomes faster. And the plain for-loop is always the fastest...

Upvotes: 7

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 250901

You can use min here:

>>> from operator import itemgetter
>>> lst = [[0, 0], [1, 0], [0, 1], [-1, 0], [0, -1], [1, -1], [2, 0], [1, 1], [0, 2]]
>>> x = min(lst, key=itemgetter(0))[0]
>>> y = min(lst, key=itemgetter(1))[1]
>>> x, y
(-1, -1)

Takes around 1 second for 9000000 items on my system(i5 4670):

In [3]: lst = lst*10**6

In [4]: %timeit (min(lst, key=itemgetter(0))[0], min(lst, key=itemgetter(1))[1])
1 loops, best of 3: 1.01 s per loop

A normal single loop version took around 341 ms:

def find_min(seq):
    min_x = float('inf')
    min_y = float('inf')
    for x, y in seq:
        if x < min_x : min_x = x
        if y < min_y : min_y = y
    return min_x, min_y

Timing comparison:

len(lst)
Out[42]: 9000000

%timeit find_min(lst)
1 loops, best of 3: 341 ms per loop

%timeit map(min, zip(*lst))
1 loops, best of 3: 1.21 s per loop

%timeit map(min, izip(*lst))
1 loops, best of 3: 1.14 s per loop

%timeit (min(lst, key=itemgetter(0))[0], min(lst, key=itemgetter(1))[1])
1 loops, best of 3: 1.04 s per loop

Upvotes: 4

m.wasowski
m.wasowski

Reputation: 6387

minima = data[0]
for pair in data[1:]:
    minima = map(min, zip(pair, minima))

Upvotes: 0

Related Questions