Hpw make lists that are easy to sort.
Terry Reedy
tjreedy at udel.edu
Thu Mar 29 04:35:29 CEST 2007
"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message
news:eueu79$mkd$1 at news5.zwoll1.ov.home.nl...
 Terry Reedy wrote:

 > One could generate the items in order in less space by doing, for
instance,
 > an mway merge, in which only the lowest member of each of the m
sublists
 > is present at any one time. But I don't know if this (which is
 > O(m*n*log(m))) would be any faster (in some Python implementation) for
any
 > particular values of m and m.

 If hashing is O(n+m), it would mean that it would be faster.

 I'm not sure if I can agree with your analysis. All information to
 generate the product is already inside the two lists we begin with.
 Doesn't that make the product less complex than a random n*m matrix? Or
 is that what you are saying with O(m*n*log(m)) ?
If I understand correctly, you want to multiiply each of m numbers by each
of n numbers, giving m*n products. That is O(m*n) work. Inserting (and
extracting) each of these is a constant size m priority cue takes, I
believe, O(log(m)) work, for a total of m*n*log(m). That is faster than
O(m*n*log(m*n)) for sorting m*n random numbers.
I don't know how you would sort by hashing.
Terry Jan Reedy
More information about the Pythonlist
mailing list