使用Perl检查数据数组中重复项的最有效方法是什么？

Question

我需要看一下字符串数组中是否有重复项,这是最省时的方法吗？

Answer 1

我喜欢Perl的一个原因是它能够像英语一样阅读.这有点道理.

use strict;
use warnings;

my @array = qw/yes no maybe true false false perhaps no/;

my %seen;

foreach my $string (@array) {

    next unless $seen{$string}++;
    print "'$string' is duplicated.\n";
}

产量

'false' is duplicated.

'no' is duplicated.

Answer 2

将数组转换为哈希是最快的方式[ O(n)],尽管它的内存效率低下.使用for循环比grep快一点,但我不知道为什么.

#!/usr/bin/perl

use strict;
use warnings;

my %count;
my %dups;
for(@array) {
    $dups{$_}++ if $count{$_}++;
}

一种有效的内存方法是对数组进行排序并遍历它,寻找相等和相邻的条目.

# not exactly sort in place, but Perl does a decent job optimizing it
@array = sort @array;

my $last;
my %dups;
for my $entry (@array) {
    $dups{$entry}++ if defined $last and $entry eq $last;
    $last = $entry;
}

这是nlogn速度,因为排序,但只需要存储重复项而不是数据的第二个副本%count.最坏的情况下内存使用仍然是O(n)(当所有内容都重复时)但是如果你的阵列很大并且没有很多重复,那么你将获胜.

除了理论之外,基准测试显示后者开始在大型阵列(如超过一百万)上丢失,并且重复率很高.

Answer 3

如果你还需要unquified数组,最快使用经过大量优化的库List :: MoreUtils,然后将结果与原始数据进行比较:

use strict;
use warnings;
use List::MoreUtils 'uniq';

my @array = qw(1 1 2 3 fibonacci!);
my @array_uniq = uniq @array;
print ((scalar(@array) == scalar(@array_uniq)) ? "no dupes" : "dupes") . " found!\n";

或者,如果列表很大并且您希望在找到重复条目后立即保释,请使用哈希:

my %uniq_elements;
foreach my $element (@array)
{
    die "dupe found!" if $uniq_elements{$element}++;
}

Answer 4

创建哈希或集合或使用collections.Counter().

当您遇到每个字符串/输入检查以查看哈希中是否存在该实例时.如果是这样,它就是重复的(做你想做的任何事情).否则,使用字符串作为键,将值(例如,哦,例如,数字1)添加到散列.

示例(使用Python collections.Counter):

#!python
import collections
counts = collections.Counter(mylist)
uniq = [i for i,c in counts.iteritems() if c==1]
dupes = [i for i, c in counts.iteritems() if c>1]

这些计数器是围绕字典构建的(用于散列映射集合的Pythons名称).

这是时间有效的,因为散列键被索引.在大多数情况下,键的查找和插入时间是在接近恒定的时间内完成的.(实际上Perl"哈希"是所谓的,因为它们是使用称为"哈希"的算法技巧实现的 - 一种校验和选择,因为它在输入任意输入时具有极低的冲突概率).

如果将值初始化为整数,从1开始,则可以在散列中找到其键时递增每个值.这是计算字符串的最有效的通用方法.