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 remove\n", $t1 - $t0);
printf("Took %.4fs to insert\n", 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
4条答案
按热度按时间dldeef671#
Perl数组存储为指针数组、起始偏移量、长度和分配的长度。
所以从中间插入或删除需要移动4或8个字节乘以数组中后面的元素数。从两端删除不需要移动任何东西,只需要调整开始的偏移量或长度。在末尾插入通常只需要调整长度,但偶尔需要重新分配整个指针数组。在开头插入,perl将尽最大努力进行安排,以便只需要调整开始的偏移量,但有时需要移动甚至重新分配整个数组。
在实践中,使用perl操作创建和管理链表的开销几乎在每种情况下都要比仅仅使用数组大得多。
为了确定基准,我们需要更多地了解您的具体情况;数组的实际大小、元素的种类和大小(与拼接成本无关,但可能与链表有关)、插入/删除的相对频率等。
hl0ma9xz2#
做了一个快速的拼接基准测试,它似乎表现为O(N)的删除和插入。
脚本:
结果:
因此,迭代次数增加10倍,运行时间大约增加10倍。
lsmepo6l3#
数组和链表的基准测试存在缺陷。数组方法可以使用以下方法加速:
1.创建一个标量数组来代替多余的哈希引用数组,以匹配链表。
这将执行速度提高了4倍。
1.由于您只是对列表执行一次传递,因此创建一个新列表,而不是尝试拼接旧列表。
这将使速度提高10倍。
当然,这会使内存加倍,但使用链表至少会使内存增加5倍。
下面的基准测试显示了这两个改进。我还简化了链表功能,但是即使对这两个功能都进行了改进,数组方法的速度仍然是原来的两倍。
基准测试
zlwx9yxi4#
我还做了一个基准测试,并希望与您分享结果。
在我得到的结果中,链表比Perl数组快得多。
这是我做的基准测试:
1.创建了一个链接列表或一个包含100万个条目的数组
1.迭代列表/数组并在适当位置插入200 K
1.检查每个场景所需的时间。
链接列表:2秒
Perl数组:1分55秒
我与您分享代码:
运行命令和结果:
源代码: