Perl как ускорить работу скрипта?

Question

[Сергей]

Нужно сравнить каждий елемент первого масива с каждым елементом второго и вывести на печать уникальные и не уникальные значения в разные файлы

#!/usr/bin/perl
.....
foreach $nn (@array0) {
$g=0;
foreach $mm (@array1) {
if ($nn==$mm) {
$g=$g+1
print FILE1 "$nn\n";
}
}
if ($g==0) {
print FILE2 "$nn\n";
}
}
.......
Как ускорить работу скрипта? обработка 10 000 х 1 000 000 = 10мин
а нужно сравнить примерно 1 000 000 000 х 1 000 000 000 000...... подскажите подход

Если использовать for то 10 000 х 1 000 000 = 37 мин

Уточняю
Сравнение не сильно замедляет.....
я запустил вот такую программу без сравнения:
foreach $nn (@array0) {
foreach $mm (@array1) {
$g=$g+1
}
}
в итоге время работы почти 10 мин
как можна сравнить значения по другому, не через foreach или for?

Comments

[Shetani]

какие значения в массивах, есть ли повторяющиеся значения?

[vaut]

Вопрос по примеру:
$nn==$mm Это точно то что вы хотите?
perldoc.perl.org/perlop.html#Equality-Operators

[Сергей]

Shetani: пример "1079123123451", есть повторения

[Сергей]

vaut: в этой задачи просто числа, но если использовать не числа, то я так понимаю оператор == не подходит?

[vaut]

Сергей: да верно, для сравнивания строк нужно использовать "eq"

[Сергей]

vaut: спасибо

Answer 1

[pcdesign]

Можно воспользоваться готовым модулем:
search.cpan.org/~zmij/Array-Utils-0.5/Utils.pm
Модуль быстрый.
Примерно так.
Есть два массива. Сравниваем их и выводим уникальные значения:

my @a = qw( a b c d );
my @b = qw( c d e f );
my @c = array_diff( @a, @b );
say for (@c)

Результат:

a
b
e
f

Теперь находим элементы не уникальные.

use feature 'say';
use Array::Utils qw(:all);


my @a = qw( a b c d );
my @b = qw( c d e f );
my @c = intersect( @a, @b );
say for (@c)

Результат

c
d

Comments

[Сергей]

cpan Array::Utils
_______________________________________________
use feature 'say';
use Array::Utils qw(:all);

# intersection
my @isect = intersect(@array0, @array1);

say for (@isect);

10 мин -> 2 sec
спасибо

Answer 2

[vaut]

Совет дилетанта:
Меньшим списком заполняем хеш, и в один проход и большого получаем уников и дубли.
Забираем дубли в новый хеш и из меньшего списка получаем уников.
На небольших числах должно летать, упадет ли производительность на 10^6 записей не знаю.
Если будет падать меньший список нужно будет порезать на несколько.

Comments

[Сергей]

Дело в том что сравнение не сильно замедляет.....
я запустил вот такую программу без сравнения:
foreach $nn (@array0) {
foreach $mm (@array1) {
$g=$g+1
}
}
в итоге время работы почти 10 мин

[Сергей]

как можна сравнить значения по другому, не через foreach или for?

[vaut]

Сергей: сложность вашего решения n*m. Как не крутись на миллионе вашем количестве будет тормозить.

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

[vaut]

Сергей: я предлагаю что то вроде этого:
foreach ( $nn (@array0) ) { $nn{$nn} = true }
foreach ( $mm (@array1) ) {
if ( exists $nn{$mm} ) {
print FILE1 "$mm\n";
delete $nn{$mm};
}
else print FILE2 "$mm\n";
}
while ( ( $key, $value ) = each %nn ) {
print FILE2 "$key\n";
}

Answer 3

[parserpro]

1. Простые и быстрые алгоритмы есть в Perl Cookbook
2. Массивы размером миллиард и триллион элементов так не сравнить - памяти просто не хватит.
3. Какой тип данных? Понятно что в Perl это вроде не так важно, но для решения задачи значение имеет.

Навскидку решение:
Допустим что у нас только целые числа - значения от 0 до 65535. Построим битовую маску имеющихся в массиве чисел, причем если число есть - соответствующий ему бит выставим в 1. Размер маски очевидно 65536 бит или 8192 байта, что совсем и не много.
Итак, идем по первому массиву и заполняем маску.
Теперь идем по второму массиву и если бит в маске для текущего числа выставлен в 1, то число не уникально.