Méthode efficace pour extraire et collecter un sous-échantillon aléatoire d'un générateur dans Julia

Question

Considérons un générateur dans Julia qui, s'il est collecté, prendra beaucoup de mémoire.

g=(x^2 for x=1:9999999999999999)

Je veux prendre un petit sous-échantillon aléatoire (Disons 1%), mais je ne veux pas collecter() l'objet car cela prendrait beaucoup de mémoire.

Jusqu'à présent, l'astuce que j'utilisais était la suivante

temp=collect((( rand()>0.01 ? nothing : x ) for x in g))
random_sample= temp[temp.!=nothing]

Mais ce n'est pas efficace pour les générateurs avec beaucoup d'éléments, collecter quelque chose avec autant d'éléments vides ne semble pas correct.

Toute idée est la bienvenue. Je suppose que l'astuce est de pouvoir obtenir des éléments aléatoires du générateur sans avoir à allouer de la mémoire pour l'ensemble.

Merci beaucoup.

Answer 1

Vous pouvez utiliser un générateur avec if condition comme celle-ci :

[v for v in g if rand() < 0.01]

ou si vous souhaitez une approche un peu plus rapide, mais plus verbeuse (j'ai codé en dur 0.01 et le type d'élément de g et je suppose que votre générateur supporte length - sinon vous pouvez supprimer sizehint! ligne) :

function collect_sample(g)
    r = Int[]
    sizehint!(r, round(Int, length(g) * 0.01))
    for v in g
        if rand() < 0.01
           push!(r, v)
        end
    end
    r
end

EDIT

Vous avez ici des exemples d'échantillonneur à évitement automatique et d'échantillonneur à réservoir vous donnant une taille de sortie fixe. Plus la fraction de l'entrée que vous voulez obtenir est petite, plus il est préférable d'utiliser un échantillonneur à évitement automatique :

function self_avoiding_sampler(source_size, ith, target_size)
    rng = 1:source_size
    idx = rand(rng)
    x1 = ith(idx)
    r = Vector{typeof(x1)}(undef, target_size)
    r[1] = x1
    s = Set{Int}(idx)
    sizehint!(s, target_size)
    for i = 2:target_size
        while idx in s
            idx = rand(rng)
        end
        @inbounds r[i] = ith(idx)
        push!(s, idx)
    end
    r
end

function reservoir_sampler(g, target_size)
    r = Vector{Int}(undef, target_size)
    for (i, v) in enumerate(g)
        if i <= target_size
            @inbounds r[i] = v
        else
            j = rand(1:i)
            if j < target_size
                @inbounds r[j] = v
            end
        end
    end
    r
end