how to find the longst element list of lists

[Michael M.]

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

 

[Jussi Salmela]

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

 

[Felipe Almeida Lessa]

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

 

[Thomas Ploch]

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

 

[Bruno Desthuilliers]

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 ?-)

 

[Michael M.]

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

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

 

[Michael M.]

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

Sorry, wrong place.

 

[Dan Sommers]

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

 

[Scott David Daniels]

...
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
(e-mail address removed)

 

[Steven Bethard]

...
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"]] (['a', 'b', 'c', 'd'], 4)

STeVe

 

[Peter Otten]

...
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

 

[Steven D'Aprano]

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:
0.00209903717041 0.00367403030396
0.00871086120605 0.00775289535522
0.121382951736 0.0518100261688
0.809508085251 0.508343935013
0.906499147415 0.732254981995
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.

 

[Peter Otten]

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:
0.00209903717041 0.00367403030396
0.00871086120605 0.00775289535522
0.121382951736 0.0518100261688
0.809508085251 0.508343935013
0.906499147415 0.732254981995
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

 

[Steven D'Aprano]

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.

 

[Peter Otten]

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