grep或拼接在大陣列上

Question

我有大量的散列，大約0.5Gb，存儲在內存中，我需要從中刪除一些元素，大約10％分佈在整個陣列周圍。

什麼是最有效的工作最好，做一個grep，或確定需要刪除的元素，並將它們拼接出來？

感謝，

西蒙娜

Answer 1

splice可能會在您描述的條件下（因爲它會移動數組內容）轉到O（n^2），並且grep/slice會分配O（n）額外的內存（可能遠遠小於500GB，但仍然會）。 ..）。

沒有與雖然沒有額外的內存線性解決方案，但看起來更象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 2

如果你已經知道你是哪個元素感興趣消除，這將是通過定義，你不會有搜索表單他們更快，只有將其刪除。否則，grep是您快速過濾方法的最佳選擇。

Answer 3

基準嗎？我猜想，不知道你的數據真的是什麼樣子，grep會比多次調用拼接一個有很多元素的數組要快。

Answer 4

如果你知道你想要的元素保持，那麼你可以使用數組切片對其進行索引：

@want = @all[ @wanted ]; 

或

@all = @all[ @wanted ]; 

至於其中的grep和接頭是最快的，splice將是最快的，因爲它需要做的只是在C中移動一些指針，並刪除你不再從內存中保存的東西，grep需要更多的工作，因爲它需要一個請致電您的選擇功能爲每個原始列表的成員。