Здравствуйте, samius, Вы писали:
FR>>Да невнятно как-то. Может имеется в виду немутабельность VList недостаток при вставке в середину? S>Я не понял о чем речь.
Я тоже
S>Переиспользование хвоста без клонирования мне как-то не видится.
S>Пусть мы имеем список А (2,3,4,5,6), как на картинке в статье. Вставим в него 1-у: S>let A1 = A.Add(1) S>здесь мы получили реюз ховста. У нас есть: S>A (2,3,4,5,6) S>A1 (1,2,3,4,5,6)
S>Теперь делаем S>let A2 = A.Add(-1) S>и получаем S>A (2,3,4,5,6) S>A1 (-1,2,3,4,5,6) S>A2 (-1,2,3,4,5,6)
S>т.е. мы добавлением к A нового элемента нарушили список A1.
Ты не учитываешь то что "указатель" на VList это база + смещение, поэтому при создании нового списка ничто ни мешает нам создать
голову (блок размером N * 2 от макимального блока родителя) которая укажет точно на нужный нам элемент начала хвоста, это конечно немного
исказит структуру, но ничего страшного. То есть любые добавления в старый список на наш новый (и наоборот) не повлияют, головы у них
получаются разные.
FR>>Вообще тут http://infoscience.epfl.ch/record/64410/files/techlists.pdf более подробно о VList и некоторых производных от него структур данных. S>Там ни слова об иммутабельности, хотя я читал невнимательно.
Ну там же все пляшет от лисповских списеов которые немутабельны по умолчанию.
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, samius, Вы писали:
S>>т.е. мы добавлением к A нового элемента нарушили список A1.
FR>Ты не учитываешь то что "указатель" на VList это база + смещение, поэтому при создании нового списка ничто ни мешает нам создать голову (блок размером N * 2 от макимального блока родителя) которая укажет точно на нужный нам элемент начала хвоста, это конечно немного исказит структуру, но ничего страшного. То есть любые добавления в старый список на наш новый (и наоборот) не повлияют, головы у них получаются разные.
Я правильно понимаю, что под головой ты понимаешь то, на что указывает Base, т.е. первый из списка массивов (вместе с дополнительной информацией)?
Если да, то об этом я и говорил, что добавление элемента в иммутабельном случае должно клонировать голову.
Но если речь о клонировании, то зачем нам создавать блок под 2*N элементов, если можно создать только под фактически необходимое кол-во элементов, ведь добавление очередного создаст новую голову.
FR>>>Вообще тут http://infoscience.epfl.ch/record/64410/files/techlists.pdf более подробно о VList и некоторых производных от него структур данных. S>>Там ни слова об иммутабельности, хотя я читал невнимательно.
FR>Ну там же все пляшет от лисповских списеов которые немутабельны по умолчанию.
Знаком с ними. Их иммутабельность не вызывает никаких сомнений. Более того, добавление (с созданием нового списка) в лисповых списках должно быть намного быстрее VList-а именно в иммутабельной функциональщине. Т.е. cons против клонирования головы...
FR>>Ты не учитываешь то что "указатель" на VList это база + смещение, поэтому при создании нового списка ничто ни мешает нам создать голову (блок размером N * 2 от макимального блока родителя) которая укажет точно на нужный нам элемент начала хвоста, это конечно немного исказит структуру, но ничего страшного. То есть любые добавления в старый список на наш новый (и наоборот) не повлияют, головы у них получаются разные.
S>Я правильно понимаю, что под головой ты понимаешь то, на что указывает Base, т.е. первый из списка массивов (вместе с дополнительной информацией)?
Да.
S>Если да, то об этом я и говорил, что добавление элемента в иммутабельном случае должно клонировать голову.
Нет, достаточно создать пустую голову нужного размера.
При конструировании нового VList если LastUsed не совпадает с нашим Offset мы создаем новый массив с Size = 1 и добавляем туда новый элемент, смотри картинку 2 в пдфке.
S>Но если речь о клонировании, то зачем нам создавать блок под 2*N элементов, если можно создать только под фактически необходимое кол-во элементов, ведь добавление очередного создаст новую голову.
Клонировать вообще не нужно.
Создавать голову в самом деле можно и меньшего размера, но это нарушит структуру. Судя по реализации в пдфке, такое нарушение выгоднее чем создание большой головы.
S>Знаком с ними. Их иммутабельность не вызывает никаких сомнений. Более того, добавление (с созданием нового списка) в лисповых списках должно быть намного быстрее VList-а именно в иммутабельной функциональщине. Т.е. cons против клонирования головы...
S>Либо я все еще чего-то не понимаю с этим VList-ом
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, samius, Вы писали:
FR>При конструировании нового VList если LastUsed не совпадает с нашим Offset мы создаем новый массив с Size = 1 и добавляем туда новый элемент, смотри картинку 2 в пдфке.
Спасибо, разобрался. Т.е речь не об полной иммутабельности, а об инкапсулированном изменяемом состоянии с locking-ом.
S>>Но если речь о клонировании, то зачем нам создавать блок под 2*N элементов, если можно создать только под фактически необходимое кол-во элементов, ведь добавление очередного создаст новую голову.
FR>Клонировать вообще не нужно. FR>Создавать голову в самом деле можно и меньшего размера, но это нарушит структуру. Судя по реализации в пдфке, такое нарушение выгоднее чем создание большой головы.
Тут сложно угадать, что выгоднее, т.к. мы не знаем, к какой голове продолжится добавление элементов и продолжится ли вообще.
S>>Знаком с ними. Их иммутабельность не вызывает никаких сомнений. Более того, добавление (с созданием нового списка) в лисповых списках должно быть намного быстрее VList-а именно в иммутабельной функциональщине. Т.е. cons против клонирования головы...
S>>Либо я все еще чего-то не понимаю с этим VList-ом
FR>Угу не понимаешь чуть-чуть
исправляюсь
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Вопрос на самом деле о том, насколько успешно можно сымитировать связный список (да, из ФЯ) на основе динамического массива. VD>Сама постановка задачи глупая. Краткий ответ — ни насколько.
Если тебе постановка задачи не нравится, мог бы не отвечать. Делать тебе что ли больше нечего?
ВВ>> "O(1) время добавления элементов в начало списка" — это все же техническая особенность связного списка, а вот иммутабельность уже особенность дизайна. VD>И то и другое особенность дизайна. Точнее особенность самой структуры данных.
Ага, масло масляное.
ВВ>>К примеру, простейший тест в Немерле — foreach для аррая и списка — показывает, что для в задаче последовательного перебора динамический массив быстрее более чем в 2 раза. Нехорошо как-то. VD>Это бред. Полнейший и махровый. Так вообще нельзя подходить к программированию. Нужно брать задачу и смотреть как ее лучше всего решать.
Бред? Правда?
Я вот прочитал в твоей статье — связные списки хорошо подходят *по производительности*, когда нужен последовательный перебор данных. А у меня задача такая — важна скорость последовательного перебора. И простейший тест показывает, что это мягко говоря не так.
И казалось бы, в чем проблема? Информация дана неправильно? Компилятор плохо оптимизирует переход по списку?
Не, проблема, оказывается, во мне и в том, что "так вообще нельзя подходить к программированию". Несерьезно, товарищ.
VD>Разница во времени затрачиваемом на перебор списка и массива ничтожна по сравнению со временем которое будет потрачено на вычисления, преобразования данных и т.п. Потом чистое время вообще не имеет смысла. Отдельно взятая задача в 99.999% случаев на современных компьютерах выполняется очень быстро! Смотреть надо на то насколько общая производительность приемлема для конкретной задачи. Может оказаться так, что задача отлично решается даже самым экстенсивными средствами. VD>Так что выжимать такты процессора из каждого перебора глупо. К тому же списки намного реже перебирают с помощью циклов. VD>Собственно тогда уж нужно задуматься над тем, что использование ФВП тоже дает оверхэд. Да и дотнет тоже не бесплатен. GC основанный на поколениях вносит оверхэд в любое присвоение указателя на ссылочный объект. Так давай откажемся и от дотнета и будем все писать на С! А там окажется, что и С вносит некоторый оверхэд. Так что здравствуй ассемблер?
К чему все это написано? Вопрос был, если хочешь, насколько нужна такая структура данных как связный список, если нужно поддерживать стандартные паттерны работы со связным списком. Тут были ответы, указывающие на вещи, на которые я внимание не обратил, но к чему поднимать эту твою песню, я не понимаю.
Вообще, я конечно понимаю, у тебя есть две любимые темы — "это лучше сделать на Немерле" и "преждевременное оптимизация — зло". Это хорошо, что темы есть любимые. У меня тоже есть любимые темы. Правда, они в основном весьма далеки от программирования. Но сколько же можно их повторять-то? Я тебя читаю с 2002 года, и все время, все время одно и то же. С той лишь разницей, что раньше вместо Немерле был C#. Это ж просто офигеть можно.
Форум называется "Философия". Тут "философские" беседы ведутся, понимаешь. Без конкретных как бы задач.
ВВ>>И длина, длина VD>Что длинна?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Если тебе постановка задачи не нравится, мог бы не отвечать. Делать тебе что ли больше нечего?
Ты как нибудь определился бы с тем нужен тебе ответ или нет.
А на неверно поставленный вопрос можно дать только один ответ. Я тебе его и дал.
ВВ>Бред? Правда?
Да, правда.
ВВ>Я вот прочитал в твоей статье — связные списки хорошо подходят *по производительности*, когда нужен последовательный перебор данных. А у меня задача такая — важна скорость последовательного перебора. И простейший тест показывает, что это мягко говоря не так.
Ты всегда читаешь только часть написанных букв вместо того чтобы понять смысл всего сказанного?
ВВ>И казалось бы, в чем проблема? Информация дана неправильно? Компилятор плохо оптимизирует переход по списку? ВВ>Не, проблема, оказывается, во мне и в том, что "так вообще нельзя подходить к программированию". Несерьезно, товарищ.
Ага. Несерьезно.
Кстати, я где-то сравнивал скорость перебора элементов списка и массива? Нет? Так о чем тогда речь?
VD>>Разница во времени затрачиваемом на перебор списка и массива ничтожна по сравнению со временем которое будет потрачено на вычисления, преобразования данных и т.п. Потом чистое время вообще не имеет смысла. Отдельно взятая задача в 99.999% случаев на современных компьютерах выполняется очень быстро! Смотреть надо на то насколько общая производительность приемлема для конкретной задачи. Может оказаться так, что задача отлично решается даже самым экстенсивными средствами. VD>>Так что выжимать такты процессора из каждого перебора глупо. К тому же списки намного реже перебирают с помощью циклов. VD>>Собственно тогда уж нужно задуматься над тем, что использование ФВП тоже дает оверхэд. Да и дотнет тоже не бесплатен. GC основанный на поколениях вносит оверхэд в любое присвоение указателя на ссылочный объект. Так давай откажемся и от дотнета и будем все писать на С! А там окажется, что и С вносит некоторый оверхэд. Так что здравствуй ассемблер?
ВВ>К чему все это написано?
Да, действительно не к чему. Тот кто не хочет понять, не поймет ничего сколько ему не объясняй.
ВВ>Вопрос был, если хочешь, насколько нужна такая структура данных как связный список, если нужно поддерживать стандартные паттерны работы со связным списком. Тут были ответы, указывающие на вещи, на которые я внимание не обратил, но к чему поднимать эту твою песню, я не понимаю.
Очень нужна для тех кто умеет ее использовать и пользуется языками представляющими для нее удобные инструменты, и совсем не нужна для тех кто пользоваться ею не умеет и не хочет учиться, а так же пользуется языками не предоставляющими адекватных инструментов ее использования.
ВВ>Вообще, я конечно понимаю, у тебя есть две любимые темы — "это лучше сделать на Немерле" и "преждевременное оптимизация — зло". Это хорошо, что темы есть любимые. У меня тоже есть любимые темы. Правда, они в основном весьма далеки от программирования. Но сколько же можно их повторять-то? Я тебя читаю с 2002 года, и все время, все время одно и то же. С той лишь разницей, что раньше вместо Немерле был C#. Это ж просто офигеть можно.
Не читай. Я не навязываюсь.
А темы отличные от программирования стоит обсуждать в соответствующих форумах.
ВВ>Форум называется "Философия". Тут "философские" беседы ведутся, понимаешь. Без конкретных как бы задач.
Форум называется "Философия программирования".
Вопрос твой к философии вообще не относится. Если честно, я бы вообще постыдился задавать такой вопрос. Это же равносильно признанию того, что не разбираешься в структурах данных.
ВВ>>>И длина, длина VD>>Что длинна?
ВВ>Длина списка.
И что с ней?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
ВВ>>Если тебе постановка задачи не нравится, мог бы не отвечать. Делать тебе что ли больше нечего? VD>Ты как нибудь определился бы с тем нужен тебе ответ или нет. VD>А на неверно поставленный вопрос можно дать только один ответ. Я тебе его и дал.
Вопрос с твоей позиции поставлен "идеологически неверно". Хорошо, смирись с этим. Я интересующие меня ответы получил. И не от тебя.
VD>Ага. Несерьезно. VD>Кстати, я где-то сравнивал скорость перебора элементов списка и массива? Нет? Так о чем тогда речь?
Что касается производительности, то списки довольно эффективны там, где требуется перебор элементов списка, добавления элементов в начало списка или преобразование списков, однако они уступают массивам, если требуется доступ к элементам списка по индексам, нужно знать длину списка, добавлять элементы в конец списка, а также по потреблению памяти.
По-моему из этого предложения вполне явно следует такой вывод.
ВВ>>К чему все это написано? VD>Да, действительно не к чему. Тот кто не хочет понять, не поймет ничего сколько ему не объясняй.
Ага, есть альтернативный вариант — эта тема здесь абсолютно не в тему.
VD>Вопрос твой к философии вообще не относится. Если честно, я бы вообще постыдился задавать такой вопрос. Это же равносильно признанию того, что не разбираешься в структурах данных.
Ну видимо создатели VList тоже не разбирались в структурах данных. Это только у тебя все либо черное, либо белое. Либо "правильные" языки, либо "неправильные".
Влад, оле, мне нужна *гибридная* *коллекция*. Массив не устраивает, список не устраивает. А вот VList по ходу вполне.
ВВ>>>>И длина, длина VD>>>Что длинна? ВВ>>Длина списка. VD>И что с ней?
Прикольно, а почему бы не сделать сцепку этих chunk-ов не на основе односвязанного списка, а на основе сбалансированного дерева? (Баланс должен быть по чанкам, а не элементам). Тогда доступ к хвосту и голове будет примерно равен по эффективности.
Только непонятно, что именно было изобретено в 2002-м, ибо страничную организацию динамических массивов нам читали еще в институте, равно как и популярное использование их в текстовых редакторах того времени.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Вопрос с твоей позиции поставлен "идеологически неверно". Хорошо, смирись с этим. Я интересующие меня ответы получил. И не от тебя.
Заметано!
VD>>Кстати, я где-то сравнивал скорость перебора элементов списка и массива? Нет? Так о чем тогда речь?
ВВ>
ВВ>Что касается производительности, то списки довольно эффективны там, где требуется перебор элементов списка, добавления элементов в начало списка или преобразование списков, однако они уступают массивам, если требуется доступ к элементам списка по индексам, нужно знать длину списка, добавлять элементы в конец списка, а также по потреблению памяти.
ВВ>По-моему из этого предложения вполне явно следует такой вывод.
У тебя очень богатая фантазия. Из этой цитаты следует только то, что перебор списков (кстати, не любой) довольно эффективен.
Кстати, ты знаком с О-нотацией?
Не подскажешь какова алгоритмическая сложность перебора списка и массива (в О-нотации)?
ВВ>Ага, есть альтернативный вариант — эта тема здесь абсолютно не в тему.
Как скажешь! Как скажешь...
VD>>Вопрос твой к философии вообще не относится. Если честно, я бы вообще постыдился задавать такой вопрос. Это же равносильно признанию того, что не разбираешься в структурах данных.
ВВ>Ну видимо создатели VList тоже не разбирались в структурах данных.
А он задает такие вопросы как ты? Можно пруфлинк?
ВВ>Это только у тебя все либо черное, либо белое.
Ага. В моем понимании некоторые понятия дуальные. Скажем понимание предмета. Оно или есть, или нет.
ВВ>Либо "правильные" языки, либо "неправильные".
Однако, причем тут Nemerle? (с)
ВВ>Влад, оле, мне нужна *гибридная* *коллекция*. Массив не устраивает, список не устраивает. А вот VList по ходу вполне.
Але, гараж? Не бывает идеальных коллекций. У всего есть свои преимущества и недостатки. VList здесь не исключение.
Ты, кстати, сколько минут о нем знаешь? Видел ли его реализации?
Я тебя огорчу, но перебор элементов в нем будет ни чем не быстрее нежели в односвязанных списках.
Кстати, ты успел прочесть о том, что для ссылки на элемент этого VLiat нужно использовать структуру данных состоящую из двух элементов (ссылки на часть и индекс в ней)?
ВВ>>>>>И длина, длина VD>>>>Что длинна? ВВ>>>Длина списка. VD>>И что с ней?
ВВ>Дык нету ее
Ее украли?
Или ты сокрушаешься о том, что ее приходится вычислять? Ну, дык особенность структуры данных. В VList ее тоже придется вычислять. Но есть радостная весть. Ее можно не использовать или хранить отдельно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
ВВ>>Что касается производительности, то списки довольно эффективны там, где требуется перебор элементов списка, добавления элементов в начало списка или преобразование списков, однако они уступают массивам, если требуется доступ к элементам списка по индексам, нужно знать длину списка, добавлять элементы в конец списка, а также по потреблению памяти.
ВВ>>По-моему из этого предложения вполне явно следует такой вывод. VD>У тебя очень богатая фантазия. Из этой цитаты следует только то, что перебор списков (кстати, не любой) довольно эффективен.
Как скажешь, хотя, честно говоря, когда читаешь фразу "Х эффективен, а У медленнее массива", то ее как бы обычно понимаешь, что Х по крайней мере не медленнее.
Впрочем, даже понятно, почему оно медленнее. Код из релиза:
Кстати, многовато nop-ов для релиза.
VD>Кстати, ты знаком с О-нотацией? VD>Не подскажешь какова алгоритмическая сложность перебора списка и массива (в О-нотации)?
Более бредовый вопрос не мог спросить?
Сложность какого перебора? Сложность доступа по индексу и сложность обращения к полю?
VD>>>Вопрос твой к философии вообще не относится. Если честно, я бы вообще постыдился задавать такой вопрос. Это же равносильно признанию того, что не разбираешься в структурах данных. ВВ>>Ну видимо создатели VList тоже не разбирались в структурах данных. VD>А он задает такие вопросы как ты? Можно пруфлинк?
Хорошо, я задал неправильный вопрос. Раскаиваюсь. Предлагаю закрыть эту тему, а то я пойду в форум Немерле и задам там кучу еще более неправильных вопросов. У меня даже кое-какие задумки уже есть.
ВВ>>Это только у тебя все либо черное, либо белое. VD>Ага. В моем понимании некоторые понятия дуальные. Скажем понимание предмета. Оно или есть, или нет. ВВ>>Либо "правильные" языки, либо "неправильные". VD>Однако, причем тут Nemerle? (с)
Какой Немерле?
ВВ>>Влад, оле, мне нужна *гибридная* *коллекция*. Массив не устраивает, список не устраивает. А вот VList по ходу вполне. VD>Але, гараж? Не бывает идеальных коллекций. У всего есть свои преимущества и недостатки. VList здесь не исключение.
Я разве просил идеальную коллекцию?
VD>Ты, кстати, сколько минут о нем знаешь? Видел ли его реализации?
Немного. Не видел. Ты можешь предложить что-то лучше?
Мне нужны:
1. Перебор по модели голова-хвост
2. Добавление в начало и конец
3. Потокобезопасность
4. Знать длину
VD>Я тебя огорчу, но перебор элементов в нем будет ни чем не быстрее нежели в односвязанных списках. VD>Кстати, ты успел прочесть о том, что для ссылки на элемент этого VLiat нужно использовать структуру данных состоящую из двух элементов (ссылки на часть и индекс в ней)?
Нет, я вообще эту статью не читал.
ВВ>>>>>>И длина, длина VD>>>>>Что длинна? ВВ>>>>Длина списка. VD>>>И что с ней? ВВ>>Дык нету ее VD>Ее украли?
Именно.
VD>Или ты сокрушаешься о том, что ее приходится вычислять? Ну, дык особенность структуры данных. В VList ее тоже придется вычислять. Но есть радостная весть. Ее можно не использовать или хранить отдельно.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Кстати, многовато nop-ов для релиза.
Если не включена поддержка pdb (что может быть и в релизе), nop-ов быть не должно.
В прочем, они выкидываются джитом когда тот работает в оптимизирующем режиме.
VD>>Кстати, ты знаком с О-нотацией? VD>>Не подскажешь какова алгоритмическая сложность перебора списка и массива (в О-нотации)?
ВВ>Более бредовый вопрос не мог спросить? ВВ>Сложность какого перебора? Сложность доступа по индексу и сложность обращения к полю?
Последовательного... с начала к концу. Ты же его тестировал.
ВВ>Хорошо, я задал неправильный вопрос. Раскаиваюсь. Предлагаю закрыть эту тему,
ОК
ВВ>а то я пойду в форум Немерле и задам там кучу еще более неправильных вопросов. У меня даже кое-какие задумки уже есть.
Если по делу, а не ради флэйма, то добро пожаловать. Если найдешь что, только спасибо скажем.
ВВ>>>Это только у тебя все либо черное, либо белое. VD>>Ага. В моем понимании некоторые понятия дуальные. Скажем понимание предмета. Оно или есть, или нет. ВВ>>>Либо "правильные" языки, либо "неправильные". VD>>Однако, причем тут Nemerle? (с)
ВВ>Какой Немерле?
Это такой риторический вопрос задаваемый когда люди переключают тему без основания на то.
ВВ>>>Влад, оле, мне нужна *гибридная* *коллекция*. Массив не устраивает, список не устраивает. А вот VList по ходу вполне. VD>>Але, гараж? Не бывает идеальных коллекций. У всего есть свои преимущества и недостатки. VList здесь не исключение.
ВВ>Я разве просил идеальную коллекцию?
А что ты искал то? Ты начал с какого-то странного заявления о недостатках списков при переборе, а теперь перешел к VList, который тоже список. Ты уж определись о чем ты говоришь и что хочешь.
VD>>Ты, кстати, сколько минут о нем знаешь? Видел ли его реализации?
ВВ>Немного. Не видел. Ты можешь предложить что-то лучше?
Я могу тебе гарантировать, что когда ты попробуешь использовать тот же VList на практике, то окажется, что он тоже нужен тебе не всегда, а только в некоторых случаях, так как в других те же массивы будут эффективнее.
ВВ>Мне нужны:
ВВ>1. Перебор по модели голова-хвост ВВ>2. Добавление в начало и конец ВВ>3. Потокобезопасность ВВ>4. Знать длину
Ну, ты приплыл. VList крайне не эффективен при добавлении в конец. Он при этом еще хуже массивов, так как для массива хотя бы один раз память придется перевыделиь.
В общем, снова не верная постановка вопроса. Не "мне нужно", а "для задач X выгоднее применять Y нежели Z". И только так!
VD>>Я тебя огорчу, но перебор элементов в нем будет ни чем не быстрее нежели в односвязанных списках. VD>>Кстати, ты успел прочесть о том, что для ссылки на элемент этого VLiat нужно использовать структуру данных состоящую из двух элементов (ссылки на часть и индекс в ней)?
ВВ>Нет, я вообще эту статью не читал.
Прочти. Там еще обсуждение есть. Очень любопытно.
Пойми. Я не против VList или массивов. И я не рекламирую списки. Я просто уверяю тебя в том, что они все хороши в некоторых ситуациях и плохи в других. Если подходят и массивы и списки, то выбор определяется с одной стороны производительностью которая у массивов зачастую лучше, или удобством, которое зачастую могут быть лучше у списков (если язык умеет с ними работать).
VD>>Или ты сокрушаешься о том, что ее приходится вычислять? Ну, дык особенность структуры данных. В VList ее тоже придется вычислять. Но есть радостная весть. Ее можно не использовать или хранить отдельно.
ВВ>Ага, и пересчитывать каждый раз.
Большая часть алгоритмов работающих со списками не нуждается в знании о длине. Посему и сокрушаться не о чем. Кроме того если длинна нужно не внутри самого вложенного цикла самого критичного алгоритма, то ее вычисление скорее всего не окажет никакого влияния на общую производительность, так как при этом не выделяется ни одного объекта, а сам алгоритм весьма шустр и имеет сложность O(n). Скажем если стоит задача скопировать значение списка в List[T], то намного эффективнее вычислить длину списка и один раз задать длинную List[T] нежели добавлять значения по одному элементу рассчитывая на автоматическое приращение List[T]-а. Происходит это потому, что даже одно выделение памяти и копирование элементов операция более медленная нежели вычисление длинны списка.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Прикольно, а почему бы не сделать сцепку этих chunk-ов не на основе односвязанного списка, а на основе сбалансированного дерева? (Баланс должен быть по чанкам, а не элементам). Тогда доступ к хвосту и голове будет примерно равен по эффективности.
Потому что VList создавался как замена односвязному списку используемому в большинстве ФЯ и поэтому задача эффективного доступа к концу списка не ставилась.
V>Только непонятно, что именно было изобретено в 2002-м, ибо страничную организацию динамических массивов нам читали еще в институте, равно как и популярное использование их в текстовых редакторах того времени.
VD>Ну, ты приплыл. VList крайне не эффективен при добавлении в конец. Он при этом еще хуже массивов, так как для массива хотя бы один раз память придется перевыделиь.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
Есть. Дело в том, что связные списки существуют, а динамические массивы — нет.
Я не шучу. Сделать настоящий динамический массив, то есть массив, который без каких-либо переаллокаций увеличивал бы свой размер, в общем случае невозможно. Причина банальна — дальше в адресном пространстве может не быть свободного места. И тогда произойдет новое выделение памяти большего размера с копированием данных , после чего старый массив удаляется. А на это нужно время, во-первых, и память, во-вторых. Например, имея динамический массив на 1 Г, увеличить его размер до 1 Г + 64 К, в 32-битной среде не удастся вообще.
Правда, есть VirtualAlloc с резервированием и коммитированием по частям. В этом случае можно зарезервировать большой кусок адресного пространства, но не выделять память на весь этот размер. Адресное пространство не жалко (до поры до времени). Потом можно коммитировать от начала и далее маленькими кусочками. Так что массив сможет действительно расти без переаллокаций. Это уже ближе к истине, но все же в пределах зарезервированного размера.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>А есть ли какое-нибудь преимущество у связных списков перед динамическими массивами, кроме, так сказать, чистоты концепции?
PD>Есть. Дело в том, что связные списки существуют, а динамические массивы — нет.
PD>Я не шучу.
http://en.wikipedia.org/wiki/Dynamic_array
В двух словах — динамический массив это не тот массив, который меняет свои размеры динамически, а структура данных (std::vector — это реализация динамического массива и она существует).
Здравствуйте, samius, Вы писали:
S>В двух словах — динамический массив это не тот массив, который меняет свои размеры динамически, а структура данных (std::vector — это реализация динамического массива и она существует).
Ну не надо же все понимать буквально...
Конечно, std::vector существует, и он есть динамический массив. И про него верно все, что я сказал — увеличение его размера после того, как исчерпан текущий размер, приведет к переаллокации и копированию.
vector::capacity
Returns the number of elements that the vector could contain without allocating more storage.
vector::resize
Specifies a new size for a vector.
void resize(size_type _Newsize, _Ty _Val)
{ // determine new length, padding with _Val elements as neededif (size() < _Newsize)
_Insert_n(end(), _Newsize - size(), _Val);
else if (_Newsize < size())
erase(begin() + _Newsize, end());
}
void _Insert_n(const_iterator _Where,
size_type _Count, const _Ty& _Val)
{ // insert _Count * _Val at _Where
//...else if (_Capacity < size() + _Count)
{ // not enough room, reallocate
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%if (_Capacity < size() + _Count)
_Capacity = size() + _Count;
pointer _Newvec = this->_Alval.allocate(_Capacity);
Этот пример не опровергает существование std::vector-а. Он только лишь подтверждает твои слова об специфике перевыделений при нехвататке адресного пространства. Но с этим-то никто не спорил.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>Павел! S>Ты сказал что настоящих динамических массивов не существует, я привел ссылку где написано что именно принято считать динамическим массивом.
Мне не хотелось бы заниматься игрой в дефиниции. Массивов (называй их хоть динамическими, хоть как-то иначе), которые могли бы изменять свой размер без переаллокаций, не существует. А термин "динамический массив" вполне существует, но только там всегда будет переаллокация. Со всеми вытекающими.
PD>>
S>Этот пример не опровергает существование std::vector-а.
Еще бы! Вот здорово бы было, если бы я смог опровергнуть его существование, употребляя его
>Он только лишь подтверждает твои слова об специфике перевыделений при нехвататке адресного пространства. Но с этим-то никто не спорил.
А я именно на этом и акцентировал внимание в своем постинге. Ответ-то был на сообщение Василия Воронкова, ну вот я и отметил, что без массовых операций при добавлении нового элемента динамический массив существовать не может. А список может — этого я не писал, но подразумевалось само собой.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>Мне не хотелось бы заниматься игрой в дефиниции. Массивов (называй их хоть динамическими, хоть как-то иначе), которые могли бы изменять свой размер без переаллокаций, не существует. А термин "динамический массив" вполне существует, но только там всегда будет переаллокация. Со всеми вытекающими.
PD>А я именно на этом и акцентировал внимание в своем постинге. Ответ-то был на сообщение Василия Воронкова, ну вот я и отметил, что без массовых операций при добавлении нового элемента динамический массив существовать не может. А список может — этого я не писал, но подразумевалось само собой.
Не сомнваюсь, что Василий об этом знает. А для меня было новостью, что динамических массивов не существует.
