Paul Rubin wrote:
> Oh, I see what you mean. I don't see an obvious faster way to do it
> and I don't have the feeling that one necessarily exists. As someone
> mentioned, you could do an n-way merge, which at least avoids using
> quadratic memory. Here's a version using Frederik Lundh's trick
Anton Vredegoor <[EMAIL PROTECTED]> writes:
> I want the product, but sorted in less time. If Fourier transforms can
> help, I want them :-)
Oh, I see what you mean. I don't see an obvious faster way to do it
and I don't have the feeling that one necessarily exists. As someone
mentioned, you cou
Terry Reedy wrote:
> 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).
Terry Reedy wrote:
> 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).
"Anton Vredegoor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
| Terry Reedy wrote:
|
| > 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
Terry Reedy wrote:
> 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 imp
"Anton Vredegoor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
| 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
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 n
Anton Vredegoor <[EMAIL PROTECTED]> writes:
> Presorting the second sequence gains us more than three seconds. I
> wonder if there is a way to generate the combined items in such a way
> that sorting them is even faster? Is there some other sorting
> algorithm that can specifically take advantage o
On Mar 28, 12:12 pm, Anton Vredegoor <[EMAIL PROTECTED]>
wrote:
> Python's sorting algorithm takes advantage of preexisting order in a
> sequence:
>
> #sort_test.py
> import random
> import time
>
> def test():
> n = 1000
> k = 2**28
>
> L = random.sample(xrange(-k,k),n)
> R = r
10 matches
Mail list logo
