Simple slice support for list.sort() and .reverse()

[hwundram]

BPO	1491804
Nosy	@rhettinger, @terryjreedy, @bitdancer
Files	python-sort-reverse.diff: Python list/array patches, with doc updates, V2.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2010-08-12.09:53:33.078>
created_at = <Date 2006-05-19.19:19:08.000>
labels = ['interpreter-core', 'type-feature']
title = 'Simple slice support for list.sort() and .reverse()'
updated_at = <Date 2010-09-23.01:04:50.188>
user = 'https://bugs.python.org/hwundram'

bugs.python.org fields:

activity = <Date 2010-09-23.01:04:50.188>
actor = 'r.david.murray'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2010-08-12.09:53:33.078>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2006-05-19.19:19:08.000>
creator = 'hwundram'
dependencies = []
files = ['7267']
hgrepos = []
issue_num = 1491804
keywords = ['patch']
message_count = 8.0
messages = ['50292', '50293', '50294', '50295', '50296', '110831', '113671', '117161']
nosy_count = 5.0
nosy_names = ['collinwinter', 'rhettinger', 'terry.reedy', 'hwundram', 'r.david.murray']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue1491804'
versions = ['Python 3.3']

[hwundram]

As requested per

http://groups.google.de/group/comp.lang.python/browse_thread/thread/6feadf8170900e53/aa621eed0fe14050?hl=de#aa621eed0fe14050

list.sort() should support extra keyword arguments
start and stop, which specify a slice of the whole list
to sort inplace.

The attached patch implements this functionality, and
extends the sorted() builtin to also offer these
keyword arguments, and additionally implements slice
support (also with start, stop) for list.reverse().

The patch updates the list object methods and the
sorted builtin, and also updates the testsuite to check
for the new keyword arguments and updates the
documentation to list them.

[terryjreedy]

Logged In: YES
user_id=593130

Having thought about submitting an RFE for start/stop for
reverse, I support the enhancement. Please do the same
for array.reverse(, so list and array.reverse continue to
have the same signature. Two uses: one way to swap
partitions in place is reverse each partition and then the
whole sequence; probably more useful is the slice reversal
in one standard method for sequentially generating
permutations in lexicographical order.

[hwundram]

Logged In: YES
user_id=791932

The attached patch implements all of the old patch, and adds
the specified logic for array.reverse(), updates the
documentation for the array module and whatsnew25, and will
speed up the methods a slight little bit in the absense of
optimization when compiling Python.

[hwundram]

Logged In: YES
user_id=791932

By the way, I've just become aware of the fact that this
patch changes the semantics of list.sort() somewhat, because
of an optimization I did to the code. The DSU-function isn't
called anymore when there are less than two items to sort,
i.e. the list or the slice to sort is one item long. This means:

---

def test(k):
    k.append(4)
    return k[0]
x = [[1,2,3]]
x.sort(key=test)
print x

---

will now print [[1,2,3]] (with the patch applied), whereas
Python 2.4 would've printed [[1,2,3,4]], but not have called
timsort either.

I don't know whether this breaks anything (or the old
behaviour was sensible); at least it should have to be
documented. I'd like feedback before I start either taking
out the optimization or documenting this.

[collinwinter]

I think anyone who was relying on that behavior was treading on "implementation details" territory to begin with, so I wouldn't worry about this particular semantics nit.

[BreamoreBoy]

I can't see any sense in doing a patch review on this until there is agreement that the patch is actually needed. Having read the initially referenced thread on groups.google.de I'm not convinced that this is going to happen.

[rhettinger]

I'm rejecting this feature request on the grounds that the use cases are sufficiently uncommon to warrant adding API complexity.

Currently, the notions of reverse() and sort() are comparatively simple. They correspond well to what I see in other languages.

Another issue is orthogonality, keeping the notions of slicing separate from concerns about sorting and reversing.

Also, the optimization aspect of this feature request is misguided (trying to reduce an O(n) step embedded inside an O(n log n) operation.

The purported syntactic gain is also negligible and uncompelling.
The rare bit of code that currently is written:

  sorted(s[a:b], key=f)

would instead become:

  sorted(s, key=f, start=a, stop=b)

There is no significant syntactic win or gain in expressiveness.