sorting list of tuples by second (third...) tuple item
Marcus Stojek
I am still struggling with tuple-lists.
How can I sort a list of tuples (all tuples have 4 float items)
by the second (or third or n-th) tuple item. And I have to
do it fast.
Tanks,
Marcus
Greg Landrum
"Marcus Stojek" <sto...@part-gmbh.de> wrote in message
news:3c6bbe96...@news.easynews.net...
> Hi,
>
> I am still struggling with tuple-lists.
>
> How can I sort a list of tuples (all tuples have 4 float items)
> by the second (or third or n-th) tuple item.
Here's the basic incantation:
>>> foo = [(1,2,3),(1,3,3),(1,0,3)]
>>> foo.sort(lambda x,y:cmp(x[1],y[1])) # sort on the second element
>>> foo
[(1, 0, 3), (1, 2, 3), (1, 3, 3)]
> And I have to
> do it fast.
well now, that's a different problem. :-)
Seriously, the default python sort is pretty fast, so give that a try.
-greg
Jeff Shannon
Marcus Stojek wrote:
You can supply a custom comparison function to sort(), such as
this:
def mycmp(first, second):
return cmp( first[2], second[2] )
mylist.sort(mycmp)
But this tends to be pretty slow. For large lists, it's usually
considered that the "decorate-sort-undecorate" pattern is the most
effective way. Something like this:
def SortOnItem(mylist, index):
templist = [ (line[index], line) for line in mylist ]
templist.sort()
return [ line[1:] for line in templist ]
What this does is build a separate list containing a tuple of the
element that you want to sort on, and the entire line, sorts that
list (by the first element, of course), and then strips that first
element off. This can use a lot of memory (you're creating two
copies of your original list, but they are only references, not
deep copies), but until you hit memory constraints this is likely
to be faster than a custom cmp() function. (The custom cmp() makes
an extra function call for *each* line of the list, and function
calls are relatively expensive in Python.)
(Of course, the list comprehensions require Python 2.x; if you're
stuck on 1.5.2, the equivalent can be done with map/filter/lambda.)
Jeff Shannon
Technician/Programmer
Credit International
Justin Sheehy
> How can I sort a list of tuples (all tuples have 4 float items)
> by the second (or third or n-th) tuple item. And I have to
> do it fast.
Python's builtin sort is fairly fast, all you need to handle is the indexing.
The straightforward way would be:
lst.sort(lambda a,b: cmp(a[2], b[2]))
or if you don't like lambda:
def cmp3(a, b):
return cmp(a[2], b[2])
lst.sort(cmp3)
If you want more speed, you may want to decorate the list first:
newlst = [(x[2], x) for x in lst]
newlst.sort()
lst = [x[1] for x in newlst]
-Justin
kevin parks
of lists (i hate tuples). first thing you want is everything sorted by
the first value and then everything that has the same value for [0]
then sorted by [1]
[['i3', 24.0, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i8', 82.25, 0.75, 101, 7, 6, 5, 0, 0, 0, 0, 0.02, 2, \
['i9', 9, 0, 255, \
['i8', 83.0, 1.0, 101, 1, 1, 5, 0, 0, 0, 0, 0.02, 2, \
['i3', 17.0, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i3', 25.5, 0.5, 101, 4, 3, 7, 0, 0, 0, 1, 0, 5, \
['i6', 2.0, 0.5, 85, 7, 4, 6, 0, 0, 0, -1, 0.02, 2, \
['i3', 13.5, 0.5, 101, 4, 3, 7, 0, 0, 0, 1, 0, 5, \
['i4', 5.5, 6.5996, 101, 7, 4, 5, 7, 4, 5, 1, 0, 50, 50, 6.5, 6.5,
0.08000002, \
['i9', 18.0, 6.0, 100, 1, 1, 3, 0, 0, 0, 0, 0, 5, \
['i2', 222.0, 16.0, 1.100001, 1.1699, 0.56995, 0.7800003, \
['i3', 26.5, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i9', 16.0, 0.5, 50, 7, 4, 3, 0, 0, 0, 0, 0, 5, \
['i6', 1.0, 0.5, 85, 1, 1, 7, 0, 0, 0, -1, 0.02, 2, \
['i3', 28.0, 0.5, 101, 4, 3, 7, 0, 0, 0, 1, 0, 5, \
['i9', 24.0, 1.5, 50, 1, 1, 4, 0, 0, 0, 0, 0, 5, \
['i7', 0.5, 0.5, 101, 1, 1, 6, 0, 0, 0, 1, 0.02, 2, \
['i6', 0.5, 0.5, 85, 7, 4, 6, 0, 0, 0, -1, 0.02, 2, \
['i8', 81.5, 0.75, 101, 7, 4, 4, 0, 0, 0, 0, 0.02, 2, \
['i6', 1.5, 0.5, 85, 7, 6, 7, 0, 0, 0, -1, 0.02, 2, \
['i9', 14.5, 1.5, 50, 1, 1, 4, 0, 0, 0, 0, 0, 5, \
['i9', 17.0, 1.0, 50, 1, 1, 4, 0, 0, 0, 0, 0, 5, \
['i3', 29.0, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i3', 12.0, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i3', 16.0, 0.5, 101, 4, 3, 7, 0, 0, 0, 1, 0, 5, \
['i1', 0, 0, 18.715278000000001, \
['i3', 14.5, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5, \
['i2', 181.4001, 0.1000001, 0.62, 0.63, 1.100001, 1.1699]]
so you would want the above list to have all the i1 lines together and
all the lines that start i2 together and then all the lines that have
the same starting value sorted by their second value, so that the
above list would start to sort perhaps like this:
x = [['i1',0,0,18.715278], ['i2',181.4,0.1,0.62,0.63,1.10,1.17],
['i2',222.0,16.0,1.10,1.17,0.57,0.78],
['i3',12.000,0.500,101,7,6,7,0,0,0,-1,0,5],
['i3',13.500,0.500,101,4,3,7,0,0,0,1,0,5],
['i3',14.500,0.500,101,7,6,7,0,0,0,-1,0,5],
['i3',16.000,0.500,101,4,3,7,0,0,0,1,0,5],
['i3',17.000,0.500,101,7,6,7,0,0,0,-1,0,5],
['i3',24.000,0.500,101,7,6,7,0,0,0,-1,0,5],
['i3',25.500,0.500,101,4,3,7,0,0,0,1,0,5],
['i3',26.500,0.500,101,7,6,7,0,0,0,-1,0,5],
['i3',28.000,0.500,101,4,3,7,0,0,0,1,0,5],
.
.
.
? I have a stupid audio program that has a broken sort routine and
barfs if things are not presorted this way, even though it is supposed
to sort everything for you..
one odd thing to note is that the nested lists are not all the same
size.
inquiring minds want to know.
bets,
kevin
Paul Rubin
> How would you sort something based on 2 criteria. Say you have a list
> of lists (i hate tuples). first thing you want is everything sorted by
> the first value and then everything that has the same value for [0]
> then sorted by [1]
# try this:
yourlist = [['i3', 24.0, 0.5, 101, 7, 6, 7, 0, 0, 0, -1, 0, 5], \
['i8', 82.25, 0.75, 101, 7, 6, 5, 0, 0, 0, 0, 0.02, 2], \
['i9', 9, 0, 255], \
['i8', 83.0, 1.0, 101, 1, 1, 5, 0, 0, 0, 0, 0.02, 2]]
def compare_lists(x,y):
a = cmp(x[0],y[0])
if a: return a
return cmp(x[1],y[1])
yourlist.sort(compare_lists)
Just van Rossum
Paul Rubin <phr-n...@nightsong.com> wrote:
Nah, just do this:
yourlist.sort()
Just
Justin Sheehy
> How would you sort something based on 2 criteria. Say you have a list
> of lists (i hate tuples). first thing you want is everything sorted by
> the first value and then everything that has the same value for [0]
> then sorted by [1]
This is the default behavior of Python's listobject's sort method.
It will sort by the first element, then the second, then the third, etc...
If you want some other order, you have two choices:
- write a custom cmp function to pass to sort
- decorate your list so that the default sort does what you want
-Justin
kevin parks
>
> yourlist.sort()
>
> Just
so does that mean that what i want is the default behavior of the sort
method?
it sorts by column one then sorts by column 2m, then column 3.....
?
Gosh, i've got no interpreter here (@ an internet cafe). Ive got to
run home and see if that is waht really happens...
-kevin
kevin parks
code. I am always amazed at how many things are built in to Python.
bisect is one of those things that you always forget is there... I am
going to look at what folks posted a play around some. Though I am
really happy too see those lambdas get explained I was about to pop a
vein trying to get my head 'round those things.
I sort of guess you were goofing on me, but the funny thing is that
those functions did mostly work....
Thanks for your help everyone I am amazed that you could all figure
out what i was getting at. I think that I made a mistake or two in my
examples (i did on the fly) but i will play with the code now to see
that it give the results that I am after.
cheers,
-kevin
Marcus Stojek
>But this tends to be pretty slow. For large lists, it's usually
>considered that the "decorate-sort-undecorate" pattern is the most
>effective way. Something like this:
>
>def SortOnItem(mylist, index):
> templist = [ (line[index], line) for line in mylist ]
> templist.sort()
> return [ line[1:] for line in templist ]
>
Thanks Marcus
krallabandi
--
Posted via dBforums
http://dbforums.com