grep или склейка на большом массиве

Question

У меня большой массив хэшей, около 0,5 Гб, хранящийся в памяти, и мне нужно удалить из него некоторые элементы, около 10% распределенных по всему массиву.

Что может быть лучше для работы, делать grep или определять элементы, которые нужно удалить, и объединить их?

Спасибо

Simone

Answer 1

Тест это?Я бы догадался, не зная, как на самом деле выглядят ваши данные, что grep будет быстрее, чем множественные вызовы склейки для массива с большим количеством элементов.

Answer 2

Если вы знаете, какие элементы вы хотите сохранить , то вы можете просто проиндексировать их с помощью фрагмента массива:

@want = @all[ @wanted ];

или

@all = @all[ @wanted ];

Какк которому из grep и сращивания самое быстрое, splice будет самым быстрым, так как все, что ему нужно сделать, это переместить некоторые указатели в C и удалить вещи, которые вы больше не храните в памяти, grep потребуетсянемного больше работы, так как для этого требуется вызов функции выбора для каждого члена исходного списка.

Answer 3

splice может перейти к O (n ^ 2) в условиях, которые вы описываете (поскольку он перемещает содержимое массива), а grep / slice выделит O (n) дополнительной памяти (возможно, намного меньше, чем 500 ГБ,но до сих пор...).

Существует линейное решение без дополнительной памяти, но оно больше похоже на C, чем на Perl:

sub inplace_grep {
    my ($code, $array) = @_; 
    # move elements backwards
    for (my ($to, $from)=(0,0); $from < @$array; $from++) {
        $code->($array->[$from]) or next;
        $array->[$to++] = $array->[$from];
    };
    # remove tail 
    splice @$array, $to; 
};

Обновление: при использовании памяти grep - выможет выполнить быструю проверку на выделение дополнительной памяти, используя большие объемы данных и ища системный вызов brk.В моей системе (Linux, Perl 5.10) это так.

strace -e trace=brk perl -MTime::HiRes -wle \
'print "start ".time; my @array = 1..10**7; print "alloc ".time;
@array = grep { $_ %2 } @array; print "grep ".time'

Answer 4

Если вы уже знаете, какие элементы вы заинтересованы в удалении, это будет по определению быстрее, поскольку вам не придется искать их по форме, только удалите их. В противном случае grep - лучший выбор для метода быстрой фильтрации.