• 15589
  • 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
3233

Загрузка...

Комментарии

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

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

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

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

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

Во-вторых, само представление массива и списка подразумевает некоторые различия в производительности (например, массивы позволяют доступ к любому элементу за константное время, а списки -- нет; зато итерация по массиву/списку займет по сути одинаковое время, и играть роль будут уже 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

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

Я был удивлён, что в Азербайджане есть Казахский район

Я был удивлён, что в Азербайджане есть Казахский район

Мне как казаху по национальности очень хотелось туда попасть. Оказалось, что климат там намного суровей и люди, говорят, суровые и воинственные. Казах – город на западе Азербайджана...
alidimash
18 янв. 2017 / 21:50
  • 30799
  • 18
Многочасовые очереди, смерти в ЦОНах: почему вопросы об этом ставят парламентариев в тупик?

Многочасовые очереди, смерти в ЦОНах: почему вопросы об этом ставят парламентариев в тупик?

Ожидали ли депутаты Мажилиса всего этого? Как планировали этот процесс регистрации, и обсуждали ли его, прежде чем одним нажатием кнопки принять нормы с такими абсурдными временными рамками?
openqazaqstan
17 янв. 2017 / 14:32
  • 5268
  • 22
Астана глазами алматинских девушек. Как при таких погодных условиях можно выжить?

Астана глазами алматинских девушек. Как при таких погодных условиях можно выжить?

В спальных районах, и в высотных домах сквозь стены слышно завывание ветра. В особенности ночью. Такие звуки, я слышала, пожалуй, только по телевизору, в фильмах про метель.
Naomi_K
20 янв. 2017 / 12:36
Сильное ДТП произошло в Алматы на Тимирязева-Байзакова

Сильное ДТП произошло в Алматы на Тимирязева-Байзакова

NoComment (c) Официальный слоган EuroNews. Катастрофа на алматинской утренней трассе началась с того, что водители «Ниссана» и микровена ожидали сигнала светофора на запад по Тимирязева...
ibestreporter
17 янв. 2017 / 22:52
  • 3943
  • 5
Вейпинг безопасен? Эндрю Холл из США тоже так считал, пока что-то не пошло не так

Вейпинг безопасен? Эндрю Холл из США тоже так считал, пока что-то не пошло не так

Эндрю Холл из США считал, что вейпинг безопасен и усиленно убеждал в этом близких. Но как-то раз что-то пошло не так. Это результат взрыва хипстерского устройства - выбило 7 зубов + ожоги и раны...
Maxambet
17 янв. 2017 / 16:28
  • 4046
  • 52
Это поколение просрет страну. 20-летняя молодежь представляет из себя сказочных эльфов

Это поколение просрет страну. 20-летняя молодежь представляет из себя сказочных эльфов

Смотря в очередные пустые глаза вчерашнего студента, приходящего устраиваться на первую работу страшно становится. Потому что сравниваю с теми же китайскими студентами, которые готовы выгрызать себе мечту.
mbaitykov
18 янв. 2017 / 11:34
Становится хуже, но как-то постепенно. Беднеем, но тоже как-то не разом

Становится хуже, но как-то постепенно. Беднеем, но тоже как-то не разом

Помню, когда я уезжал и Казахстана, тут было довольно прилично, даже не смотря на то, что жить было невыносимо. Но прилично так. Мусора было меньше. Дороги чистили, вони почти не было. Да и в остальном тоже норм.
shootnix
18 янв. 2017 / 12:49
  • 3812
  • 35
Любимый Тайланд. Правящий король называет Паттайю «черным пятном на репутации страны»

Любимый Тайланд. Правящий король называет Паттайю «черным пятном на репутации страны»

Тайланд мы впервые посетили в декабре 2012 года. Полученные эмоции настолько были яркими, что в конце 2015 года мы решили еще разок слетать в Тайланд. Вспоминая Тай, первое о чем я думаю - горячий...
zhainar_d
17 янв. 2017 / 11:11
  • 3873
  • 25
Разрубить сирийский узел. Казахстан как миротворец сделает невозможное?

Разрубить сирийский узел. Казахстан как миротворец сделает невозможное?

Только что в Астане начались межсирийские переговоры. Событие это примечательно не столько содержанием и ожидаемыми результатами, а самим фактом.
openqazaqstan
вчера / 13:35
  • 2928
  • 10