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  2449 
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 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
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
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
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
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.
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
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.
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 This discussion thread is closed Replies have been disabled for this discussion. Similar topics
3 posts
views
Thread by Dirk Hagemann |
last post: by
|
2 posts
views
Thread by vsgdp |
last post: by
|
3 posts
views
Thread by Massimiliano Alberti |
last post: by
|
13 posts
views
Thread by Joseph Garvin |
last post: by
|
43 posts
views
Thread by michael.f.ellis |
last post: by
|
51 posts
views
Thread by Joerg Schoen |
last post: by
|
9 posts
views
Thread by Paulo da Silva |
last post: by
|
28 posts
views
Thread by hlubenow |
last post: by
|
12 posts
views
Thread by Lars Eighner |
last post: by
| | | | | | | | | | | | | | | | | | | |
