Combinatorics.jl
Combinatorics.jl copied to clipboard
Improve partitions performance
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 asVector{Int8}in this case); - For consistency,
partitions(0)returns[Int[]]andpartitions(-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 withcollect(partitions(n))).