Помнится последний раз с этим сталкивался еще в универе.
По работе особо и не приходится этим заниматься. Что не говори, а лучший провайдер алгоритмов - база данных.
Мы уже настолько привыкли к этому, что если нас попросить сделать сортировку списка, мы будем кричать "Да я, да я! Да я два списка по 100000 записей сджойню и отсортирую в пять сек!"
Мы уже настолько привыкли к этому, что если нас попросить сделать сортировку списка, мы будем кричать "Да я, да я! Да я два списка по 100000 записей сджойню и отсортирую в пять сек!"
А на деле что? Ну хорошо если полезешь на CPAN да скачаешь модуль который за тебя все это сделает, а если решишь сам все сделать?
Сколько интересно времени на все уйдет. Так что повторение, как говорится, мать учения.
Так что начнем с основ.
Связной список.
Связной список.
Сам придумывать не стал, честно спер с вики. Связной список - структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Интресно было сравнить различные списки.
Список построенный на массиве, хеше, объекте массиве и объекте хеше
В итоге получилось два объекта, практически идентичных. Ниже код объекта на основе хеша
package LinkedListHash;
use Data::Dumper;
sub new
{
my $class = shift;
my $value = shift;
$class = ref $class || $class;
return bless { value => $value, next => undef }, $class;
}
sub add
{
my $self = shift;
my $item = shift;
my $obj = (ref $self)->new($item);
$self->tail->{next} = $obj;
return $self;
}
sub tail
{
my $self = shift;
my $next = $self;
while ( $next->{next} ){ $next = $next->{next} }
return $next;
}
sub find
{
my $self = shift;
my $val = shift;
my $cmp = shift;
for(my $next = $self; $next; $next = $next->{next}){
return $next if $cmp->($next->{value}, $val) == 0 ;
}
return undef;
}
sub insertAfter
{
my $self = shift;
my $item = shift;
my $newItem = shift;
if($item->{next}){
my $obj = (ref $self)->new($newItem);
$obj->{next} = $item->{next};
$item->{next} = $obj;
}
else{
$item->next = (ref $self)->new($newItem);
}
return $self;
}
sub removeAfter
{
my $self = shift;
my $item = shift;
return $self unless $item->{next};
if($item->{next}->{next}){
my $obj = $item->{next}->{next};
$item->{next} = $obj;
}
else{
$item->{next} = undef;
}
return $self;
}
sub DESTROY
{
my $self = shift;
warn Dumper($self->{value});
}
1;
Сравнивал используя Benchmark.В сравнении участвовали функции создания списка и поиска элемента.
Вставка и удаление делаются за O(1), без учета поиска.
Поиск элемента занимает O(N) операций.
Скрипт оценки производительности создания списка:
use LinkedListHash;
use LinkedListArr;
use Benchmark qw(:all) ;
my $count = 100;
timethese($count, {
'Object Hash' => \&hash_fill,
'Object Array' => \&array_fill,
'Pure Hash' => \&pure_hash_fill,
'Pure Array' => \&pure_array_fill,
});
sub hash_fill
{
my $item = {val1 => 1, val2 => 2};
my $list = new LinkedListHash($item);
for (my $i = 3; $i <>add(
{val1 => $i, val2 => $i+1 }
);
}
}
sub array_fill
{
my $item = {val1 => 1, val2 => 2};
my $list = new LinkedListArr($item);
for (my $i = 3; $i <>add(
{val1 => $i, val2 => $i+1 }
);
}
}
sub pure_array_fill
{
my ($tail, $list);
for (my $i = 1; $i <>[0] = [ undef, {val1 => $i, val2 => $i+1 } ];
$tail = $tail->[0];
}
else
{
$list = $tail = [ undef, {val1 => $i, val2 => $i+1 } ];
}
}
}
sub pure_hash_fill
{
my ($tail, $list);
for (my $i = 1; $i <>{next} = { next => undef, val => {val1 => $i, val2 => $i+1 } };
$tail = $tail->{next};
}
else
{
$list = $tail = { next => undef, val => {val1 => $i, val2 => $i+1 } };
}
}
}
И результаты:
Benchmark: timing 100 iterations of Object Array, Object Hash, Pure Array, Pure Hash...
Object Array: 28 wallclock secs (27.88 usr + 0.00 sys = 27.88 CPU) @ 3.59/s (n=100)
Object Hash: 32 wallclock secs (30.97 usr + 0.00 sys = 30.97 CPU) @ 3.23/s (n=100)
Pure Array: 6 wallclock secs ( 5.32 usr + 0.00 sys = 5.32 CPU) @ 18.80/s (n=100)
Pure Hash: 7 wallclock secs ( 7.24 usr + 0.00 sys = 7.24 CPU) @ 13.81/s (n=100)
Результаты конечно предсказуемы, но что бы настолько - я был очень удивлен. Причем, если создавать не 10000 элементов в не объектных списках, а 999 то получаем
(warning: too few iterations for a reliable count)
Далее оценим поиск элемента
Скрипт оценки производительности
use LinkedListHash;
use LinkedListArr;
use Data::Dumper;
use Benchmark qw(:all) ;
my $count = 10000;
our $ho_list = &hash_fill;
our $ao_list = &array_fill;
our $ph_list = &pure_hash_fill;
our $pa_list = &pure_array_fill;
our $find_val = 9;
timethese($count, {
'object Hash Find' => \&hash_find,
'object Array Find' => \&array_find,
'pure Hash Find' => \&pure_hash_find,
'pure Array Find' => \&pure_array_find,
});
sub hash_find
{
my $fitem = $ho_list->find($find_val, \&compare);
}
sub array_find
{
my $fitem = $ao_list->find($find_val, \&compare);
}
sub pure_hash_find
{
my $item = $ph_list;
while ($item){
last if ::compare->($item->{val}, $find_val) == 0;
$item = $item->{next};
}
}
sub pure_array_find
{
my $item = $pa_list;
while ($item){
last if ::compare->($item->[1], $find_val) == 0;
$item = $item->[0];
}
}
sub compare
{
return $_[0]->{val1} > $_[1] ? 1 : $_[0]->{val1} < $_[1] ? -1 : 0; } Замеры делались для поиска элементов в начале, середине и конце списка
our $find_val = 9;
Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...
object Array Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53191.49/s (n=10000)
(warning: too few iterations for a reliable count)
object Hash Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)
(warning: too few iterations for a reliable count)
pure Array Find: 1 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)
(warning: too few iterations for a reliable count)
pure Hash Find: 0 wallclock secs ( 0.19 usr + 0.00 sys = 0.19 CPU) @ 53475.94/s (n=10000)
(warning: too few iterations for a reliable count)
our $find_val = 550;
Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...
object Array Find: 10 wallclock secs (10.37 usr + 0.00 sys = 10.37 CPU) @ 963.95/s (n=10000)
object Hash Find: 10 wallclock secs (10.97 usr + 0.00 sys = 10.97 CPU) @ 911.91/s (n=10000)
pure Array Find: 10 wallclock secs (10.54 usr + 0.00 sys = 10.54 CPU) @ 948.32/s (n=10000)
pure Hash Find: 11 wallclock secs (11.22 usr + 0.00 sys = 11.22 CPU) @ 891.58/s (n=10000)
our $find_val = 996;
Benchmark: timing 10000 iterations of object Array Find, object Hash Find, pure Array Find, pure Hash Find...
object Array Find: 20 wallclock secs (19.25 usr + 0.01 sys = 19.27 CPU) @ 519.08/s (n=10000)
object Hash Find: 21 wallclock secs (20.58 usr + 0.02 sys = 20.59 CPU) @ 485.63/s (n=10000)
pure Array Find: 20 wallclock secs (19.55 usr + 0.03 sys = 19.58 CPU) @ 510.78/s (n=10000)
pure Hash Find: 21 wallclock secs (20.23 usr + 0.00 sys = 20.23 CPU) @ 494.22/s (n=10000)
Собственно поиск получается довольно таки стабильным и равномерным.
В итоге хочется сказать, что жаль конечно что создание списка на основе обьекта занимает столько времени, оно то и понятно, столько памяти нужно перекорячить. Но, для небольших списков вполне можно использовать.
