Hpw make lists that are easy to sort.
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
| > an m-way merge, in which only the lowest member of each of the m
| > 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
| > 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 Python-list