[Haskell-cafe] ANN: combinatorics
Daniel Fischer
daniel.is.fischer at googlemail.com
Sun Feb 5 16:21:45 CET 2012
On Wednesday 01 February 2012, 07:53:03, wren ng thornton wrote:
> > The primes function in the combinat package is based on an old Cafe
> > thread, and actually seems to be faster than the one in the
> > combinatorics package.
Yes, but it has a memory leak. On my box at least, with ghc 6.12, 7.0 and
7.2.
>
> The primes generator was some old code I had laying around for one of
> those online programming challenges; fast enough for the task.
> I'll probably trade it in for your algorithm though.
Why not use one of the packages on hackage which offer faster prime
generators?
I'm aware of the following usable packages:
- primes: decentish performance if you don't need to sieve high, but not
recommendable if you want to sieve above ~10^7, in my measurements about
the same performance as the algorithm used in combinat, but without memory
leak.
- NumberSieves: The O'Neill sieve, about twice as fast as the primes sieve,
uses less memory (and scales better if you want to sieve to higher limits).
- arithmoi: A segmented Eratosthenes sieve using mutable unboxed arrays.
Much faster than the above and uses less memory.
If you don't like arrays, it also has a priority queue sieve similar to the
O'Neill sieve, but with a more efficient PQ implementation.
> One of the things
> I'm disappointed by about the current implementation is the memory
> overhead for storing the primes. It'd be nice to use chunked arrays of
> unboxed integers in order to remove all the pointers; but my attempt at
> doing so had catastrophic performance...
arithmoi's Eratosthenes sieve offers the option to get a list of sieve
chunks, basically UArray Int Bool, which gives far more compact storage
than a list of Integers (~33KB per million range, much more compact than an
unboxed array of primes for the reachable ranges) from which the list of
primes can rather efficiently obtained when needed. That may do what you
want well enough.
Cheers,
Daniel
More information about the Haskell-Cafe
mailing list