Quickest sorting mechanism for sorting by multiple predicates in python

Question

import operator
a = [[1,0.7,1],[4,0.8,1],[5,0.8,0.99],[11,0.9,0.98]]
b = sorted(a, key=lambda x:x[1], reverse=True);
c = sorted(b, key=lambda x:x[2], reverse=True);
s = sorted(a, key=lambda x : (x[2],x[1]), reverse=True);
i = sorted(a, key = operator.itemgetter(2, 1),reverse=True);

out of following outputs such as c,s and i which is the quickest method (in terms of time in worst case) for sorting a 5 Diamensional array of length around 20,000. Or are there any specific way of doing it rather than c,s,i

Use the timeit module and see which one runs the fastest for you — Blender
– Blender, Commented Sep 9, 2017 at 3:14
The time complexity is exactly the same for all of these - they are using the same sorting algorithm, and your key function doesn't do anything crazy. So, this is an empirical question, one which you have all the tools at your disposal to elucidate. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Sep 9, 2017 at 3:30

cs95 · Accepted Answer · 2018-09-25 05:01:48Z

2

I'm not sure there's any sense comparing the first two with the 3rd and 4th - they do different things.

sorted(a, key=lambda x:x[1], reverse=True)

Sorts the list of lists by the second element only, while...

sorted(b, key=lambda x:x[2], reverse=True)

Sorts the list of lists by the third element only, regardless of how the list was sorted before.

sorted(a, key=lambda x: (x[2],x[1]), reverse=True)
sorted(a, key=operator.itemgetter(2, 1), reverse=True)

Both of these methods sort the list by the third as well as the second element. Ties on the 3rd element are broken by the second, basically.

Performance

Small

100000 loops, best of 3: 3.62 µs per loop
100000 loops, best of 3: 2.9 µs per loop

The last method is faster simply because lambda functions are slower.

Medium (100K elements)

10 loops, best of 3: 60.7 ms per loop
10 loops, best of 3: 50.7 ms per loop

Large (3M elements)

1 loop, best of 3: 2.07 s per loop
1 loop, best of 3: 1.71 s per loop

It is important to understand that the theoretical time complexity of these methods are exactly the same - their order of growth is identical. The only difference here is the techniques you use, which can make minor differences in speed. It is also important to understand that if you're looking for high performance, Python isn't the language you should be working with.

edited Sep 25, 2018 at 5:01

answered Sep 9, 2017 at 3:18

cs95

406k106 gold badges744 silver badges797 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

juanpa.arrivillaga Over a year ago

Yes, I suspect these differences to disappear as the list grows larger, and the overhead of mapping the key function gets dwarfed by the sorting.

cs95 Over a year ago

@juanpa.arrivillaga Added some more numbers.

VPfB Over a year ago

@COLDSPEED. Python sort is stable. Sorting by the secondary key first and then by the primary key makes sense.

Amutheezan Over a year ago

@COOLSPEED I am doing an Machine Learning project, and I prefer to use python for it, are there any language that are capable of doing these kind of calculation easily except R and Matlab.( I have some issues and draw backs in implementing those for my project

cs95 Over a year ago

@AmutheezanSivagnanam there is a module called "timeit" that you could look into.

Collectives™ on Stack Overflow

Quickest sorting mechanism for sorting by multiple predicates in python

1 Answer 1

Small

Medium (100K elements)

Large (3M elements)

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Small

Medium (100K elements)

Large (3M elements)

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related