# Best way to store integer partitions
**URL:** https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276
**Category:** Performance
**Created:** [December 14, 2019, 4:20pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276 "2019-12-14T16:20:52Z")
**Posts on this page:** 7
**Page:** 1
### Author:  [@Tqft](https://discourse.julialang.org/u/Tqft)
#### Post date: [December 14, 2019, 4:20pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/1 "2019-12-14T16:20:52Z")
This is just a toy example but I was wondering what the best (memory and performance wise) way is to store partitions of a fixed integer n, i.e. lists of positive integers which sum up to n.
Currently, I’m using Array{Int8,1} for the partitions and Array{Array{Int8,1},1} to store all the partitions. But I think this is not optimal.
julia\> @time P = partitions(10)
0.000011 seconds (53 allocations: 5.328 KiB)
julia\> @time P = partitions(90)
4.301507 seconds (56.63 M allocations: 6.239 GiB, 34.52% gc time)
This is quite a lot of memory allocated compared to what I actually have to store. The number of partitions of 90 for example is 56634173, so this is much less than 56634173\*90/1000^3 = 5.1GiB of data (ignoring pointers etc.).
What’s the best way to do this?
---
### Author:  [@leiteiro](https://discourse.julialang.org/u/leiteiro)
#### Post date: [December 14, 2019, 6:28pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/2 "2019-12-14T18:28:59Z")
If this fits your needs better:
```
n = 100: 167.598273 seconds (15 allocations: 4.813 KiB)
```
then look at
[https://github.com/OpenLibMathSeq/IntegerSequences.jl/blob/master/src/Partitions.jl](https://github.com/OpenLibMathSeq/IntegerSequences.jl/blob/master/src/Partitions.jl)
---
### Author:  [@Tqft](https://discourse.julialang.org/u/Tqft)
#### Post date: [December 14, 2019, 7:03pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/3 "2019-12-14T19:03:47Z")
Interesting, thank you. But I fear this is useless. This implementation does not store the partitions, it just prints (visits) them. In fact, in the code for the benchmark you find the comment “# – first comment out println in VISIT”.
This would be equivalent to not push the partitions into the array. If I just do the visit, I’m a bit more efficient:
julia\> @time P = partitions(100)
0.250746 seconds (8 allocations: 576 bytes)
But that’s not the point.
---
### Author:  [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)
#### Post date: [December 14, 2019, 7:11pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/4 "2019-12-14T19:11:13Z")
What I don’t really understand is that you show the results from `@time` but that gives the total number of allocations in the algorithm that creates `P` but doesn’t say much about the size of `P` itself. Maybe you just do a bunch of non-needed allocations in `partitions`?
---
### Author:  [@Tqft](https://discourse.julialang.org/u/Tqft)
#### Post date: [December 14, 2019, 7:46pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/5 "2019-12-14T19:46:32Z")
How can I get the actual size of P? I tried
julia\> P=partitions(2)
2-element Array{Array{Int8,1},1}:
[2]
[1, 1]
julia\> sizeof( P)
16
julia\> Base.summarysize( P)
139
So, maybe it’s 16 bytes for 3 8-bit integers plus pointers etc!? I don’t know what summarysize is.
I checked allocations using `julia --track-allocation=user` and as far as I can tell the only allocations came from the `push!(P,part)` for each partition found.
---
### Author:  [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)
#### Post date: [December 14, 2019, 8:02pm UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/6 "2019-12-14T20:02:42Z")
Instead of storing things as `[[1,1,1], [1, 2], [3]]` you could store it as
```julia
data = [1, 1, 1, 1, 2, 3]
offsets = [1, 4, 6, 7]
```
and then you get the offsets at `i` as `data[offsets[i]:offsets[i+1]-1]`. Would save you all the overhead from a bunch of small arrays.
---
### Author:  [@Tqft](https://discourse.julialang.org/u/Tqft)
#### Post date: [December 15, 2019, 9:04am UTC](https://discourse.julialang.org/t/best-way-to-store-integer-partitions/32276/7 "2019-12-15T09:04:23Z")
This sounds like a very good idea, cheers.