Hpw make lists that are easy to sort.
tjreedy at udel.edu
Thu Mar 29 00:37:09 CEST 2007
"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message
news:euenlj$oll$1 at news4.zwoll1.ov.home.nl...
| Paul Rubin wrote:
| > Well there are various hacks one can think of, but is there an actual
| > application you have in mind?
| Suppose both input lists are sorted. Then the product list is still not
| sorted but it's also not completely unsorted. How can I sort the
| product? I want to know if it is necessary to compute the complete
| product list first in order to sort it. Is it possible to generate the
| items in sorted order using only a small stack?
If you have lists A and B of lengths m and n, m < n, and catenate the m
product lists A*B, A*B, ..., A[m-1]*B, then list.sort will definitely
take advantage of the initial order in each of the m sublists and will be
faster than sorting m*n scrambled items (which latter is O(m*n*log(m*n))).
One could generate the items in order in less space by doing, for instance,
an m-way 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.
Terry Jan Reedy
More information about the Python-list