`calculate_eltype(iter)` produces wrong type inference

[dmetivie]

I am trying to use this package to sample from Combinatorics.jl objects (which typically produce super large iterator you don't want to collect, thus your package is perfect!).

The following works, but the result is a Vector{Any} instead of Vector{Vector{Int64}}

X = 1:6
k = 2
iter = multiset_combinations(X, k)
itsample(iter, 2; replace = false, ordered = false)

if we do

itsample(iter, 20; replace = false, ordered = false) # ask for more element than the 15 in the iter

it errors ERROR: TypeError: in typeassert, expected Vector{Any}, got a value of type Vector{Vector{Int64}}

I believe this is due to usage of calculate_eltype(iter) i.e. Base.@default_eltype(iter).

[Tortar]

Cool! you asked at the right time because I did a major refactoring of the library and now it is much more flexible i.e. in your case you can do

using StreamSampling, Combinatorics

X = 1:6
k = 2
iter = multiset_combinations(X, k)

rs = ReservoirSample(Vector{Int}, 20)

for x in iter
    update!(rs, x)
end

value(rs) # this contains the sample values collected

it is still in the process of registration (JuliaRegistries/General#105117) because I changed the name from IteratorSampling to StreamSampling so it will take some days, but you can use the dev version

[Tortar]

anyway, maybe calculate_eltype could be further refined by checking if it does infer Any and in that case call eltype

[Tortar]

Now also itsample computes the right type :-)

[Tortar]

Hi @dmetivie, I'd like to ask you if you found this library useful in the end in your work, I ask because I'd like to publish it in JOSS and I'm thinking of possible applications where this kind of methods could be useful, so it would be really great if you had some more insights on what you found helpful. Hope you’ve been doing well, and thanks in advance for any feedback you can share!

[dmetivie]

Hi, Funny you ask because now I just retried your packages last Friday.
My goal was to sample from a huge combinatorial set for Monte Carlo exploration.
However, I am not sure that I fully grasp what StreamSampling.jl was for. To me, it allows to sample from iterators (possibly to big to be collected).
I tried using it like that. For small-ish sets this was indeed faster but for larger ones e.g. bellow, it seems the same as collect (and for even larger I am not sure).

using StreamSampling, Combinatorics

X = 1:60
k = 5
iter = multiset_combinations(X, k)
length(iter)
@btime itsample(iter, 2)
  20.951 s (22986712 allocations: 2.02 GiB)
@btime sample(iter |> collect, 2)
18.663 s (54615209 allocations: 4.44 GiB)

Did I mis understood the package usage?

In any case, it would be great to have more examples and probably more context/comments/plots on the illustrative example (maybe with a real dataset) for naive user (as myself).
Thanks

[Tortar]

Ahah what a coincidence! Your goal and the usage of this library are sensibly connected but unfortunately Combinatorics.jl still needs improvements to integrate well with this library. The reason is that the iterator itself for multiset_combinations is allocating, so even if you don't collect it you still have a lot of time passing allocating vectors of combinations, this can be seen by the fact that there are 22986712 allocations even when you use itsample which wouldn't happen if instead the iterator was not allocating e.g.

julia> a = (x for x in 1:10^9 if x != 1);

julia> using StreamSampling

julia> @time itsample(a, 2);
  0.718155 seconds (2 allocations: 80 bytes)

julia> using StatsBase

julia> @time sample(collect(a), 2);
 19.854985 seconds (57 allocations: 31.871 GiB, 18.85% gc time)

so if you reimplemented multiset_combinations not to allocate every time a new vector (e.g. use tuples instead) then you would see a big speed-up (probably less than this because the iterator would still be more complex than this simple one). Though for very big multiset_combinations at least you can't go out of memory with StreamSampling.jl (but it is so slow currently that it would take a very long time to happen anyway ahah) because while the iterator is allocating the memory usage is "smooth" without collect.

Yeah, anyway, my package is still not very good in terms of examples, and I need to add more, I still need good examples to show its usefulness, but maybe starting with a elementary example where I say that it is good for (fast) iterators is a start. I should probably read some more literature on stream sampling for applications though.

[dmetivie]

Thanks for the explanation! It now makes sense indeed the implementation of multiset_combinations does allocate.
Maybe in addition to more examples you could:

1. (harder) make some contributions in packages producing interesting iterators like Combinatorics.jl (only one that comes to mind) to make them non allocating, so they are more compatible with your package (and that should not break the original package). This will provide diverse examples for your package in addition to a new Julia package composability showcase.
2. Make a warning note about this allocating issue + provide examples of construction of non allocating iterators. So that people interested in itsample can try to cook their own if needed.

good luck thanks for the work