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

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

1 голос
/ 22 января 2012

Моя задача состоит в том, чтобы пройтись по списку (до 50 КБ) имен хостов и связанных IP-адресов и MAC-адресов, в поисках дубликатов, чтобы попытаться привести их в порядок, и я нашел это рабочее решение : 

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;


my %HoA = (
    host1   => [ "10.1", "ae:ab" ],
    host2   => [ "10.2", "aa:ee" ],
    host3   => [ "10.3", "aa:ee" ],
    host4   => [ "10.1", "ab:ab" ],
);

my %duplicate =();

foreach my $key ( keys %HoA ) {
  push @{ $duplicate { $HoA{$key}[0] } } , "$key", "$HoA{$key}[1]" ;
  push @{ $duplicate { $HoA{$key}[1] } } , "$key", "$HoA{$key}[0]" ;
}

foreach my $key2 ( keys %duplicate ) {
    if ( (scalar @{ $duplicate{$key2} } ) > 2  ) {
        print "Duplicate:$key2\tGroup:@{ $duplicate{$key2} }\n";
    }
}


print Dumper (\%duplicate) . "\n";

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

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

Любые идеи с радостью приветствуются.

Приветствия

Andy

UPDATE: В конце концов я выбрал это решение (после нескольких недель игры) и добавил дополнительное сравнение анонимных массивов.

Спасибо за все комментарии, это действительно помогает обмениваться идеями: 

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my (%dup) = ();
my ( $data_a, $data_b ) = ();
my ( @a,      @b )      = ();

@a = (
    [qw/ host1 10.1 ae:ab /], [qw/ host2 10.2 aa:ee /],
    [qw/ host3 10.3 aa:ee /], [qw/ host4 10.1 ab:ab /],
);

@b = (
    [qw/ host1 10.1 ae:ab /], [qw/ host3 10.2 aa:ee /],
    [qw/ host6 10.3 aa:ee /], [qw/ host4 10.1 ab:ab /],
);

foreach $data_a (@a) {
    my ( $host, $ip, $mac ) = @$data_a;
    push @{ $dup{$host} }, "$host $ip $mac";
    push @{ $dup{$ip} },   "$host $ip $mac";
    push @{ $dup{$mac} },  "$host $ip $mac";
}

foreach $data_b (@b) {
    my ( $host, $ip, $mac ) = @$data_b;
    push @{ $dup{$host} }, "$host $ip $mac";
    push @{ $dup{$ip} },   "$host $ip $mac";
    push @{ $dup{$mac} },  "$host $ip $mac";
}

print Dumper (%dup) . "\n";
#skipped scalar search

Ответы [ 3 ]

1 голос
/ 22 января 2012

Вы в значительной степени получили это.Лучший способ обнаружения дубликатов - создать хеш.Вы только дважды просматриваете свою структуру, что довольно эффективно.Даже миллион записей будет выполняться менее чем за секунду на современном компьютере.Основные проблемы с масштабированием возникают при выполнении циклов.

Например, что если вы решили сравнить каждый ключ с другим ключом: 

foreach my $key ( keys %HoA ) {
    foreach my $key2 (keys %HoA) {
       #Some sort of comparison between $HoA{$key} and $HoA{$key2}
    }
}

Это будет циклически сравнивать квадрат числа записей в% HoA.Для сравнения, ваш алгоритм выполняет только удвоение числа ключей (один раз для каждого цикла).Ваш алгоритм может сделать 1000000 записей менее чем за секунду.Цикл цикла может занять более одного дня.

Мои единственные комментарии касаются читабельности:

  • Почему вы использовали $key и $key2?Мне потребовалось несколько микросекунд, чтобы понять, что вам не нужны ни $key, ни $key2.
  • Я бы использовал два отдельных хеша вместо массива с двумя хешами, и я назначил бы IP-адрес иMAC-адрес для двух временных переменных.Это упрощает ваш синтаксис и делает его намного проще для чтения.

Например: 

my %ip_hash;
my %mac_hash;
foreach my $key ( keys %HoA ) {
    my $ip = $HoA{$key}[0];
    my $mac = $HoA{$key}[1];
    push @{ $ip_hash{$ip} }, $key, $mac;
    push @{ $mac_hash{$mac} }, $key, $ip;
}

Я изначально упустил тот факт, что вы вводили MAC-адрес в хэш IP, иIP-адрес в MAC-хэш.Здесь очень ясно.

1 голос
/ 22 января 2012

Простое обнаружение дубликатов может быть сделано намного более кратким, но если у вас есть требование отображать всех членов групп с несколькими записями, то вы близки к наилучшему, что можно сделать. Однако я бы сказал, что %HoA - это плохое имя для вашего хэша, потому что оно должно описывать содержимое хэша, а не его структуру. Я также предпочел бы, чтобы значения хеш-элементов были вытянуты вот так 

foreach my $key ( keys %HoA ) {
  my $val = $HoA{$key};
  push @{ $duplicate { $val->[0] } } , "$key", "$val->[1]" ;
  push @{ $duplicate { $val->[1] } } , "$key", "$val->[0]" ;
}

Наконец, ваш %HoA - это на самом деле просто набор записей с тремя значениями в каждой, и он также может легко содержаться в массиве анонимного массива. Этот код эквивалентен вашему оригиналу, и я думаю, что более читабельным 

my @data = (
  [qw/ host1 10.1 ae:ab / ],
  [qw/ host2 10.2 aa:ee / ],
  [qw/ host3 10.3 aa:ee / ],
  [qw/ host4 10.1 ab:ab / ],
);

my %duplicate = ();

foreach my $rec ( @data) {
  my ($host, $val1, $val2) = @$rec;
  push @{$duplicate {$val1}} , "$host", "$val2" ;
  push @{$duplicate {$val2}} , "$host", "$val1" ;
}
0 голосов
/ 22 января 2012 
#! /usr/bin/perl
use strict;
use warnings;

my %hosts = (
  host1 => [ "10.1", "ae:ab" ],
  host2 => [ "10.2", "aa:ee" ],
  host3 => [ "10.3", "aa:ee" ],
  host4 => [ "10.1", "ab:ab" ],
);

my (%dup_mac,%dup_ip);

while( my($hostname,$addr) = each %hosts ) {
  push @{ $dup_ip{  $addr->[0] } }, $hostname;
  push @{ $dup_mac{ $addr->[1] } }, $hostname;
}

find_dup(\%dup_mac,'MAC');
find_dup(\%dup_ip,'IP');

sub find_dup{
  my($hash,$type) = @_;
  for my $addr ( sort keys %$hash ){
    my $hosts = $hash->{$addr};
    next unless @$hosts > 1;

    print "Duplicate $type: $addr\n";
    print ' 'x4, $_, "\n" for sort @$hosts;
  }
}

Duplicate MAC: aa:ee
    host2
    host3
Duplicate IP: 10.1
    host1
    host4
...