• 16082
  • 27
  • 0
Нравится блог?
Подписывайтесь!

Basic Data Structures: Linked List

Решил тут вспомнить что же такое структуры данных да алгоритмы.
Помнится последний раз с этим сталкивался еще в универе.

По работе особо и не приходится этим заниматься. Что не говори, а лучший провайдер алгоритмов - база данных.
Мы уже настолько привыкли к этому, что если нас попросить сделать сортировку списка, мы будем кричать "Да я, да я! Да я два списка по 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)
Собственно поиск получается довольно таки стабильным и равномерным.
В итоге хочется сказать, что жаль конечно что создание списка на основе обьекта занимает столько времени, оно то и понятно, столько памяти нужно перекорячить. Но, для небольших списков вполне можно использовать.
16 ноября 2009, 22:23
3263

Загрузка...
Loading...

Комментарии

хоть бы катом пользовались %)
а то я подумала у меня что-то с компом...
Поддерживаю! Засранец!
и сразу ругаться (
Сори.
Ммм, а что такое каток?
Честно говоря, Вы сравниваете яблоки с апельсинами.
Хм, а что тут яблоко и что апельсин? )

Мне интересны результаты которые получаются. Я не претендую на правильность изложенных сравнений, и даже на правильность реализации. Мне скорее хотелось получить альтернативные варианты реализации.

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

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

Во-первых, сравнивать исключительно производительность нужно в тех случаях, когда важна только производительность. :)

Во-вторых, само представление массива и списка подразумевает некоторые различия в производительности (например, массивы позволяют доступ к любому элементу за константное время, а списки -- нет; зато итерация по массиву/списку займет по сути одинаковое время, и играть роль будут уже cache misses, т.е. локальность данных и пр.). Тоже какбы очевидно.

Не читал толком (но посоветую :3), но есть книга Кормена по алгоритмам ("Введение в алгоритмы"), и там про такое должно рассказываться.
Спасибо, посмотрю.

Правда не совсем понимаю причем тут массивы, ведь оценка была именно списка. Списки строились на основе массива, хеша и объектов.
> Правда не совсем понимаю причем тут массивы, ведь оценка была именно списка. Списки строились на основе массива, хеша и объектов.

А зачем списки строить на основе массива или хеша? :) Вот в чем вопрос!
Хорошо, тогда встречный вопрос:
Как построить список в Perl? )
Вот это не поможет?



В Perl не разбираюсь, к сожалению.
Оно самое.

Списки строятся с использованием пользовательских типов, в частности структур или классов. В Perl нет такого понятия как структура (в том смысле как мы привыкли ее понимать основываясь например на C структуры) или класс.

В Perl все пользовательские типы строятся на основе 3-х встроенных типов: scalar, array, hash (больше ни каких типов нет в принципе).

Потому и список строится на основе одного из этих типов, исключая скаляр.

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

В статье список строился из обьектов двух типов.

Однако, если говорить о списке - то это собственно просто обычный массив. Принимаем что первый элемент массива указывает на другой массив, хотя мы можем договорится с самим собой и назначить связь вторым или третьим элементом. Вот и получается, что список это просто N массивов, связанных между собой ссылкой.
Тоже самое можно сказать и про хеши.
Таким образом получается что список в Perl мы можем построить 4-мы способами на основе массива, хеша, объекта на основе массива, либо объекта на основе хэша.
И тут, собственно, встает вопрос: какой подход построения списка лучше?

Хотя слово лучше не корректно в данном случае.
> В Perl все пользовательские типы строятся на основе 3-х встроенных типов: scalar, array, hash (больше ни каких типов нет в принципе).

Как и в JS. Ужас.

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

Да, в JS так делается.

Наверное, списки это просто "непрактично" и "не относится к реальному миру". :) (понятное дело, что это не так, но ...)

> какой подход построения списка лучше?

В Perl есть абстрактные типы данных? Алгебраически, списки можно задать так:

head (cons (x, xs)) = x
tail (cons (x, xs)) = xs
cons (head x, tail x) = x

(head возвращает голову непустого списка, tail возвращает хвост, cons присоединяет голову к списку, возможно пустому)

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

Оставьте свой комментарий

Спасибо за открытие блога в Yvision.kz! Чтобы убедиться в отсутствии спама, все комментарии новых пользователей проходят премодерацию. Соблюдение правил нашей блог-платформы ускорит ваш переход в категорию надежных пользователей, не нуждающихся в премодерации. Обязательно прочтите наши правила по указанной ссылке: Правила

Также можно нажать Ctrl+Enter

Популярные посты

Мой дом – не гостиница. Я не останавливаюсь у своей родни, потому что знаю, что это такое

Мой дом – не гостиница. Я не останавливаюсь у своей родни, потому что знаю, что это такое

Наступил долгожданный момент и мы смогли заселиться в собственную квартиру. А потом началось... Все знакомые, родственники, даже коллеги и соседи родителей вспомнили о нашем существовании.
Idealovnet
14 окт. 2017 / 20:38
  • 8091
  • 78
Работа на EXPO. «Улыбайтесь, вы – лица Казахстана»

Работа на EXPO. «Улыбайтесь, вы – лица Казахстана»

Продление перерывов, втыки от менеджеров, борьба за стенды, кучкования, как мы друг-друга прикрывали, защищали от гостей. Все эти события доставляли радость, и каждый день на работу я приходила...
madiNAtty
14 окт. 2017 / 22:34
  • 5516
  • 22
Молчание Бозумбаева. Как «бензиновые короли» диктуют государству свои правила игры

Молчание Бозумбаева. Как «бензиновые короли» диктуют государству свои правила игры

Произошедшая в сентябре одновременная остановка двух казахстанских НПЗ из трёх и последовавший за этим топливный кризис – это для Казахстана уже не ново. История повторяется каждый год.
openqazaqstan
11 окт. 2017 / 16:32
  • 4319
  • 44
«Что дали задом?» Родительский чат в WhatsApp покорил Интернет

«Что дали задом?» Родительский чат в WhatsApp покорил Интернет

Чат дагестанских родителей в WhatsApp стал популярным в Интернете. Кто-то записал общение родителей в мессенджере и после опубликовал в Твиттере.
tala03
12 окт. 2017 / 15:10
  • 2999
  • 11
«Bank RBK» банкрот? Почему мы не можем распоряжаться собственными же деньгами?!

«Bank RBK» банкрот? Почему мы не можем распоряжаться собственными же деньгами?!

Мы не можем выдать зарплату, оплатить по счетам или как-то иначе распорядиться нашими же деньгами! У физ.лиц, насколько мне известно, ситуация не лучше - при нас люди не могли снять свои деньги с депозитов.
daniyar4422017
13 окт. 2017 / 15:46
  • 2917
  • 12
Актогайский горно-обогатительный комплекс – брат-близнец Бозшаколя

Актогайский горно-обогатительный комплекс – брат-близнец Бозшаколя

Рядом с посёлком Актогай в ВКО расположено одно из крупнейших в мире неосвоенных медных месторождений. В октябре Актогайская обогатительная фабрика вышла на проектную мощность.
theYakov
12 окт. 2017 / 10:47
  • 3005
  • 20
Я четко помню тот день, когда мне позвонили друзья и сообщили: «Она выходит замуж»

Я четко помню тот день, когда мне позвонили друзья и сообщили: «Она выходит замуж»

У нас была особенная атмосфера, мы постоянно были вместе, читали треки, летом часто поднимались в горы. Гуляли пешком по ночному городу, иногда до утра. Снимали хату и представляли совместную жизнь...
Dominator-kz
14 окт. 2017 / 22:29
Отчего в Казахстане предвзятое отношение к отечественному продукту?

Отчего в Казахстане предвзятое отношение к отечественному продукту?

Вы когда-нибудь пользовались казахстанской косметикой? Я тоже нет, поэтому сразу же откликнулась на приглашение своего фейсбук-френда протестировать отечественные крема… из Степногорска.
Shimanskaya
16 окт. 2017 / 11:32
  • 2162
  • 29
Когда почти все уехали в «А-города», стоит ли жить в Шымкенте?

Когда почти все уехали в «А-города», стоит ли жить в Шымкенте?

Город имеет особую ауру - очень густая энергетика, думаю, это от того, что он со всех сторон окружен "местами силы". Шымкент напоминает мне старенького доброго мудрого дедушку-аксакала.
Bonittta
13 окт. 2017 / 15:15