Эффективный способ извлечь и собрать случайную подвыборку генератора в Юлии - PullRequest
Новая
       25

Эффективный способ извлечь и собрать случайную подвыборку генератора в Юлии

2 голосов
/ 18 мая 2019

Рассмотрим генератор в Юлии, который, если его собрать, займет много памяти 

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

Я хочу взять случайную небольшую подвыборку (скажем, 1%), но я не хочу собирать () объект, потому что он займет много памяти

До сих пор я использовал трюк 

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

Но это неэффективно для генераторов с большим количеством элементов, сбор чего-либо с таким количеством элементов ничего не кажется правильным

Любая идея высоко ценится. Я предполагаю, что хитрость заключается в том, чтобы иметь возможность получать случайные элементы из генератора без необходимости выделять память для всего этого.

Большое спасибо

1 Ответ

2 голосов
/ 18 мая 2019

Вы можете использовать генератор с условием if, например: 

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

или если вы хотите немного более быстрый, но более подробный подход (я жестко закодировал 0.01 и тип элемента g, и я предполагаю, что ваш генератор поддерживает length - в противном случае вы можете удалить строку sizehint!): 

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

Здесь у вас есть примеры самозапускающегося пробоотборника и пробоотборника резервуара, дающего вам фиксированный выходной размер. Чем меньше доля ввода, которую вы хотите получить, тем лучше использование самозапускающегося сэмплера: 

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
...