perl – 大型数组上的grep或splice

发布时间：2020-12-16 06:18:27 所属栏目：大数据来源：网络整理

导读：我有一大堆哈希值,大约0.5Gb,存储在内存中,我需要从中删除一些元素,大约10％遍布整个数组. 什么是最有效的工作,做grep,或识别需要删除的元素,并将它们拼接出去？谢谢, 西蒙娜解决方法 splice可以在你描述的条件下(当它移动数组内容时)转到O(n ^ 2),而grep

我有一大堆哈希值,大约0.5Gb,存储在内存中,我需要从中删除一些元素,大约10％遍布整个数组.

什么是最有效的工作,做grep,或识别需要删除的元素,并将它们拼接出去？

谢谢,

西蒙娜

解决方法

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'

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!