M>

M>Правда состоит в том, что, если вы не занимаетесь низкоуровневым программированием, массивы (и даже векторы) редко необходимы или оптимальны дл большинства задач. Самая яркая особенность массивов — это константное время доступа к любому значению по порядковуму номеру. Проблма состоит в том, что мало какая задача требует константного времени доступа к значениям по порядковым значениям. Массивы в основном применяются как коллекции данных, для чего больше подходит список.

M>А как часто вы используете массивы?

Мы не используем, но понимаем, где они нужны.

Это вторая часть правды: в программе на массивах компилятору проще проверять зависимости.

Именно поэтому Фортран до сих пор рвёт другие ЯП в высокопроизводительных вычислениях.

Здравствуйте, Sinclair, Вы писали:

SS>Это сильно зависит от набора выполняемых операций. Подсказка: список — далеко не единственная альтернатива массиву.
S>И для многих сценариев (например, со вставками в середину) массивы в чистом виде непригодны. Также ограничением может служить доступный объем адресного пространства, так что для совсем-совсем больших структур массивы малопригодны.
Лучше дерево в качестве листьев массивов сцепленных между собой и количеством элементов в поддереве для веток. Это будет называться дерево списков массивов

Здравствуйте, samius, Вы писали:

S>А тут прибежали дотнетчики, которые привыкли списком обзывать List<T>, который на самом деле вектор а не список, т.к. имеет константное время доступа

Это проблемы перевода и терминологии. В английском есть термин list, что как выше было сказано — упорядоченный набор элементов. А конкретные структуры данных, реализовывающие список — это array и linked list. Так что дотнетчики тут примерно в таком же положении, как и плюсовики, привыкшие под словом list подразумевать linked list.

Здравствуйте, Serginio1, Вы писали:
S> Лучше дерево в качестве листьев массивов сцепленных между собой и количеством элементов в поддереве для веток. Это будет называться дерево списков массивов

КЧ дерево или дерево массивов с количеством элементов в поддереве. Листья содержат массивы и количество элементов в массиве и ссылки на предыдущий и следующий лист. Аналог Б+ деревьев, но в качестве виртуального массива с поиском Ln(N) и вставкой равной дполвине длины массива

Здравствуйте, Qbit86, Вы писали:

G>>Опять-таки требование параметром конкретного типа нарушает инкапсуляцию.

Q>Это одно из проявлений Закона Дырявых Абстракций.
Это просто красивая фраза, сказанная Спольки, не более того.

Q>Предположим, создатель библиотеки пишет функцию, которая принимает коллекцию, и в реализации часто-часто делает вставки в начало.
Вставляет в начало переданного списка? Я не уверен что так стоит делать.

Q>У него есть два варианта: 1) Получить в аргументе LinkedList<T>; 2) Получать в аргументе IList<T> но писать в документации и в комментариях, что функция будет медленно работать на коллекциях, не поддерживающих быструю вставку. И в том, и в другом случае нарушается инкапсуляция. Но первый способ, имхо, честнее. Те же рассуждения остаются верными при замене (вставки-в-начало, LinkedList) ← (обращения-по-индексу, List).
На самом деле вариантов гораздо больше.

Q>Если считать временные гарантии частью контракта, то эта ситуация чем-то сродни отрицательной изменчивости (по Коплиену). Можно провести далёкую аналогию с некорректным наследованием квадрата от прямоугольника.
Далекии аналогии не интересуют. Доказательство по аналогии неверно.


G>>Реализация метода может меняться, менять при этом контракт нежелательно.

Q>Если бы всё было так просто, то разработчики BCL не предоставляли бы разных коллекций, а только IList<T> и IDictionary<T>.
Все равно нужны конкретные классы.

Q>В одной версии фреймворка их реализация по умолчанию использовала бы динамический массив и дерево. В следующей версии фреймворка разработчики именили бы реализацию на связный список и хэш-таблицу под предлогом «не надо закладываться на детали реализации». А у пользователей бы изменилась асимптотика их кода (причём не обязательно в худшую сторону).
В BCL нету функций, которые под такое попадают.

Здравствуйте, Qbit86, Вы писали:

G>>Опять-таки требование параметром конкретного типа нарушает инкапсуляцию.

Q>Это одно из проявлений Закона Дырявых Абстракций. Предположим, создатель библиотеки пишет функцию, которая принимает коллекцию, и в реализации часто-часто делает вставки в начало. У него есть два варианта: 1) Получить в аргументе LinkedList<T>; 2) Получать в аргументе IList<T> но писать в документации и в комментариях, что функция будет медленно работать на коллекциях, не поддерживающих быструю вставку. И в том, и в другом случае нарушается инкапсуляция. Но первый способ, имхо, честнее. Те же рассуждения остаются верными при замене (вставки-в-начало, LinkedList) < (обращения-по-индексу, List).

Вообще, такой дизайн библиотеки заставляет заподозрить ее автора в тяжких грехах.
Что должна делать такая функция? Для чего ей вообще потребовалась mutable коллекция? Почему важны именно вставки в начало, а не в конец?

G>>Реализация метода может меняться, менять при этом контракт нежелательно.

Q>Если бы всё было так просто, то разработчики BCL не предоставляли бы разных коллекций, а только IList<T> и IDictionary<T>. В одной версии фреймворка их реализация по умолчанию использовала бы динамический массив и дерево. В следующей версии фреймворка разработчики именили бы реализацию на связный список и хэш-таблицу под предлогом «не надо закладываться на детали реализации». А у пользователей бы изменилась асимптотика их кода (причём не обязательно в худшую сторону).

Ход мысли неясен. Закладываться, очевидно, нужно на то, что существенно. А на несущественное закладываться не нужно. Но ты почему-то с маниакальным упорством доказываешь, что в общем IList<T> светить вредно, и предлагаешь зашивать конкретный класс.
Это сильно ограничивает возможности по использованию твоей библиотеки, ради каких-то неясных бенефитов.
Ну вот представь себе, что TextReader работал бы не с любым Stream, а, к примеру, только с MemoryStream. Из соображений "а вдруг пользователь передаст поток, у которого плохая асимптотика операций". Ну и нахрена такой ридер будет нужен?

Не надо бояться нарушений performance-гарантий. Если пользователя не устроит кубическая реализация (которая может вполне хорошо работать для N=1..4), то он поменяет тип используемой коллекции. Это его дело — следить за перформансом приложения.
Почему ты думаешь, что любая реализация IList[] будет страдать от плохой производительности? Вообще-то все реализации во фреймворке, кроме одного класса, индексируются вполне нормально.

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:
S>> Лучше дерево в качестве листьев массивов сцепленных между собой и количеством элементов в поддереве для веток. Это будет называться дерево списков массивов

S>КЧ дерево или дерево массивов с количеством элементов в поддереве. Листья содержат массивы и количество элементов в массиве и ссылки на предыдущий и следующий лист. Аналог Б+ деревьев, но в качестве виртуального массива с поиском Ln(N) и вставкой равной дполвине длины массива

А для чего конкретно этот комбайн лучше?

Здравствуйте, _DAle_, Вы писали:

S>>> Лучше дерево в качестве листьев массивов сцепленных между собой и количеством элементов в поддереве для веток. Это будет называться дерево списков массивов

S>>КЧ дерево или дерево массивов с количеством элементов в поддереве. Листья содержат массивы и количество элементов в массиве и ссылки на предыдущий и следующий лист. Аналог Б+ деревьев, но в качестве виртуального массива с поиском Ln(N) и вставкой равной дполвине длины массива

_DA>А для чего конкретно этот комбайн лучше?

Например для работы с текстом http://www.rsdn.ru/article/cpp/segmented_list.xml

Автор(ы): Алексей Семенюк
Дата: 31.10.2004
В статье приводится пример реализации нестандартного контейнера, позволяющего обеспечить приемлемую скорость доступа к произвольному элементу и вставки/удаления в произвольную позицию.

Здравствуйте, Serginio1, Вы писали:

S>КЧ дерево или дерево массивов с количеством элементов в поддереве. Листья содержат массивы и количество элементов в массиве и ссылки на предыдущий и следующий лист. Аналог Б+ деревьев, но в качестве виртуального массива с поиском Ln(N) и вставкой равной дполвине длины массива
Ну то есть не поиском, а доступом к i-тому элементу. И вставку можно свести к ln(N). Либо вообще на неё забить, рассчитывая вместо нее на операции слияния деревьев.

Здравствуйте, Mamut, Вы писали:

M>А как часто вы используете массивы? ;)

Всегда использую массивы по умолчанию (C++). Другие структуры данных использую только если они действительно требуются и без них по каким-то причинам не обойтись.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:

S>>КЧ дерево или дерево массивов с количеством элементов в поддереве. Листья содержат массивы и количество элементов в массиве и ссылки на предыдущий и следующий лист. Аналог Б+ деревьев, но в качестве виртуального массива с поиском Ln(N) и вставкой равной дполвине длины массива
S>Ну то есть не поиском, а доступом к i-тому элементу. И вставку можно свести к ln(N). Либо вообще на неё забить, рассчитывая вместо нее на операции слияния деревьев.
Вернее доступ будет ln(N/(размер_массива*коэффициент_заполнения)), вставка ~размер массива. Все по аналогии с Б+ деревьями, только сверху КЧ деревья, только вместо индекса в узле указывается количество элементов в поддереве, которое корректируется при вставке,удалении.

Здравствуйте, samius, Вы писали:

S>Кстати, считаю, что было бы здорово, если бы Enumerable.Range и подобные ему методы возвращали бы IList<int>.

Это было бы очень плохо. Потому что от ленивого энумератора перейти к списку очень легко, а вот в обратном направлении все намного печальнее.

Здравствуйте, AndrewVK, Вы писали:

AVK>Здравствуйте, samius, Вы писали:

S>>Кстати, считаю, что было бы здорово, если бы Enumerable.Range и подобные ему методы возвращали бы IList<int>.

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

Здравствуйте, Mamut, Вы писали:

M>via http://damienkatz.net/2008/12/arrays_whats_the_point_good_qu.html

M>[q]
M>В чем фишка массивов? Хороший вопрос

M>[code]

M>ЗЫ. Сорри за корявоватый перевод. Оригинал — по ссылке в начале поста
да, часто, я ж веб программист получил массив (набор строк из базы), отобразил.
P.S. массивы в erlang появились cравнительно недавно, и начало счета там отличается от списков, непонятно зачем...

Здравствуйте, samius, Вы писали:

S>от ленивого энумератора к списку перейти легко, но можно было бы перейти к ленивому списку если бы разработчики расстарались.

Старатся пришлось бы очень долго.

S> От ленивого списка перейти к ленивому энумератору было бы очень просто в этом случае.

А еще лучше оставить все энумераторы ленивыми, как оно сейчас и есть. А если тебе все же понадобится коллекция, заполненная элементами по порядку (зачем, кстати?), а не функция, то всегда можно позвать ToList().

Здравствуйте, AndrewVK, Вы писали:

AVK>Здравствуйте, samius, Вы писали:

S>>от ленивого энумератора к списку перейти легко, но можно было бы перейти к ленивому списку если бы разработчики расстарались.

AVK>Старатся пришлось бы очень долго.
Нет, довольно легко написать ленивые списки для Range, Repeat, Reverse...
здесь

Автор: samius
Дата: 01.12.08

я уже писал.

S>> От ленивого списка перейти к ленивому энумератору было бы очень просто в этом случае.

AVK>А еще лучше оставить все энумераторы ленивыми, как оно сейчас и есть. А если тебе все же понадобится коллекция, заполненная элементами по порядку (зачем, кстати?), а не функция, то всегда можно позвать ToList().
Да я не возражаю. И не предлагаю ничего переписывать. Когда понадобится — можно и ToList позвать и если напряжет перфоманс, то написать самому этот ленивый список.

Делать ленивый список из Range — и правда дурь

Гораздо интереснее для подобных целей (чем Enumerable.Range) ленивый список принимающий размер и Func<int, T>. Но цели слишком экзотичны, чтобы вставлять такое в FCL.

Здравствуйте, samius, Вы писали:

S>Нет, довольно легко написать ленивые списки для Range, Repeat, Reverse...

А в текущем варианте ничего писать не надо.

Здравствуйте, Mamut, Вы писали:

M>В чем фишка массивов? Хороший вопрос

В чём же вопрос?

#if MOON_PHASE == 0
typedef std::vector<X> range_type;
#elif MOON_PHASE == 1
typedef std::deque<X> range_type;
#elif MOON_PHASE == 2
typedef std::list<X> range_type;
#elif MOON_PHASE == 3
typedef boost::iterator_range<some_iterator> range_type;
#else
typedef boost::iterator_range<any_iterator<X> > range_type;
#endif

range_type get_a_sequence_of_X();

Утиная типизация, в общем.

Насчет массивов: если контейнер нужен только для чтения и изменения отдельных элементов и он не гигантских размеров, то массив — идеальный вариант. А таких случаев большинство.

Здравствуйте, Tilir, Вы писали:

T>у и редкие алгоритмические исключения. Когда хоть убей нужен логарифмический поиск и приходится делать дерево.

Дык можно же просто массив отсортировать. И бинарным поиском по нему искать. Как раз и будет логарифмический поиск.

Здравствуйте, Mamut, Вы писали:

M>А как часто вы используете массивы?

Всё зависит от языка...

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

Различные структуры данных, где используются указатели (списки, деревья) при небольшом количестве элементов неэффективны по сравнению с массивами из-за использования дополнительной памяти на указатели, и из-за того что требуют быстрого случайного доступа к оперативной памяти, которого нет (последовательный быстрее, тк данные кешируются). До определенного количества элементов вообще нет смысла использовать что то кроме массивов/сортированных массивов.