How to find the longst element list of lists?
I think, there should be an easier way then this:
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
if len(s1) >= len(s2) and len(s1) >= len(s3):
sx1=s1 ## s1 ist längster
if len(s2) >= len(s3):
sx2=s2
sx3=s3
else:
sx2=s3
sx3=s2
if len(s2) >= len(s3) and len(s2) >= len(s1):
sx1=s2 ## s2 ist längster
if len(s3) >= len(s1):
sx2=s3
sx3=s1
else:
sx2=s1
sx3=s3
if len(s3) >= len(s1) and len(s3) >= len(s2):
sx1=s3 ## s3 ist längster
if len(s1) >= len(s2):
sx2=s1
sx3=s2
else:
sx2=s2
sx3=s1
After, the list ist sorted:
sx1 = ["a", "b", "c", "d"]
sx2 = ["q", "e", "d"]
sx3 = ["a", "b"] 16 2561
Michael M. kirjoitti:
How to find the longst element list of lists?
I think, there should be an easier way then this:
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
<snip>
After, the list ist sorted:
sx1 = ["a", "b", "c", "d"]
sx2 = ["q", "e", "d"]
sx3 = ["a", "b"]
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
ss = ((len(s1), s1), (len(s2), s2), (len(s3), s3))
sx = [y for (x, y) in sorted(ss)[::1]]
print sx
sx1, sx2, sx3 = sx
print sx1, sx2, sx3
Cheers,
Jussi
Michael M. a écrit :
How to find the longst element list of lists?
For what definition of "find" ? You want the lenght of the longest
sublist, it's index, or a reference to it ?
I think, there should be an easier way then this:
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
Err... this makes three distinct lists, not a list of lists.
if len(s1) >= len(s2) and len(s1) >= len(s3):
sx1=s1 ## s1 ist längster
if len(s2) >= len(s3):
sx2=s2
sx3=s3
else:
sx2=s3
sx3=s2
(snip repeated code)
Looks like it would be time to learn how to factor out repetitions...
After, the list ist sorted:
sx1 = ["a", "b", "c", "d"]
sx2 = ["q", "e", "d"]
sx3 = ["a", "b"]
This is still not a list of lists. Now for the answer, sorted() is your
friend:
print sorted([s1, s2, s3], key=list.__len__, reverse=True)
=[['a', 'b', 'c', 'd'], ['q', 'e', 'd'], ['a', 'b']]
# Or if you really want sx1, sx2 and sx3:
sx1, sx2, sx3 = sorted([s1, s2, s3], key=list.__len__, reverse=True)
Is that easier enough ?)
On 1/7/07, Michael M. <mi*****@mustun.chwrote:
How to find the longst element list of lists?
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
s = [s1, s2, s3]
s.sort(key=len, reverse=True)
print s[0] is s3
print s[1] is s1
print s[2] is s2
sx1, sx2, sx3 = s
print 'sx1:', sx1
print 'sx2:', sx2
print 'sx3:', sx3

Felipe.
Michael M. schrieb:
How to find the longst element list of lists?
I think, there should be an easier way then this:
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
if len(s1) >= len(s2) and len(s1) >= len(s3):
sx1=s1 ## s1 ist längster
if len(s2) >= len(s3):
sx2=s2
sx3=s3
else:
sx2=s3
sx3=s2
if len(s2) >= len(s3) and len(s2) >= len(s1):
sx1=s2 ## s2 ist längster
if len(s3) >= len(s1):
sx2=s3
sx3=s1
else:
sx2=s1
sx3=s3
if len(s3) >= len(s1) and len(s3) >= len(s2):
sx1=s3 ## s3 ist längster
if len(s1) >= len(s2):
sx2=s1
sx3=s2
else:
sx2=s2
sx3=s1
After, the list ist sorted:
sx1 = ["a", "b", "c", "d"]
sx2 = ["q", "e", "d"]
sx3 = ["a", "b"]
I don't really get that. You have three lists, you want to sort them
after their length. You should put them into one list.
I think you should rather implement this as:
>>list = [a1, s2, s3] list.sort(lambda x,y: cmp(len(y), len(x))) list
[['a', 'b', 'c', 'd'], ['q', 'e', 'd'], ['a', 'b']]
Thomas
>
Err... this makes three distinct lists, not a list of lists.
Sure. Logically spoken. Not in Python code. Or a number of lists.
Sure not [[ bla... ] [bla.]] etc.
Michael M. schrieb:
>Err... this makes three distinct lists, not a list of lists.
Sure. Logically spoken. Not in Python code. Or a number of lists.
Sure not [[ bla... ] [bla.]] etc.
???????
Thomas
Bruno Desthuilliers wrote:
>
Err... this makes three distinct lists, not a list of lists.
Sure. Logically spoken. Not in Python code. Or a number of lists.
Sure not [[ bla... ] [bla.]] etc.
On Sun, 07 Jan 2007 22:23:22 +0100,
"Michael M." <mi*****@mustun.chwrote:
How to find the longst element list of lists?
I think, there should be an easier way then this:
s1 = ["q", "e", "d"]
s2 = ["a", "b"]
s3 = ["a", "b", "c", "d"]
[ snip ]
One more thing to think about : if your list of lists grows (i.e., if
you end up with thousands of lists instead of just three), then sorting
may not be the way to go. Assuming that list_of_lists is your list of
lists, then something like this:
longest_list, longest_length = list_of_lists[ 0 ], len( longest_list )
for a_list in list_of_lists[ 1 : ]:
a_length = len( a_list )
if a_length longest_length:
longest_list, longest_length = a_list, a_length
will run faster than sorting the list just to pick off one element (O(n)
vs. O(n log n) for all of you BigOh notation fans out there; you know
who you are!).
Regards,
Dan

Dan Sommers
<http://www.tombstonezero.net/dan/>
"I wish people would die in alphabetical order."  My wife, the genealogist
Dan Sommers wrote:
...
longest_list, longest_length = list_of_lists[ 0 ], len( longest_list )
for a_list in list_of_lists[ 1 : ]:
a_length = len( a_list )
if a_length longest_length:
longest_list, longest_length = a_list, a_length
will run faster than sorting the list just to pick off one element (O(n)
vs. O(n log n) for all of you BigOh notation fans out there; you know
who you are!).
Or, more succinctly, after:
list_of_lists = [["q", "e", "d"],
["a", "b"],
["a", "b", "c", "d"]]
You can find the longest with:
maxlength, maxlist = max((len(lst), lst) for lst in list_of_lists)
or (for those pre2.5 people):
maxlength, maxlist = max([(len(lst), lst) for lst in list_of_lists])
Scott David Daniels sc***********@acm.org
Scott David Daniels wrote:
Dan Sommers wrote:
>... longest_list, longest_length = list_of_lists[ 0 ], len( longest_list ) for a_list in list_of_lists[ 1 : ]: a_length = len( a_list ) if a_length longest_length: longest_list, longest_length = a_list, a_length will run faster than sorting the list just to pick off one element (O(n) vs. O(n log n) for all of you BigOh notation fans out there; you know who you are!).
Or, more succinctly, after:
list_of_lists = [["q", "e", "d"],
["a", "b"],
["a", "b", "c", "d"]]
You can find the longest with:
maxlength, maxlist = max((len(lst), lst) for lst in list_of_lists)
or (for those pre2.5 people):
maxlength, maxlist = max([(len(lst), lst) for lst in list_of_lists])
Generator expressions worked in 2.4 too. If you're using 2.5, you should
take advantage of the key= argument to max and skip the generator
expression entirely::
>>list_of_lists = [["q", "e", "d"],
... ["a", "b"],
... ["a", "b", "c", "d"]]
>>maxlist = max(list_of_lists, key=len) maxlist, len(maxlist)
(['a', 'b', 'c', 'd'], 4)
STeVe
Scott David Daniels wrote:
Dan Sommers wrote:
>... longest_list, longest_length = list_of_lists[ 0 ], len( longest_list ) for a_list in list_of_lists[ 1 : ]: a_length = len( a_list ) if a_length longest_length: longest_list, longest_length = a_list, a_length will run faster than sorting the list just to pick off one element (O(n) vs. O(n log n) for all of you BigOh notation fans out there; you know who you are!).
Or, more succinctly, after:
list_of_lists = [["q", "e", "d"],
["a", "b"],
["a", "b", "c", "d"]]
You can find the longest with:
maxlength, maxlist = max((len(lst), lst) for lst in list_of_lists)
or (for those pre2.5 people):
pre2.4
maxlength, maxlist = max([(len(lst), lst) for lst in list_of_lists])
With the caveat that if there are lists of equal length their items will be
compared:
>>max((len(lst), lst) for lst in [[1], [1j]])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers
So if you want the first out of the lists with equal length on a python
where Steve's enhancement is not yet available (pre2.5):
>>max_len, dummy, max_list = max((len(lst), i, lst) for i, lst in
enumerate([[1], [1j]]))
>>max_len, max_list
(1, [1])
Peter
On Sun, 07 Jan 2007 20:55:19 0500, Dan Sommers wrote:
On Sun, 07 Jan 2007 22:23:22 +0100,
"Michael M." <mi*****@mustun.chwrote:
>How to find the longst element list of lists? I think, there should be an easier way then this:
> s1 = ["q", "e", "d"] s2 = ["a", "b"] s3 = ["a", "b", "c", "d"]
[ snip ]
One more thing to think about: if your list of lists grows (i.e., if
you end up with thousands of lists instead of just three), then sorting
may not be the way to go. Assuming that list_of_lists is your list of
lists, then something like this:
longest_list, longest_length = list_of_lists[ 0 ], len( longest_list )
for a_list in list_of_lists[ 1 : ]:
a_length = len( a_list )
if a_length longest_length:
longest_list, longest_length = a_list, a_length
will run faster than sorting the list just to pick off one element (O(n)
vs. O(n log n) for all of you BigOh notation fans out there; you know
who you are!).
But your O(n) code is running in relatively slow Python, while the sort
method, while O(n log n), is some of the fastest, most highly optimized C
code out there. Unless your list is truly gigantic, chances are the sort
version will win.
Here's my timing code:
import timeit
def getlongest1(list_of_lists):
longest_list = list_of_lists[ 0 ]
longest_length = len( longest_list )
for a_list in list_of_lists[ 1 : ]:
a_length = len( a_list )
if a_length longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
def getlongest2(list_of_lists):
list_of_lists.sort(key=len)
return list_of_lists[0]
def make_list_of_lists(length):
return [[None]*i for i in xrange(length)]
t1 = timeit.Timer("getlongest1(L)", "from __main__ import getlongest1, L")
t2 = timeit.Timer("getlongest2(L)", "from __main__ import getlongest2, L")
Note that my test list_of_lists grows very big quite fast, like O(n**2).
Assuming Python pointers are eight bytes, a mere length=10000 will
require over 760MB just for the pointers. More realistic data may allow
more extensive testing.
And here are my timing results:
>>L = make_list_of_lists(1) print t1.timeit(1000), t2.timeit(1000)
0.00209903717041 0.00367403030396
>>L = make_list_of_lists(10) print t1.timeit(1000), t2.timeit(1000)
0.00871086120605 0.00775289535522
>>L = make_list_of_lists(100) print t1.timeit(1000), t2.timeit(1000)
0.121382951736 0.0518100261688
>>L = make_list_of_lists(1000) print t1.timeit(1000), t2.timeit(1000)
0.809508085251 0.508343935013
>>L = make_list_of_lists(10000) print t1.timeit(100), t2.timeit(100)
0.906499147415 0.732254981995
>>L = make_list_of_lists(20000) print t1.timeit(100), t2.timeit(100)
1.83560800552 1.58732700348
For a list of 1 item, sorting is 1.8 times SLOWER;
For a list of 10 items, sorting is 1.1 times FASTER;
For 100 items, sorting is 2.3 times faster;
For 1000 items, sorting is 1.6 times faster;
For 10,000 items, sorting is 1.2 times faster;
For 20,000 items, sorting is 1.1 times faster.
The precise results depend on the version of Python you're running, the
amount of memory you have, other processes running, and the details of
what's in the list you are trying to sort. But as my test shows, sort has
some overhead that makes it a trivial amount slower for sufficiently small
lists, but for everything else you're highly unlikely to beat it.

Steven.
Steven D'Aprano wrote:
On Sun, 07 Jan 2007 20:55:19 0500, Dan Sommers wrote:
>On Sun, 07 Jan 2007 22:23:22 +0100, "Michael M." <mi*****@mustun.chwrote:
>>How to find the longst element list of lists? I think, there should be an easier way then this:
>> s1 = ["q", "e", "d"] s2 = ["a", "b"] s3 = ["a", "b", "c", "d"]
[ snip ]
One more thing to think about: if your list of lists grows (i.e., if you end up with thousands of lists instead of just three), then sorting may not be the way to go. Assuming that list_of_lists is your list of lists, then something like this:
longest_list, longest_length = list_of_lists[ 0 ], len( longest_list ) for a_list in list_of_lists[ 1 : ]: a_length = len( a_list ) if a_length longest_length: longest_list, longest_length = a_list, a_length
will run faster than sorting the list just to pick off one element (O(n) vs. O(n log n) for all of you BigOh notation fans out there; you know who you are!).
But your O(n) code is running in relatively slow Python, while the sort
method, while O(n log n), is some of the fastest, most highly optimized C
code out there. Unless your list is truly gigantic, chances are the sort
version will win.
Here's my timing code:
import timeit
def getlongest1(list_of_lists):
longest_list = list_of_lists[ 0 ]
longest_length = len( longest_list )
for a_list in list_of_lists[ 1 : ]:
a_length = len( a_list )
if a_length longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
def getlongest2(list_of_lists):
list_of_lists.sort(key=len)
return list_of_lists[0]
def make_list_of_lists(length):
return [[None]*i for i in xrange(length)]
t1 = timeit.Timer("getlongest1(L)", "from __main__ import getlongest1, L")
t2 = timeit.Timer("getlongest2(L)", "from __main__ import getlongest2, L")
Note that my test list_of_lists grows very big quite fast, like O(n**2).
Assuming Python pointers are eight bytes, a mere length=10000 will
require over 760MB just for the pointers. More realistic data may allow
more extensive testing.
And here are my timing results:
>>>L = make_list_of_lists(1) print t1.timeit(1000), t2.timeit(1000)
0.00209903717041 0.00367403030396
>>>L = make_list_of_lists(10) print t1.timeit(1000), t2.timeit(1000)
0.00871086120605 0.00775289535522
>>>L = make_list_of_lists(100) print t1.timeit(1000), t2.timeit(1000)
0.121382951736 0.0518100261688
>>>L = make_list_of_lists(1000) print t1.timeit(1000), t2.timeit(1000)
0.809508085251 0.508343935013
>>>L = make_list_of_lists(10000) print t1.timeit(100), t2.timeit(100)
0.906499147415 0.732254981995
>>>L = make_list_of_lists(20000) print t1.timeit(100), t2.timeit(100)
1.83560800552 1.58732700348
For a list of 1 item, sorting is 1.8 times SLOWER;
For a list of 10 items, sorting is 1.1 times FASTER;
For 100 items, sorting is 2.3 times faster;
For 1000 items, sorting is 1.6 times faster;
For 10,000 items, sorting is 1.2 times faster;
For 20,000 items, sorting is 1.1 times faster.
The precise results depend on the version of Python you're running, the
amount of memory you have, other processes running, and the details of
what's in the list you are trying to sort. But as my test shows, sort has
some overhead that makes it a trivial amount slower for sufficiently small
lists, but for everything else you're highly unlikely to beat it.
Try again with tN.timeit(1) and a second list that is random.shuffle()d and
copied to L before each measurement. list.sort() treats already sorted
lists specially.
Peter
On Mon, 08 Jan 2007 13:55:40 +0100, Peter Otten wrote:
>The precise results depend on the version of Python you're running, the amount of memory you have, other processes running, and the details of what's in the list you are trying to sort. But as my test shows, sort has some overhead that makes it a trivial amount slower for sufficiently small lists, but for everything else you're highly unlikely to beat it.
Try again with tN.timeit(1) and a second list that is random.shuffle()d and
copied to L before each measurement. list.sort() treats already sorted
lists specially.
Or, simply shuffle the list itself. Why copy it?
In my tests, sorting still wins, and by roughly the same factor.
One optimization that might shift the balance would be to remove the
list copying in the nonsort code (list_of_lists[1:]). That's going to be
very time consuming for big lists.

Steven.
Steven D'Aprano wrote:
On Mon, 08 Jan 2007 13:55:40 +0100, Peter Otten wrote:
>>The precise results depend on the version of Python you're running, the amount of memory you have, other processes running, and the details of what's in the list you are trying to sort. But as my test shows, sort has some overhead that makes it a trivial amount slower for sufficiently small lists, but for everything else you're highly unlikely to beat it.
Try again with tN.timeit(1) and a second list that is random.shuffle()d and copied to L before each measurement. list.sort() treats already sorted lists specially.
Or, simply shuffle the list itself. Why copy it?
To feed the same data to every algorithm. This is an act of fairness, though
with negligable impact on the benchmark results, I suspect :)
In my tests, sorting still wins, and by roughly the same factor.
One optimization that might shift the balance would be to remove the
list copying in the nonsort code (list_of_lists[1:]). That's going to be
very time consuming for big lists.
With the tweak that you suggest above the loop wins for 100 items on my
machine...
N loop iloop max sort
1 0.000008 0.000019 0.000012 0.000010
10 0.000008 0.000008 0.000009 0.000013
100 0.000095 0.000037 0.000028 0.000088
1000 0.000374 0.000341 0.001304 0.001204
5000 0.001930 0.001719 0.001212 0.007062
if you can trust the timings for small values of N.
The script to generate this table has become somewhat baroque :)
import random
import timeit
timers = []
def bench(f):
t = timeit.Timer("getlongest(L)", "from __main__ import %s as
getlongest, L, items; L[:] = items" % f.__name__)
t.name = f.__name__.split("_")[1]
t.function = f
timers.append(t)
return f
@bench
def getlongest_loop(lists):
longest_list = lists[0]
longest_length = len(longest_list)
for a_list in lists[1:]:
a_length = len(a_list)
if a_length longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
@bench
def getlongest_iloop(lists):
lists = iter(lists)
longest_list = lists.next()
longest_length = len(longest_list)
for a_list in lists:
a_length = len(a_list)
if a_length longest_length:
longest_list, longest_length = a_list, a_length
return longest_list
@bench
def getlongest_max(lists):
return max(lists, key=len)
@bench
def getlongest_sort(lists):
lists.sort(key=len)
return lists[1]
def make_list_of_lists(length):
lol = [[None]*i for i in xrange(length)]
random.shuffle(lol)
return lol
def measure(N):
print "%10d" % N,
for t in timers:
print "%10.6f" % t.timeit(1),
print
if __name__ == "__main__":
import sys
if "test" in sys.argv:
L = make_list_of_lists(100)
expected = [None]*99
for t in timers:
assert t.function(L[:]) == expected
raise SystemExit
L = []
print "N".rjust(10),
print " ".join(t.name.rjust(10) for t in timers)
for N in [1, 10, 100, 1000, 5000]:
items = make_list_of_lists(N)
measure(N)
Peter This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Dirk Hagemann 
last post by:
Hi!
I have a list of lists and in some of these lists are elements which I
want to change.
Here an example:
lists=
'None' should be replaced by 0 or NULL or something else. But as far as
I...

by: vsgdp 
last post by:
From what I learned, if you want to do random element insertions and
deletions you should use a list. But, with std::vector, if the order of the
elements does not matter, couldn't you efficiently...

by: Massimiliano Alberti 
last post by:
Can someone check this? If it's OK, you can use however you want... :)
It should search for an element in an array and, if it can't find it, return
the next element.
key is what you are...

by: Joseph Garvin 
last post by:
When I first came to Python I did a lot of C style loops like this:
for i in range(len(myarray)):
print myarray
Obviously the more pythonic way is:
for i in my array:
print i

by: michael.f.ellis 
last post by:
The following script puzzles me. It creates two nested lists that
compare identically. After identical element assignments, the lists
are different. In one case, a single element is replaced. In...

by: Joerg Schoen 
last post by:
Hi folks!
Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.)
For linked lists, mergesort is the typical choice.
While I was looking for a optimized implementation of mergesort...

by: Paulo da Silva 
last post by:
Hi!
What is the best way to have something like the bisect_left
method on a list of lists being the comparision based on an
specified arbitrary i_th element of each list element?
Is there,...

by: hlubenow 
last post by:
Hello,
I really like Perl and Python for their flexible lists like @a (Perl) and
a (Python), where you can easily store lots of strings or even a whole
textfile.
Now I'm not a...

by: Lars Eighner 
last post by:
I take this example from a writer in alt.usage.english
<news://r3jie3p93s1eaflgcckn2hinf3li4mnfud@4ax.com>, where the question
of whether the "and" is required came up strictly as an issue of...

by: isladogs 
last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
For other local times, please check World Time Buddy
In...

by: jianzs 
last post by:
Introduction
Cloudnative applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...

by: abbasky 
last post by:
### Vandf component communication method one: data sharing
Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...

by: fareedcanada 
last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...

by: stefan129 
last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multidomain SSL certificates? Any recommendations on reliable providers or specific...

by: egorbl4 
last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это
Что это? Что мне с этим делать?
...

by: davi5007 
last post by:
Hi,
Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...

by: MeoLessi9 
last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

by: Aftab Ahmad 
last post by:
Hello Experts!
I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
 