Fastest way to sort tiny lists in python [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 11 years ago.

Improve this question

I have a large number of very small lists I need to sort as quickly as possible. Usually these lists have 2-3 values in them, and the built in sorting methods seem to have too much overhead. Would a simple bubble sort be ok in this situation?

Example, want to sort:

[1, 5]
[4, 2]
[3, 7]
...

To:

[1, 5]
[2, 4]
[3, 7]
...

Right now I'm doing something like this:

def do_something( ilist ):
    ilist = sorted(ilist, reverse = True);
    return ilist;

for i in range(1000000000):
    do_something( [random_num,random_num ] );

Thanks.

What makes you think the built in functions have too much overhead? — Collin
– Collin, Commented Apr 30, 2014 at 2:19
Python's built-in sort is actually quite fast. It adjusts the algorithm it uses based on the size of the input, and for small lists it'll just end up using insertion sort. It's also implemented in C, so it'll probably be faster than anything you come up with in pure Python. See en.wikipedia.org/wiki/Timsort — dano
– dano, Commented Apr 30, 2014 at 2:21
My code is like 7 times slower when I sort, which seems like a lot since about half of the lists are already sorted. I just need a method to swap the elements if they're out of order, which doesn't seem like an exponential operation — CamJohnson26
– CamJohnson26, Commented Apr 30, 2014 at 2:36

Kei Minagawa · Accepted Answer · 2014-04-30 05:34:31Z

Yes. If the list of the lists has always 2 element. It's faster to use like > operator than using sorted.

[(i[1], i[0]) if i[0]>i[1] else i for i in lst]

Time:

lst = [(0, 9),
       (1, 8),
       (2, 7),
       (3, 6),
       (4, 5),
       (5, 4),
       (6, 3),
       (7, 2),
       (8, 1),
       (9, 0)]

%timeit [(i[1], i[0]) if i[0]>i[1] else i for i in lst]
1000000 loops, best of 3: 1.96 us per loop

%timeit [sorted(i) for i in lst]
100000 loops, best of 3: 5.87 us per loop

In your case, you said your list has 2 or 3 elements. So your sort function look like this.

def sort_few(lst):
    if len(lst)==2:
        if lst[0] > lst[1]:
            return (lst[1], lst[0])
        else:
            return lst
    else:
        if lst[0] > lst[1]:
            if lst[1] > lst[2]:
                return (lst[2], lst[1], lst[0])
            else:
                return (lst[1], lst[2], lst[0])
        elif lst[1] > lst[2]:
            if lst[2] > lst[0]:
                return (lst[0], lst[2], lst[1])
            else:
                return (lst[2], lst[0], lst[1])
        elif lst[2] > lst[0]:
            if lst[0] > lst[1]:
                return (lst[1], lst[0], lst[2])
            else:
                return lst

Time:

lst = [(1, 2, 3),
       (1, 3, 2),
       (2, 1, 3),
       (2, 3, 1),
       (3, 1, 2),
       (3, 2, 1),
       (1, 2, 3),
       (1, 3, 2),
       (2, 1, 3),
       (2, 3, 1),
       (3, 1, 2),
       (3, 2, 1)]


%timeit [sort_few(i) for i in lst]
100000 loops, best of 3: 6.3 us per loop

%timeit [sorted(i) for i in lst]
100000 loops, best of 3: 7.32 us per loop

So it's faster to use sort_few than sorted if there are a 2 or 3 element in the list.

shaktimaan · Accepted Answer · 2014-04-30 02:20:29Z

0

Using sorted() is pretty efficient:

>>> list_of_lists = [[1, 5], [4, 2], [3, 7]]
>>> sorted_lol = [sorted(sub_list) for sub_list in list_of_lists]
>>> sorted_lol
[[1, 5], [2, 4], [3, 7]]

answered Apr 30, 2014 at 2:20

shaktimaan

12.1k2 gold badges32 silver badges33 bronze badges

1 Comment

CamJohnson26 Over a year ago

Thanks, but its not sublists. It's a function that sorts a list of size 2... 100000000 times or however many are needed.

jake · Accepted Answer · 2014-04-30 02:21:12Z

0

values = [{1, 5},{4, 2},{3, 7}]
print(sorted(values))

Result:

[set([1, 5]), set([2, 4]), set([3, 7])]

answered Apr 30, 2014 at 2:21

jake

1,0278 silver badges9 bronze badges

1 Comment

roippi Over a year ago

He wants to sort sub-lists, and sets are unordered, so I don't see how this answers his question at all.

jmq · Accepted Answer · 2014-04-30 03:39:02Z

0

If it's only two elements:

f = lambda x: x if x[0] < x[1] else [x[1],x[0]]

then

x = [5,4]
f(x)

This would return '[4,5]'

x = [4,5]
f(x)

Also returns [4,5]

If it's more than two this doesn't work, though you could special case 3. This just doing a compare and swap instead of calling a full sort function.

answered Apr 30, 2014 at 3:39

jmq

10.4k16 gold badges60 silver badges73 bronze badges

Collectives™ on Stack Overflow

Fastest way to sort tiny lists in python [closed]

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Linked

Related