435,375 Members | 3,001 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,375 IT Pros & Developers. It's quick & easy.

how to find the longst element list of lists

 P: n/a 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 Replies

 P: n/a 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"] 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

 P: n/a 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

 P: n/a On 1/7/07, Michael M.

 P: n/a 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

 P: n/a > 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

 P: n/a 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

 P: n/a 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

 P: n/a Sorry, wrong place. Jan 7 '07 #9

 P: n/a On Sun, 07 Jan 2007 22:23:22 +0100, "Michael M." "I wish people would die in alphabetical order." -- My wife, the genealogist Jan 8 '07 #10

 P: n/a 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

 P: n/a 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_lengthwill 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 knowwho 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

 P: n/a 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_lengthwill 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 knowwho 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 [, [1j]]) Traceback (most recent call last): File "", line 1, in 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([, [1j]])) >>max_len, max_list (1, ) Peter Jan 8 '07 #13

 P: n/a On Sun, 07 Jan 2007 20:55:19 -0500, Dan Sommers wrote: On Sun, 07 Jan 2007 22:23:22 +0100, "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"] [ 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 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

 P: n/a 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." >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., ifyou end up with thousands of lists instead of just three), then sortingmay not be the way to go. Assuming that list_of_lists is your list oflists, 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_lengthwill 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 knowwho 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 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

 P: n/a On Mon, 08 Jan 2007 13:55:40 +0100, Peter Otten wrote: >The precise results depend on the version of Python you're running, theamount of memory you have, other processes running, and the details ofwhat's in the list you are trying to sort. But as my test shows, sort hassome overhead that makes it a trivial amount slower for sufficiently smalllists, 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

 P: n/a 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, theamount of memory you have, other processes running, and the details ofwhat's in the list you are trying to sort. But as my test shows, sorthas some overhead that makes it a trivial amount slower for sufficientlysmall 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()dand copied to L before each measurement. list.sort() treats alreadysorted 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 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 discussion thread is closed

Replies have been disabled for this discussion. 