А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Удаление елемента в списке происходит за O(1). Если попробывать в массиве сделать ссылку на следующий елемент, то получим список.
Здравствуйте, Воронков Василий, Вы писали: ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Динамический — это какой? Который при достижении максимального размера выделяет новый блок и копирует туда все элементы? Тогда с точки зрения внутреннего устройства структуры данных (раз уж мы говорим, что интерфейс поверх этого можно любой навернуть) — вставка элемента в голову списока — всегда предполагает только лишь аллокацию очередного элемента. Удаление, вставка в середину тоже простые операции (правда нужно сперва найти нужное место).
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции? ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
immutable list позволяет шарить одинаковый хвост между несколькими экземплярами списка + не нужна синхронизация при доступе из разных потоков.
Здравствуйте, ankorol, Вы писали:
ВВ>>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции? ВВ>>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
A>Удаление елемента в списке происходит за O(1). Если попробывать в массиве сделать ссылку на следующий елемент, то получим список.
Да ну, список — immutable структура. Любые операции с ним приводят к созданию нового списка. Каким образом вы, кстати, собираетесь указать, какой именно из элементов списка вы собираетесь "удалить"? Доступа по индексу-то нет.
А операции плана head:tail легко эмулируются через энумератор.
Здравствуйте, Воронков Василий, Вы писали: ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Кстати, насчет реализации связных списков, в этой теме один наш коллега в том числе и этим занимался: http://rsdn.ru/forum/decl/3176311.aspx
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Подлинковка одного списка в другой список (то, что делает std::list::split). Если нам не надо хранить длину списка, то эта операция константная. Вставка и удаление элемента в список по известному местоположению — тоже константная операция.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Да ну, список — immutable структура. Любые операции с ним приводят к созданию нового списка. Каким образом вы, кстати, собираетесь указать, какой именно из элементов списка вы собираетесь "удалить"? Доступа по индексу-то нет.
Я имел введу, если у нас есть "указатель" на елемент который мы хотим удалить.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Главное преимущество связного списка перед массивами — другая алгоритмическая сложность операций. И совершенно другие стратегии синхронизации при параллельном доступе из разных потоков.
Предвосхищая ваши возражения, хочу сразу заметить, что главными недостатками связных списков перед массивами являются: другая алгоритмическая сложность операций и совершенно другие стратегии синхронизации при параллельном доступе из разных потоков.
ВВ>>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Кэр>Главное преимущество связного списка перед массивами — другая алгоритмическая сложность операций. И совершенно другие стратегии синхронизации при параллельном доступе из разных потоков.
Кэр>Предвосхищая ваши возражения, хочу сразу заметить, что главными недостатками связных списков перед массивами являются: другая алгоритмическая сложность операций и совершенно другие стратегии синхронизации при параллельном доступе из разных потоков.
Василий, послушай этого человека, он дело говорит. Хотя и выглядит как капитан Очевидность.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Для начала нужно определиться о чем идет речь. Если о списках из ФЯ (т.е. о незименяемых), то один разговор. Если о "классических" реализациях, то другой.
Списки из ФЯ имеют следующие приемущества:
1. O(1) время добавления элементов в начало списка.
2. Неизменяемость, а значит версионность и типобезопасность.
3. Повторное использование хвостов других списков.
5. Они реализуются в виде Алгебраических типов данных, что делает их использование в сопоставлении с образцом очень удобным.
Недостатки тоже очевидны:
1. Медленная вставка, замена и удаление элементов, если эти операции осуществляются не в начале списка.
2. Каждый элемент объекта требует создания отдельного объекта в куче.
3. Несколько ухудшает попадание в кэш процессора, так как занимает больше памяти и иногда приводит к тому что элементы идут не последовательно в памяти.
В общем, списки хороший инструмент в языках где имеется их хорошая поддержка и когда речь не идет о числодробильных задачах.
Вот пример из недавнего. В макросе построителе парсеров по PEG-грамматике списки применяются по полной программе, но в генерируемом этим макросом коде мы их применять не стали.
В общем, там где нужно распознавать сложные конструкции списки рулят. А там где нужны высокопроизводительные вычисления или добавление в конец списка, там они не к чему.
Ну, и они не для тех кто использует C# или VB, так как эти языки не имеют встроенной поддержки списков, а без нее кайф от применения списков теряется.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Ты описал только иммутабельные сценарии, на них массив эффективнее порой на порядок.
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Цена изменения содержимого не зависит от кол-ва элементов.
Экономия места для данных, которые по природе близки к "chain of responsibility", там дерево "наоборот" получается.
Для иммутабельного случая эта экономия применима к сценариям любой природы.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Воронков Василий, Вы писали: ВВ>>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции? ВВ>>Просто, честно говоря, при желании можно легко сымитировать связный список на динамическом массиве + энумератор, при этом мы получим кучу бенефитов, например, нам всегда будет известна длина и сложение списков будет стоить дешевле. VD>Для начала нужно определиться о чем идет речь. Если о списках из ФЯ (т.е. о незименяемых), то один разговор. Если о "классических" реализациях, то другой.
Вопрос на самом деле о том, насколько успешно можно сымитировать связный список (да, из ФЯ) на основе динамического массива. "O(1) время добавления элементов в начало списка" — это все же техническая особенность связного списка, а вот иммутабельность уже особенность дизайна.
Положим, что в каких-то случаях мы начнем отставать от честного связного списка, но не получится ли так, что в наиболее часто востребованных задачах производительность будет лучше?
К примеру, простейший тест в Немерле — foreach для аррая и списка — показывает, что для в задаче последовательного перебора динамический массив быстрее более чем в 2 раза. Нехорошо как-то.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Например, в случае двусвязного циклического списка, чтобы удалить элемент нам даже не нужно знать в каком из списков он хранится. Кроме того, список легко может быть только частью более сложной сети зависимостей, при этом требует фиксированной памяти.
Например, дерево шахматных ходов. Например, если все позиции, которые возникают в результате всех возможных ответов в данной, хранить в виде списка, то размер структуры под одну позицию постоянный, и для нее можно реализовать свой распределитель памяти, где выделение/уничтожение позиции будет O(1). И это все операции, что нам надо.
While immutability is a benefit, it is also a drawback, making it inefficient to modify elements in the middle of the array.
Я как-то не так понимаю термин immutability? Речь действительно о том чтобы менять элементы в середине массива?
Но меня смущает еще кое-что:
Единственный вариант, при котором можно говорить о иммутабельности данной структуры — это клонировать весь массив по указателю Base при каждом добавлении элемента чтобы гарантировать неизменность существующих списков, содержащих массив по указателю Base.
Это делает вставку настолько неэффективной, что про иммутабельность можно было просто не упоминать вообще (вне зависимости от середины или краев массива).
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Вопрос на самом деле о том, насколько успешно можно сымитировать связный список (да, из ФЯ) на основе динамического массива.
Сама постановка задачи глупая. Краткий ответ — ни насколько.
ВВ> "O(1) время добавления элементов в начало списка" — это все же техническая особенность связного списка, а вот иммутабельность уже особенность дизайна.
И то и другое особенность дизайна. Точнее особенность самой структуры данных.
ВВ>Положим, что в каких-то случаях мы начнем отставать от честного связного списка, но не получится ли так, что в наиболее часто востребованных задачах производительность будет лучше?
Производительность будет лучше только при одном условии — если программист будет выбирать структуры данных и алгоритмы под задачу, то есть будет выстраивать общее решение путем построения дизайна учитывающего особенности структур данных и алгоритмов их обработки.
Короче, нужно понимать что делаешь.
ВВ>К примеру, простейший тест в Немерле — foreach для аррая и списка — показывает, что для в задаче последовательного перебора динамический массив быстрее более чем в 2 раза. Нехорошо как-то.
Это бред. Полнейший и махровый. Так вообще нельзя подходить к программированию. Нужно брать задачу и смотреть как ее лучше всего решать. Разница во времени затрачиваемом на перебор списка и массива ничтожна по сравнению со временем которое будет потрачено на вычисления, преобразования данных и т.п. Потом чистое время вообще не имеет смысла. Отдельно взятая задача в 99.999% случаев на современных компьютерах выполняется очень быстро! Смотреть надо на то насколько общая производительность приемлема для конкретной задачи. Может оказаться так, что задача отлично решается даже самым экстенсивными средствами.
Так что выжимать такты процессора из каждого перебора глупо. К тому же списки намного реже перебирают с помощью циклов.
Собственно тогда уж нужно задуматься над тем, что использование ФВП тоже дает оверхэд. Да и дотнет тоже не бесплатен. GC основанный на поколениях вносит оверхэд в любое присвоение указателя на ссылочный объект. Так давай откажемся и от дотнета и будем все писать на С! А там окажется, что и С вносит некоторый оверхэд. Так что здравствуй ассемблер?
ВВ>И длина, длина
Что длинна?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, samius, Вы писали:
S>Я как-то не так понимаю термин immutability? Речь действительно о том чтобы менять элементы в середине массива?
Да невнятно как-то. Может имеется в виду немутабельность VList недостаток при вставке в середину?
S>Но меня смущает еще кое-что: S>Единственный вариант, при котором можно говорить о иммутабельности данной структуры — это клонировать весь массив по указателю Base при каждом добавлении элемента чтобы гарантировать неизменность существующих списков, содержащих массив по указателю Base. S>Это делает вставку настолько неэффективной, что про иммутабельность можно было просто не упоминать вообще (вне зависимости от середины или краев массива).
VList это замена обычному односвязному списку который используется в функциональщине, и соответственно оптимизирован под это, то есть предполагается быстрая добавление к голове и легкое переиспользование хвоста. При таком использовании клонирование не нужно.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, samius, Вы писали:
S>>Я как-то не так понимаю термин immutability? Речь действительно о том чтобы менять элементы в середине массива?
FR>Да невнятно как-то. Может имеется в виду немутабельность VList недостаток при вставке в середину?
Я не понял о чем речь.
FR>VList это замена обычному односвязному списку который используется в функциональщине, и соответственно оптимизирован под это, то есть предполагается быстрая добавление к голове и легкое переиспользование хвоста. При таком использовании клонирование не нужно.
Переиспользование хвоста без клонирования мне как-то не видится.
Пусть мы имеем список А (2,3,4,5,6), как на картинке в статье. Вставим в него 1-у:
let A1 = A.Add(1)
здесь мы получили реюз ховста. У нас есть:
A (2,3,4,5,6)
A1 (1,2,3,4,5,6)
Теперь делаем
let A2 = A.Add(-1)
и получаем
A (2,3,4,5,6)
A1 (-1,2,3,4,5,6)
A2 (-1,2,3,4,5,6)
т.е. мы добавлением к A нового элемента нарушили список A1.
