ansaurus

Question

Sorting a sublist within a Python list of integers

Answer 1

+6 A:

You can write p[i:j] = sorted(p[i:j])

THC4k 2010-09-08 14:48:27

+1: Beat me by seconds with a simpler solution.

S.Lott 2010-09-08 14:50:29

Still not what the operator desires, but what I was going to suggest. It still has to make a separate sub-array and sort it before assigning it to `p[i:j]`. I've thought for some time that there should be an option in sort() to specify the range to sort over. That would eliminate the unnecessary memory usage.

Justin Peel 2010-09-08 14:54:02

That certainly addresses the "how" but wouldn't this create at least 2 new lists? One for the p[i:j] inside sorted and the second for the result from sorted.

sizzzzlerz 2010-09-08 14:54:49

@sizzzzlerz: How do you know `sort()` doesn't create **O** (n log(n)) temporary lists? What's wrong with one extra list?

S.Lott 2010-09-08 14:58:17

I don't know that it doesn't but there are many sorting algorithms that don't require additional memory for the main list itself and I would assume that .sort utilizes one of them. To be specific, I'm potentially calling this sort operation millions of times and I'd rather not have to continually allocate and free temporary memory.

sizzzzlerz 2010-09-08 15:00:57

@sizzzzlerz: "continually allocate and free temporary memory" That's not much overhead in Python. Until you can prove this actually **is** the bottleneck, don't prematurely optimize. Indeed, creating a list that requires sorting a sublist may indicate a poor choice of algorithm which creates the list. Indeed, a list may be inappropriate when there are sublists -- you may want to consider using some kind of tree to avoid all the sorting.

S.Lott 2010-09-08 15:05:53

@sizzzzlerz: What do you need this for anyways? Probably a list is not the data structure you want to begin with ...

THC4k 2010-09-08 15:07:44

If you're doing tons of numeric calculations, `numpy` *might* be better.

Nick T 2010-09-08 15:12:48

The list maintains a permutation of indices into another list. It is used to drive a exhaustive search for a set of solutions to a particular geometric puzzle. Once all the solutions are found for a given permutation, the next permutation of the list is found and the search proceeds until no more permutations are left. The permutation algorithm I'm using requires this sort operation. Although there are optimizations in place so I don't have to try all the possible 12! permutations, there still can be a very large number of them, thus, the desire to limit memory allocations, copies, etc..

sizzzzlerz 2010-09-08 15:30:09

@sizzzzlerz: Why aren't you using `itertools`? http://docs.python.org/library/itertools.html#itertools.permutations might do this for you.

S.Lott 2010-09-08 15:59:36

One of my optimizations to reduce the search space requires an ability to skip permutations that can't ever lead to a solution. This means that I may want to start my search for the next permutation at a location somewhere in the middle. itertools produces every possible permutation in lexographical order which isn't what I want.

sizzzzlerz 2010-09-08 16:18:53

@sizzzzlerz: It sounds like a "flat" list is inappropriate. If you can eliminate some permutations, it sounds like you have more structure in the problem, and should perhaps be using a tree of lists where all permutations make sense.

S.Lott 2010-09-08 18:30:12

Answer 2

A:

"in place" doesn't mean much. You want this.

p[i:j] = list( sorted( p[i:j] ) )

S.Lott 2010-09-08 14:48:34

Answer 3

A:

This is because p[i:j] returns a new list. I can think of this immediate solution:

l = p[i:j]
l.sort()
a = 0
for x in range(i, j):
    p[x] = l[a]
    a += 1

inspectorG4dget 2010-09-08 14:48:36

You could just write `p[i:j] = l`

KennyTM 2010-09-08 14:49:14

ansaurus

tags:

views:

answers:

Sorting a sublist within a Python list of integers

related questions