Does '#hash' mean anything in IDLE?

Kent Johnson kent at kentsjohnson.com
Tue Mar 7 02:14:12 CET 2006


Paul Rubin wrote:
> Scott David Daniels <scott.daniels at acm.org> writes:
>>Using a variant of DSU (Decorate-Sort-Undecorate) with max for S,
>>rather than sort:
>>
>>     print max((len(words), words) for words in d.itervalues())
>>or:
>>     size, words = max((len(words), words) for words in d.itervalues())
>>     print size, sorted(words)
> 
> 
> That's nice and concise but it doesn't completely fix the running time
> issue.  max(words, key=len) should run in O(N) time where N is the
> number of words, but
>   max((len(words), words) for words in d.itervalues())
> might need time proportional to the total lengths of the words.  I.e.
> suppose words=['aaaaaaaa','aaaaaaab','aaaaaaac'].  They are the same
> length so the cmp builtin proceeds to the next component of the tuples
> being compared.  That means the strings get compared character by
> character.  That's maybe not too bad for dictionary words, but isn't
> too great for arbitrary strings which might be millions of chars each.

use
max((len(words), i, words) for i, words in enumerate(d.itervalues()))

The index will always disambiguate and words will never be compared.
> 
> In general that DSU pattern doesn't even always work: you might want
> the max of objects which don't directly support any comparison methods
> that the cmp builtin understands. 

Using the index as above prevents the objects from ever being compared.

Kent



More information about the Python-list mailing list