Каков наиболее эффективный способ проверки дубликатов в массиве данных с помощью Perl?

Ответ 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.

Ответ 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) (когда все дублируется), но если ваш массив большой и не много дубликатов, вы выиграете.

Теория в сторону, бенчмаркинг показывает, что последний начинает терять на больших массивах (например, более миллиона) с высоким процентом дубликатов.

Ответ 3

Если вам все равно нужен уникальный массив, он быстрее всего использует сильно оптимизированную библиотеку 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}++;
}

Ответ 4

Создайте хэш или набор или используйте collections.Counter().

Как вы сталкиваетесь с каждой проверкой строки/ввода, чтобы увидеть, есть ли экземпляр этого в хеше. Если это так, это дубликат (делайте все, что вы хотите о них). В противном случае добавьте значение (например, о, скажем, числовое) в хэш, используя строку в качестве ключа.

Пример (с использованием 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, то вы можете увеличить каждое значение, когда вы найдете его ключ уже в хеше. Это всего лишь наиболее эффективное средство общего подсчета строк.

Ответ 5

Не прямой ответ, но он вернет массив без дубликатов:

#!/usr/bin/perl

use strict;
use warnings;

my @arr = ('a','a','a','b','b','c');
my %count;
my @arr_no_dups = grep { !$count{$_}++ } @arr;

print @arr_no_dups, "\n";

Ответ 6

Пожалуйста, не спрашивайте о наиболее эффективном способе делать что-либо, если у вас нет каких-либо конкретных требований, таких как "Я должен дедупировать список из 100 000 целых чисел за секунду". В противном случае вы беспокоитесь о том, как долго что-то берется без причины.

Ответ 7

похож на второе решение @Schwern, но проверяет дубликаты немного раньше из функции сравнения sort:

use strict;
use warnings;

@_ = sort { print "dup = $a$/" if $a eq $b; $a cmp $b } @ARGV;

он будет не так быстро, как хеширующие решения, но он требует меньше памяти и довольно чертовски симпатичен