perl: удаление дубликатов (самый короткий способ)

[agbr]

подскажите самый коротный (в смысле длинны кода) и желательно быстрый способ удаление дубликатов из массива (уже отсортированного)

Код: Выделить всё

# из этого
['a','a','b','b','b','c','d','e','e','f','g','h']
# надо получить
['a','b','c','d','e','f','g','h']
# кстати необязательно в таком порядке

[elide]

ну... я перл не знаю, но думаю, что перегнать массив в множество (как оно там называется в перле-то?) и обратно - и быстро, и недлинно.

[AndyX]

О!!! Perl golf!!!

Код: Выделить всё

@arr = ('a','a','b','b','b','c','d','e','e','f','g','h');
@arr = grep {! $tmp{$_}++ } @arr;

[t.t]

О!!! Perl golf!!!

↑

А что, тоже ваиант.
Только тогда уж просьба: раз уж началось дело с вопроса от человека (судя по всему) не очень в перле понимающего, не будет ли любезен многоуважаемый джин расфаршировать эту строчку на русский язык?

[AndyX]

Дык это и так практически русский язык

DECLARE
%tmp - хэш, ключами являются элементы массива, значениями - кол-во их вхождений в исходный массив.
BEGIN
Берем элемент, смотрим кол-во его вхождений. Если таковое не установлено, стало быть элемент встретился впервые - пропускаем его. Количество его вхождений увеличиваем на единицу - в седующий раз не пройдет
END

[madskull]

Код: Выделить всё

@arr = ('a','a','b','b','b','c','d','e','e','f','g','h');
@arr = grep { ($_ ne $t) ? $t=$_ : 0 } @arr;

Где $t - некая временная переменная, которая содержит предыдущее значение.
Но этот способ годится только для отсортированных массивов, но по сравнению с предыдущим

1) не занимает дополнительное место, для хранения временного хэша
2) не выполняет операций поиска/вставки в хэш, т.е. в целом работает быстрее

↑

На основе чего сделаны выводы о меньшей скорости работы хэша?

Код: Выделить всё

use Benchmark;

@arr = ('a','a','b','b','b','c','d','e','e','f','g','h');

timethese(1000000,
        {
                test1 => '@a1 = grep { ($_ ne $t) ? $t=$_ : 0 } @arr',
                test2 => '@a2 = grep {! $tmp{$_}++ } @arr',
        }
);

результат:

Код: Выделить всё

Benchmark: timing 1000000 iterations of test1, test2...
     test1: 28 wallclock secs (29.22 usr +  0.06 sys = 29.28 CPU) @ 34153.01/s (n=1000000)
     test2:  9 wallclock secs ( 9.82 usr +  0.01 sys =  9.83 CPU) @ 101729.40/s (n=1000000)

no comments

[madskull]

Не долго проверить: (*)

Код: Выделить всё

use Benchmark;

@arr = (1..1000000);

timethese(100,
       {
               test1 => '@a1 = grep { ($_ ne $t) ? $t=$_ : 0 } @arr',
               test2 => '@a2 = grep {! $tmp{$_}++ } @arr',
       }
);

результат:

Код: Выделить всё

Benchmark: timing 100 iterations of test1, test2...
     test1: 616 wallclock secs (602.90 usr +  4.96 sys = 607.86 CPU) @  0.16/s (n=100)
     test2: 220 wallclock secs (214.56 usr +  1.73 sys = 216.29 CPU) @  0.46/s (n=100)

* пришлось сделать 100 проверок, а то слишком уж долго

Дело в том, что в перле нет чисел как таковых. Все хранится в виде строк...

[agbr]

За предложенный алгоритм еще раз спасибо. Насчет собственного, то должен принести извинения, ибо вчера вечером уже ничего не соображал. Итак:

Код: Выделить всё

@arr = grep { ($_ ne $t) ? $t=$_ : 0 } @arr

Будет действительно работать медленне, чем предложенный ибо (а я вчера перепутал бинарное дерево и хэш) в хэшах не используется поиск/сравнение вообще, а используется прямой доступ к элемену, что очень ускорят работу (желающие узнать о том, как это работает могут прочитать Д.Кнут ИП том.3 "Сортировка и Поиск"), но
предложенный алгоритм опять же из-за использования хэша потреблят большее количество памяти (желающие могут прочитать названную выше книгу и узнать, что для работы хэша требуется намного больше памяти, чем для бинарного дерева, например), что иногда может быть действительно неприятно.