Какой самый эффективный способ проверить наличие дубликатов в массиве данных с помощью 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

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

Создать хэш или набор или использовать collection.Counter () .

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

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

Answer 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";

Answer 6

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

use strict;
use warnings;

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

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

Answer 7

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