Perl：使用 'splice()' VS 链表的数组插入性能

我有一个使用Perl数组的脚本。每个数组包含数十万个项。

我经常需要动态地在数组中间添加项，或者从数组中删除项。

我想了解是否应该使用链表而不是Perl数组，因为我经常进行插入和删除

我的问题是:

splice()是如何实现的?
在Perl数组索引i中插入x项时，splice()的复杂度是多少
你能推荐一个你用过的Perl链表模块吗?

谢谢!

Perl数组存储为指针、开始偏移量、长度和分配长度的数组。

因此，从中间插入或删除将需要移动4或8字节乘以数组中后面元素的数量。从任何一端删除都不需要移动任何东西，只需调整开始偏移量或长度。在末尾插入通常只需要调整长度，但偶尔需要重新分配整个指针数组。在开始插入时，perl会尽力安排，以便只需要调整开始偏移量，但有时整个数组需要移动甚至重新分配。

在实践中，使用perl操作创建和管理链表的开销几乎在任何情况下都比仅仅使用数组要大得多。

要对它进行基准测试，我们需要更多地了解您的特定情况;数组的实际大小，元素的类型和大小(与拼接的成本无关，但可能与链表相关)，插入/删除的相对频率等

做了一个快速的拼接基准测试，对于删除和插入，它似乎都表现为O(N)。

脚本:

my $length = shift;
my $toSplice = 100;
my @list = (1 .. $length);
my $t0 = Time::HiRes::time();
for(1 .. $toSplice) {
    my $removeIdx = int(rand() * @list);
    splice @list, $removeIdx, 1;
}
my $t1 = Time::HiRes::time();
for(1 .. $toSplice) {
    my $insertIdx = int(rand() * @list);
    splice @list, $insertIdx, 0, 0;
}
printf("Took %.4fs to removen", $t1 - $t0);
printf("Took %.4fs to insertn", Time::HiRes::time() - $t0);

结果:

$ perl test.pl 100000
Took 0.0026s to remove
Took 0.0092s to insert
$ perl test.pl 1000000
Took 0.0296s to remove
Took 0.0617s to insert
$ perl test.pl 10000000
Took 0.2876s to remove
Took 0.6252s to insert

因此，迭代次数增加10倍，运行时间大约增加10倍。

您对数组和链表的基准测试是有缺陷的。可以使用以下命令加速arrays方法:

创建一个标量数组，而不是多余的哈希引用数组来匹配链表。
因为你只是做一个列表的单遍，创建一个新的列表，而不是试图拼接旧的列表。

这将使速度提高10倍。

当然这会使内存翻倍，但是使用链表至少会使内存增加5倍。

下面是显示这两个改进的基准测试。我还简化了链表功能，但数组方法的速度仍然是两倍，即使改进了这两种方法。

use strict;
use warnings;
use Benchmark;
my $INSERTION_FREQUENCY = 5;
my $num_of_items = shift or die "Specify size of listn";
timethese(10, {
    'linked_list'  => sub { linked_list($num_of_items) },
#   'array_splice' => sub { array_splice($num_of_items) },
    'array_map'    => sub { array_map($num_of_items) },
});
sub linked_list {
    my $count = shift;
    my $curr_node = my $list_head = {data => 1};
    # Creating List 
    for my $i (2 .. $num_of_items) {
        $curr_node = $curr_node->{next} = {
            data => $i,
            prev => $curr_node,
        };
    }
    # Inserting Items
    $curr_node = $list_head;
    my $i = 0;
    while ($curr_node) {
        if (++$i % $INSERTION_FREQUENCY == 0) {
            my %new_node = (
                data => "inserted",
                prev => $curr_node->{"prev"},
                next => $curr_node,
            );
            $curr_node->{"prev"}{"next"} = %new_node if $curr_node->{"prev"};
            $curr_node->{"prev"} = %new_node;
        }
        $curr_node = $curr_node->{"next"};
    }
    return $list_head;
}
sub array_splice {
    my $num_of_items = shift;
    # Creating Array
    my @array = (1..$num_of_items);
    # Inserting Items
    for my $i (1 .. $num_of_items) {
        if ($i % $INSERTION_FREQUENCY == 0) {
            splice(@array, $i - 1, 0, "inserted");
        }
    }
    return @array;
}
sub array_map {
    my $num_of_items = shift;
    # Creating Array
    my @array = (1..$num_of_items);
    # Inserting Items
    my $i = 0;
    @array = map {
        ++$i % $INSERTION_FREQUENCY == 0 ? ("inserted", $_) : $_
    } @array;
    return @array;
}

基准

$ perl arrays.pl 100000
Benchmark: timing 10 iterations of array_map, array_splice, linked_list...
 array_map:  1 wallclock secs ( 0.58 usr +  0.01 sys =  0.59 CPU) @ 16.89/s (n=10)
array_splice: 16 wallclock secs (16.21 usr +  0.00 sys = 16.21 CPU) @  0.62/s (n=10)
linked_list:  2 wallclock secs ( 1.43 usr +  0.09 sys =  1.53 CPU) @  6.54/s (n=10)
$ perl arrays.pl 200000
Benchmark: timing 10 iterations of array_map, array_splice, linked_list...
 array_map:  1 wallclock secs ( 1.20 usr +  0.05 sys =  1.25 CPU) @  8.01/s (n=10)
array_splice: 64 wallclock secs (64.10 usr +  0.03 sys = 64.13 CPU) @  0.16/s (n=10)
linked_list:  3 wallclock secs ( 2.92 usr +  0.23 sys =  3.15 CPU) @  3.17/s (n=10)
$ perl arrays.pl 500000
Benchmark: timing 10 iterations of array_map, linked_list...
 array_map:  4 wallclock secs ( 3.12 usr +  0.36 sys =  3.48 CPU) @  2.87/s (n=10)
linked_list:  8 wallclock secs ( 7.52 usr +  0.70 sys =  8.22 CPU) @  1.22/s (n=10)

我也做了一个基准测试，想和大家分享一下结果。

在我得到的结果中，链接列表比Perl数组快得多。

这是我做的基准测试:

创建一个包含1M项的链表或数组
遍历列表/数组并在适当位置插入200K
检查每个场景花费的时间。

链表:2秒
Perl-array: 1:55min

我和你分享代码:

运行命令和结果:

> time perl_benchmark.pl list 1000000
1.876u 0.124s 0:02.01 99.0%     0+0k 0+0io 0pf+0w
> time perl_benchmark.pl array 1000000
115.159u 0.104s 1:55.27 99.9%   0+0k 0+0io 0pf+0w

源代码:

my $INSERTION_FREQUENCY = 5;
my $use_list = $ARGV[0] eq "list";
my $num_of_items = $ARGV[1];
my $list_header;
my $list_tail;
my @array;
# Creating List or Array
for (my $i = 0 ; $i < $num_of_items ; $i++) {
    my %new_node;
    $new_node{"data"} = $i;
    if ($use_list) {        
        if (! defined($list_header)) {
            $list_header = $list_tail = %new_node;
        } else {
            $new_node{"prev"} = $list_tail;
            $list_tail->{"next"} = %new_node;          
            $list_tail = %new_node;
        }
    } else {
        push(@array, %new_node);
    }
}
# Inserting Items
my $curr_node = $list_header;
for (my $i = 1 ; $i < $num_of_items ; $i++) {
    if ($i % $INSERTION_FREQUENCY == 0) {
        my %new_node;
        $new_node{"data"} = "inserted";
        if ($use_list) {
            my $prev_ptr = $curr_node->{"prev"};
            if (defined($prev_ptr)) {
                $prev_ptr->{"next"} = %new_node;
            }
            $new_node{"prev"} = $prev_ptr;
            $new_node{"next"} = $curr_node;
            $curr_node->{"prev"} = %new_node
        } else {
            splice(@array, $i - 1, 0, %new_node);
        }
    }
    if ($use_list) {
        $curr_node = $curr_node->{"next"};
    }
}

相关内容

最新更新

热门标签：