In which versions is list.sort stable? 
Author Message
 In which versions is list.sort stable?

Has list.sort always been stable? Or, if not, in which python versions
is it not stable?

--
Magnus Lie Hetland               "Nothing shocks me. I'm a scientist."
http://www.*-*-*.com/                                   -- Indiana Jones



Thu, 13 Oct 2005 01:46:37 GMT  
 In which versions is list.sort stable?

Quote:

> Has list.sort always been stable? Or, if not, in which Python versions
> is it not stable?

list.sort has not been stable in 1.5.2, 2.0.*, 2.1.*, 2.2.*.  I do not
know about previous versions.  Note that list.sort may once again cease
being stable (in 2.4.* or further versions) if the timbot dreams up one
that's even better on _other_ criteria -- stability's not going to
constrain his algorithm choices.

Alex



Thu, 13 Oct 2005 02:51:10 GMT  
 In which versions is list.sort stable?


Quote:

>> Has list.sort always been stable? Or, if not, in which Python versions
>> is it not stable?

>list.sort has not been stable in 1.5.2, 2.0.*, 2.1.*, 2.2.*.  I do not
>know about previous versions.  Note that list.sort may once again cease
>being stable (in 2.4.* or further versions) if the timbot dreams up one
>that's even better on _other_ criteria -- stability's not going to
>constrain his algorithm choices.

OTOH, Uncle Timmy won't gratuitously remove stability, either.  But I
still wouldn't bet on Python's sort staying stable past 2.3.
--

"In many ways, it's a dull language, borrowing solid old concepts from
many other languages & styles:  boring syntax, unsurprising semantics,
few automatic coercions, etc etc.  But that's one of the things I like
about it."  --Tim Peters on Python, 16 Sep 93



Thu, 13 Oct 2005 03:37:45 GMT  
 In which versions is list.sort stable?
Aahz wrote on 2003-04-26:

Quote:



> >> Has list.sort always been stable? Or, if not, in which Python versions
> >> is it not stable?

> >list.sort has not been stable in 1.5.2, 2.0.*, 2.1.*, 2.2.*.  I do not
> >know about previous versions.  Note that list.sort may once again cease
> >being stable (in 2.4.* or further versions) if the timbot dreams up one
> >that's even better on _other_ criteria -- stability's not going to
> >constrain his algorithm choices.

> OTOH, Uncle Timmy won't gratuitously remove stability, either.  But I
> still wouldn't bet on Python's sort staying stable past 2.3.

Why don't we just grow a `list.stablesort` method that can be an alias
to `list.sort` currently but is guaranteed to be some stable sort
forever?  Explicit is better than implicit, so in the rare case that
you do rely on it, why not spell it out?

--



Fri, 14 Oct 2005 02:17:04 GMT  
 In which versions is list.sort stable?

Quote:

> Why don't we just grow a `list.stablesort` method that can be an alias
> to `list.sort` currently but is guaranteed to be some stable sort
> forever?  Explicit is better than implicit, so in the rare case that
> you do rely on it, why not spell it out?

Or, as a temporary workaround:

# non-in-place sort
def stablesort(lst):
   # insure stable sorting by adding indices to the list to sort
   lst = [(lst[i], i) for i in xrange(len(lst))]
   lst.sort()
   # remove the indices
   return [t[0] for t in lst]

# in-place sort
def stablesort(lst):
   for i in xrange(len(lst)):
      lst[i] = (lst[i], i)
   lst.sort()
   for i in xrange(len(lst)):
      lst[i] = lst[i][0]



Fri, 14 Oct 2005 04:39:44 GMT  
 In which versions is list.sort stable?
[Beni Cherniavsky]

Quote:
> Why don't we just grow a `list.stablesort` method that can be an alias
> to `list.sort` currently but is guaranteed to be some stable sort
> forever?  Explicit is better than implicit, so in the rare case that
> you do rely on it, why not spell it out?

Because Guido has shown no interest in saying that Python-the-language
guarantees to provide a stable sorting method.  Now that 2.3 has a stable
sort, I expect many apps will find that it's still more efficient to force
stability via injecting sequence indices into sort tuples.  That is,

    temp = [(obj.key(), i, obj) for i, obj in enumerate(list_of_objects)]
    temp.sort()
    result = [obj for key, i, obj in temp]

will often be faster than

    temp = [(obj.key(), obj) for obj in list_of_objects]
    temp.sort()
    result = [obj for key, obj in temp]

The hangup is that tuple comparison breaks ties in the first element
position by going on to compare more element positions.  In the latter
spelling, that can invoke arbitrarily expensive object comparison, but in
the former spelling is always resolved no latter than by comparison of
unequal ints.

This became painfully clear during timing tests run while the 2.3 sort was
being developed, on a database-sorting example contributed by an alpha
tester, where primary keys where often equal.  Forcing stability in that
test ran twice as fast as when leaving the sequence indices out of the
tuples.

stability-is-the-answer-to-fewer-questions-than-are-asked-ly y'rs  - tim



Fri, 14 Oct 2005 05:35:36 GMT  
 In which versions is list.sort stable?
Tim Peters wrote on 2003-04-27:

Quote:
> [Beni Cherniavsky]
> > Why don't we just grow a `list.stablesort` method that can be an alias
> > to `list.sort` currently but is guaranteed to be some stable sort
> > forever?  Explicit is better than implicit, so in the rare case that
> > you do rely on it, why not spell it out?

> Because Guido has shown no interest in saying that Python-the-language
> guarantees to provide a stable sorting method.  Now that 2.3 has a stable
> sort, I expect many apps will find that it's still more efficient to force
> stability via injecting sequence indices into sort tuples.  That is,

>     temp = [(obj.key(), i, obj) for i, obj in enumerate(list_of_objects)]
>     temp.sort()
>     result = [obj for key, i, obj in temp]

Neat trick, never occurred to me to force stability with the
{,un}decorate pattern (although I'm well familiar with it), perhaps
because I never needed a stable sort so far <wink>.  I made this
suggestion simply because I thought of this as a cleaner way
immediately after I saw the announcement that "it's now stable but
without promises"...

Quote:
> will often be faster than

>     temp = [(obj.key(), obj) for obj in list_of_objects]
>     temp.sort()
>     result = [obj for key, obj in temp]

> The hangup is that tuple comparison breaks ties in the first element
> position by going on to compare more element positions.  In the latter
> spelling, that can invoke arbitrarily expensive object comparison, but in
> the former spelling is always resolved no latter than by comparison of
> unequal ints.

> This became painfully clear during timing tests run while the 2.3 sort was
> being developed, on a database-sorting example contributed by an alpha
> tester, where primary keys where often equal.  Forcing stability in that
> test ran twice as fast as when leaving the sequence indices out of the
> tuples.

Even more neat; I think I can use this trick right now.  Perhaps the
docs should mention this right after saying that "code that intends to
be portable across implementations and versions must not rely on
stability".  Hmm, this "perhaps the docs should say X" theme is
recurring lately.  I wander what would happen if the docs would be
turned into a Wiki (probably - a mess - but a pseudo-wiki that
automagically turns edits into submitted patches or something like
that could be convenient.

[s.split("-ly y'rs\n")[::-1] for s in signatures].sort()-ly y'rs



Sat, 15 Oct 2005 04:32:18 GMT  
 In which versions is list.sort stable?
Can you please explain to a newbie what this thread means?

Should I not use SORT in Python 2.2.2? Docs do not mention anything
about "unstability". Are there any other "bacis" functions (and SORT
seems pretty basic to me) that I should avoid???

Thanks



Sat, 15 Oct 2005 08:15:12 GMT  
 In which versions is list.sort stable?

Quote:

> Can you please explain to a newbie what this thread means?

> Should I not use SORT in Python 2.2.2? Docs do not mention anything
> about "unstability". Are there any other "bacis" functions (and SORT
> seems pretty basic to me) that I should avoid???

It's not that list.sort is buggy in some versions of Python.

The "stability" of a sort refers to the result of a sort on a list where
there is not a total ordering.  For instance, consider the following list:
        [4, 3a, 2, 3b]
where 3a and 3b are equal to each other, but distinct.

One possible sorted version of that list is
        [2, 3b, 3a, 4]
but if your sort routine gives this result then it is not "stable", because
3a was before 3b in the input, but not in the output.  The "stable" output
is
        [2, 3a, 3b, 4]

In Python 2.3, the sort happens to have the property that it will always
give the *second* result, while in other versions either result may be
given.  Unless the sort is "stable", either result is acceptable.

A non-stable sort can be made stable by sorting on a tuple of (l[i], i)
because now there are no equal but distinct elements.  This is one use of
the decorate-sort-undecorate idiom.  A "sort stably" function was posted
elsewhere in this thread that (I think) achieves the result in this way.
As Tim (author of the new sort) also posted, this may be faster anyway(!).

Jeff



Sat, 15 Oct 2005 08:48:11 GMT  
 In which versions is list.sort stable?

Cheers,
Brian

Quote:
> -----Original Message-----



Quote:
> On Behalf Of Frantisek Fuka
> Sent: Monday, April 28, 2003 17:15

> Subject: Re: In which versions is list.sort stable?

> Can you please explain to a newbie what this thread means?

A stable sort is a sorting algorithm that does not change the relative
order of elements that have equal values. It has nothing to do with
crashing. Here is an example:

Python 2.2.1 Build...

Quote:
>>> stuff = [("grape", 5.50), ("banana", 5.50), ("cherry", 3)]
>>> stuff.sort(lambda x,y: cmp(x[1], y[1]))
>>> print stuff

[('cherry', 3), ('banana', 5.5), ('grape', 5.5)]

As you can see, the banana and grape tuples have been swapped even
though swapping them was not necessary to satisfy the sorting condition.
So the Python 2.2 sorting algorithm is not stable. The Python 2.3
sorting algorithm is i.e. if would return:
[('cherry', 3), ('grape', 5.5), ('banana', 5.5)]

Cheers,
Brian



Sat, 15 Oct 2005 08:56:05 GMT  
 In which versions is list.sort stable?

Quote:

> Can you please explain to a newbie what this thread means?

> Should I not use SORT in Python 2.2.2? Docs do not mention anything
> about "unstability". Are there any other "bacis" functions (and SORT
> seems pretty basic to me) that I should avoid???

I didn't know what a "stable sort" is, either. So I looked it up:

http://www.wikipedia.org/wiki/Stable_sort

"""
A stable sort is a sort algorithm that does not change the relative
order of elements that have equal key values. This is important for some
algorithms (for example, radix sort).
"""

So it's not that Python's sort implementation is unstable in the sense
of broken :-)

HTH,

-- Gerhard



Sat, 15 Oct 2005 08:42:54 GMT  
 
 [ 11 post ] 

 Relevant Pages 

1. fast stable rs-sort, transpose and FAQ 4.51

2. stable sorting in 8.0

3. Sort (List sorts...)

4. when will the next stable version available

5. New GNU PROLOG stable version

6. VSE, Most stable version?

7. stLgrind - fileOut files to LaTeX (stable version)

8. Sorting a list of lists.

9. operator - on list should be O(n) on sorted lists

10. Sorting lists of lists by columns

11. Can you sort a list of lists?

12. Need to Create a Catalogued Version of the Sorted File

 

 
Powered by phpBB® Forum Software