473,233 Members | 1,430 Online

# how to find the longst element list of lists

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"]

Jan 7 '07 #1
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
Jan 7 '07 #2
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 ?-)
Jan 7 '07 #3
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.
Jan 7 '07 #4
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
Jan 7 '07 #5
>
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.
Jan 7 '07 #6
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
Jan 7 '07 #7
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.
Jan 7 '07 #8
Sorry, wrong place.
Jan 7 '07 #9
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 Big-Oh 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
Jan 8 '07 #10
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 Big-Oh 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 pre-2.5 people):
maxlength, maxlist = max([(len(lst), lst) for lst in list_of_lists])

--Scott David Daniels
sc***********@acm.org
Jan 8 '07 #11
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 Big-Oh 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 pre-2.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
Jan 8 '07 #12
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 Big-Oh 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 pre-2.5 people):
pre-2.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 (pre-2.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
Jan 8 '07 #13
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 Big-Oh 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.

Jan 8 '07 #14
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 Big-Oh 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

Jan 8 '07 #15
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 non-sort code (list_of_lists[1:]). That's going to be
very time consuming for big lists.
--
Steven.

Jan 8 '07 #16
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 non-sort 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
Jan 9 '07 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 3 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... 2 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... 3 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... 13 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 43 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... 51 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... 9 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,... 28 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 text-file. Now I'm not a... 12 by: Lars Eighner | last post by: I take this example from a writer in alt.usage.english , where the question of whether the "and" is required came up strictly as an issue of... 3 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... 0 by: jianzs | last post by: Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from... 0 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... 0 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... 0 by: stefan129 | last post by: Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific... 0 by: egorbl4 | last post by: Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ... 1 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... 0 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".... 0 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...