Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #50388
| References | (1 earlier) <15167633-b6e7-46cc-a043-8dfe8aaad11e@googlegroups.com> <mailman.4525.1373469147.3114.python-list@python.org> <ff09d214-1962-4500-a2a3-483872ce2cb9@googlegroups.com> <CAPTjJmqY6_gaGqvRSYzccWU1EjHPFxYkWWXHhPcwE+iZoDW2zg@mail.gmail.com> <CAN1F8qXajvvpUjFnMNRzQiBbvrPUz4b9QXck1RRNhWJYxkQDhw@mail.gmail.com> |
|---|---|
| From | Ian Kelly <ian.g.kelly@gmail.com> |
| Date | 2013-07-10 12:56 -0600 |
| Subject | Re: Prime number generator |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.4545.1373482626.3114.python-list@python.org> (permalink) |
On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau <joshua@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). > 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.
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 00:00 +1000
Re: Prime number generator Bas <wegwerp@gmail.com> - 2013-07-10 07:35 -0700
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 01:12 +1000
Re: Prime number generator bas <blswinkels@gmail.com> - 2013-07-10 08:47 -0700
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:15 +1000
Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 18:47 +0100
Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 12:56 -0600
Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 20:06 +0100
Re: Prime number generator bryanjugglercryptographer@yahoo.com - 2013-07-30 21:57 -0700
Re: Prime number generator Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-10 16:01 +0000
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:52 +1000
Re: Prime number generator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-30 10:58 +0000
Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-30 11:33 -0600
csiph-web