Prime number generator

[Joshua Landau]

On 10 July 2013 19:56, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau <joshua at landau.ws> wrote:
>>>> If you care about speed, you might want to check the heapq module. Removing the smallest item and inserting a new item in a heap both cost O(log(N)) time, while finding the minimum in a dictionary requires iterating over the whole dictionary, which cost O(N) time.
>>
>> Actually, because it's a list under the hood I'd imagine push and pop
>> still take O(n) time :/.
>
> It shouldn't.  You can implement push by appending the new item and
> then getting it into the right place by performing O(log n) swaps.
> Likewise for pop, you can update the heap with O(log n) swaps and then
> removing the tail element.  Appending or removing the tail element of
> a list is amortized O(1).

Genius. Bas replied off-list that it won't matter too much anyway as
they're over-allocated, but this makes tons of sense.

>> PS: It's faster to use heapreplace(...) than
>> heappop(...);heappush(...) but it only saves a few %.
>
> The problem with heapreplace here is that the value to be pushed
> is dependent on the value returned by pop.

That's fine because indexing is much faster than pop. The "few %" was
a real statistic from working, timed code.