less performant than standard list #34

Closed
xcombelle opened this Issue Sep 2, 2011 · 2 comments

Projects

None yet

2 participants

@xcombelle

the performance on sorting can be inferior at standard python list (from an example of performance of timsort)

>>> import blist
>>> l = [i for i in range(1048576)]
>>> for i in range(3):
import random
r1 = random.randint(0,len(l)-1)
r2 = random.randint(0,len(l)-1)
l[r1],l[r2] = l[r2],l[r1]


>>> bl = blist.blist(l)
>>> def t(l):
    import time
    before = time.time()
    l.sort()
    return time.time() - before

>>> t(l)
0.04699993133544922
>>> t(bl)
0.28100013732910156
@DanielStutzbach

Yes, there are cases where Python's built-in list has better performance.

blist is optimized for sorting objects when using an int or float key (using the key= parameter). Python's built-in list does a better job when sorting simple types on a list that's already mostly ordered. If you'd like to compare their performance on random lists, try calling random.shuffle(l) just before the "before = time.time() line". I think sorting unordered objects is far more common in practice than sorting mostly-ordered integers, but if you frequently need to sort lists of already-mostly-sorted integers in practice, I'm curious to hear more about your use case.

@xcombelle

I don't know what is the most frequently use case, but as Java adopted TimSort as python I suppose that the developper of both language thinks that better behaviour in case of partially sorted list is preferable. Anyway, your sort doesn't do that bad in a case it was not designed for

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment