Combinatorics.jl icon indicating copy to clipboard operation
Combinatorics.jl copied to clipboard

Improve partitions performance

Open jieaosong opened this issue 4 years ago • 0 comments

Here are some timings for comparison. before

julia> @btime collect(partitions(10));
  3.995 μs (85 allocations: 6.12 KiB)

julia> @btime collect(partitions(30));
  772.853 μs (11210 allocations: 1017.45 KiB)

julia> @btime collect(partitions(50));
  35.195 ms (408454 allocations: 42.44 MiB)

after

julia> @btime collect(partitions(10));
  1.467 μs (44 allocations: 5.53 KiB)

julia> @btime collect(partitions(30));
  222.300 μs (5607 allocations: 930.16 KiB)

julia> @btime collect(partitions(50));
  10.732 ms (204229 allocations: 39.36 MiB)

This is about the same speed as JuLie.partitions or AbstractAlgebra.Generic.partitions. Also the algorithm is fairly simple and straightforward :)

Some other remarks

  • Use type parameter so one can use partitions(Int8(n)) to save some memory for large n (the partitions are generated as Vector{Int8} in this case);
  • For consistency, partitions(0) returns [Int[]] and partitions(-1) returns an empty iterator (this is treated in #82 but has not been merged);
  • Added deprecation warning for integer_partitions (which I'd suggest to replace completely with collect(partitions(n))).

jieaosong avatar Aug 25 '21 08:08 jieaosong