Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, maggot, Вы писали:
M>>Дык можно же просто массив отсортировать. И бинарным поиском по нему искать. Как раз и будет логарифмический поиск.
DR>Данные могут быть текстовым файлом, могут быть множеством N-мерных векторов с N≥2.
Для ведения конструктивного разговора, попробуем определеиться с терминологией.
1. Разделим контейнеры на имплементацию и их интерфейс, например массив с доступом по целому ключу может быть реализован через хеш таблицу, список элементов через последовательный массив в памяти.
С точки зрения интерфейсов мы можем практически все контейнеры реализовать через другие. Именно поэтому дальнейшее рассмотрение именно с этой точки зрения я считаю неинтересным.
С точки зрения имплементации мы сталкиваемся с .... И вот начинается реальная жизнь , оказывается имплементации имеют четкие временные характеристики и расходы на память ... и открывается что существует архитектура процессора , алгоритмическая сложность и т.п.
Таким образом если вас не интересует производительность (а точнее у вас есть огромный запас производительности ) тогда вам совершенно все равно как реализуются те или инные интерфейсы , и спор что лучше или хуже переходит в область какая абстракция лучше описывает прикладную задачу.
2. Определимся что мы добразумеваем под массивом с точки зрения интерфейса. Если бы я пробовал ввести некую классификацию , я бы обратился к основам алгоритмов и операции совершаемые над контейнерами.
Под интерфейсом массива буду подразумевать контейнер с операцией взятия по целочисленному индексу и двунаправленный перебор элементов.
Ремарка: часто термин "list" подразумевает Ordered sequence of elments и совсем не одно или двунаправленный список.
попробую расположить сценарии использования контейнеров встречающиеся ЛИЧНО для меня в порядке убывания частоты использования
а) Последовательность элементов не сохраняющая порядок. 70%
б) Последовательность элементов сохраняющая порядок. 15%
в) Ассоциативный контейнер. 10%
г) Все отстальное требующее специфической производительности или расхода памяти 5%.
Попробую добавить примеров.
а) Последовательность элементов не сохраняющая порядок. 70%
Это когда необходимо получить или отдать набор объектов и провести над каждым некую операци.
как пример
for(i=0; i < s; i++)
{
array[s].execute()
}
В данном примере массив используется не как ассоциативный контейнер а только лишь как множество элементов доступ к которым можно переписать как
IEnumerable<> , IList<> , range<> и т.п.
Рассматривая современные процессоры убежденно утверждаю , для хранения таких последовательностей лучше использовать непрерывный кусок памяти и досуп организовать приращениями к указателю на пямять.
Вот отсюда я считаю идет мысль что контейнером по умолчанию берется массив. А вот интерфейс к нему наиболее частый это некий ISequanceIterator а совсем не оператор доступа по индексу.
б) Последовательность элементов сохраняющая порядок. 15%
тоже самое , массив сохраняет порядок.
в) Ассоциативный контейнер. 10%
Ни в коем случае , только если индексом служит целое число в определенном диапазоне.
г) Все отстальное требующее специфической производительности или расхода памяти 5%.
необходимо разбирать отдельно .
Подрезюмирую мыслю.
Очень часто авторы путают интерфейс и реализацию. Например понимая что операция индексирования используется не очень часто вводится утверждение что наиболее часто используемы й контейнер это список "list" , подразумевая лишь иниерфейс доступа к элементам. Другие бездумно переводят эту терминологию у себя в голове на другой уровень и получается неразбериха типа
"После некоторого размышления я понял, что вопрос не такой уж и глупый. Я понял, что я не использую массивы в Эрланге, они там просто не нужны. Программируя на С и С++, я постоянно их использовал, потому что я был практически вынужден их использовать. Но в Эрланге на передний план выходят списки."
Хотя после анализа становится понятно что имелисьь виду просто коллекции объектов Ordered sequances.
Очень повезло програмистам на C++ где существует STL в котором дизайн был изначально правилен, интерфейсы и данные четко разделены , терминология выверенна и однозначна.
Здравствуйте, minorlogic, Вы писали:
M> Очень часто авторы путают интерфейс и реализацию. Например понимая что операция индексирования используется не очень часто вводится утверждение что наиболее часто используемы й контейнер это список "list" , подразумевая лишь иниерфейс доступа к элементам. Другие бездумно переводят эту терминологию у себя в голове на другой уровень и получается неразбериха типа
M> "После некоторого размышления я понял, что вопрос не такой уж и глупый. Я понял, что я не использую массивы в Эрланге, они там просто не нужны. Программируя на С и С++, я постоянно их использовал, потому что я был практически вынужден их использовать. Но в Эрланге на передний план выходят списки."
M> Хотя после анализа становится понятно что имелисьь виду просто коллекции объектов Ordered sequances.
Мне показалось, что автор говорил как раз про интерфейсы, а не про реализацию. Это, во-первых. Во-вторых,общеизвестно, что никакие массивы на основе эрланговских списков не лежат.
Безусловно, некоторые путают интерфейс и релазацию, но автор не из их числа.
... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>
Социализм — это власть трудящихся и централизованная плановая экономика.
Здравствуйте, LaPerouse, Вы писали:
LP>Мне показалось, что автор говорил как раз про интерфейсы, а не про реализацию. Это, во-первых. Во-вторых,общеизвестно, что никакие массивы на основе эрланговских списков не лежат.
Я понимаю, я говорю что (тут я боюсь ошибиться , поправь меня плиз) эрланговских списки это не структура linked list а интерфейс типа object sequence который очень хорошо (в других языках и подходах) реализуется как массив (массив как имплементация).
Мысль что интерфейс доступа к коллекции по индексу является в большинстве МОИХ применений лишней, я подтверждаю.
LP>Безусловно, некоторые путают интерфейс и релазацию, но автор не из их числа.
В данном случае я автора не критикую , а наоборот пытаюсь уточнить. Потому что легко человеку неподкованному терминологически , перейти на суждения что C++ std::list надо использовать вместо std::vector. Я даже не удивлюсь если в этом топике ктонить сделает подобные выводы.
ЗюЫю
К моему огромному сожалению как в минимум 2х мейстримовых языках C/C++ проход по абстрактной коллекции и операции с элементами синтаксически некрасив и не всегда удобен. Именно поэтому проход по object sequence зачастую организуется как цикл по индексу.
И с этим давно необходимо ченить делать. (как пример BOOST :: FOR_EACH, boost::range, iterators, iterators adaptors, pointer ariphmetic )
Здравствуйте, Qbit86, Вы писали: Q>Предположим, создатель библиотеки пишет функцию, которая принимает коллекцию, и в реализации часто-часто делает вставки в начало. У него есть два варианта: 1) Получить в аргументе LinkedList<T>; 2) Получать в аргументе IList<T> но писать в документации и в комментариях, что функция будет медленно работать на коллекциях, не поддерживающих быструю вставку. И в том, и в другом случае нарушается инкапсуляция. Но первый способ, имхо, честнее.
ИМХО, второй вариант предпочтительней. Потому что потом функции перестанет быть нужна быстрая вставка в начало, а анахронизм в виде жесткого интерфейса останется. А документацию всегда можно изменить, это ее главное предназначение.
Здравствуйте, LaPerouse, Вы писали:
LP>Мне показалось, что автор говорил как раз про интерфейсы, а не про реализацию. Это, во-первых. Во-вторых,общеизвестно, что никакие массивы на основе эрланговских списков не лежат.
"As I'm programming I haven't seen an instance where an array is better for storing information than another form thereof. "
Он использует термин storing, так что может об имплементации.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, LaPerouse, Вы писали:
LP>>Мне показалось, что автор говорил как раз про интерфейсы, а не про реализацию. Это, во-первых. Во-вторых,общеизвестно, что никакие массивы на основе эрланговских списков не лежат.
M>Я понимаю, я говорю что (тут я боюсь ошибиться , поправь меня плиз) эрланговских списки это не структура linked list а интерфейс типа object sequence который очень хорошо (в других языках и подходах) реализуется как массив (массив как имплементация).
В функциональных языках используются односвязные списки как по интерфейсу, так и по реализации с выполнением типичных операций за O(1). В Erlang также.
M>Мысль что интерфейс доступа к коллекции по индексу является в большинстве МОИХ применений лишней, я подтверждаю.
У меня также.
M>ЗюЫю M>К моему огромному сожалению как в минимум 2х мейстримовых языках C/C++ проход по абстрактной коллекции и операции с элементами синтаксически некрасив и не всегда удобен. Именно поэтому проход по object sequence зачастую организуется как цикл по индексу.
Мало того, из-за этой неудобности многие используют std::vector там, где он совершенно не нужен.
... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>
Социализм — это власть трудящихся и централизованная плановая экономика.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, LaPerouse, Вы писали:
LP>>Мне показалось, что автор говорил как раз про интерфейсы, а не про реализацию. Это, во-первых. Во-вторых,общеизвестно, что никакие массивы на основе эрланговских списков не лежат.
M>Я понимаю, я говорю что (тут я боюсь ошибиться , поправь меня плиз) эрланговских списки это не структура linked list а интерфейс типа object sequence который очень хорошо (в других языках и подходах) реализуется как массив (массив как имплементация).
По поводу Object Sequence — в большинстве языков как раз таки это абстрактный интерфейс IEnumeration, который может быть чем угодно.
... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>
Социализм — это власть трудящихся и централизованная плановая экономика.
Здравствуйте, Serginio1, Вы писали: S>Вернее доступ будет ln(N/(размер_массива*коэффициент_заполнения)), вставка ~размер массива.
Нам известны техники, позволяющие держать делитель N достаточно высоким для обеспечения логарифмической асимптотики.
S>Все по аналогии с Б+ деревьями, только сверху КЧ деревья, только вместо индекса в узле указывается количество элементов в поддереве, которое корректируется при вставке,удалении.
Совершенно верно.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, minorlogic, Вы писали:
M>Я понимаю, я говорю что (тут я боюсь ошибиться , поправь меня плиз) эрланговских списки это не структура linked list а интерфейс типа object sequence который очень хорошо (в других языках и подходах) реализуется как массив (массив как имплементация).
В ерланге, как и в подавляющем большинстве ФЯ используется immutable cons-list. Конечно это интерфейс, а не реализация, но опять же в подавляющем большинстве случаев он реализован как односвязный список. Альтернативной реализацией является, например, VList.
Как массив cons-list реализовать нельзя — он потеряет персистентность (http://en.wikipedia.org/wiki/Purely_functional).
Здравствуйте, samius, Вы писали: S>Да я не возражаю. И не предлагаю ничего переписывать. Когда понадобится — можно и ToList позвать и если напряжет перфоманс, то написать самому этот ленивый список.
Я только одного не понимаю — что нам мешает добавить в проект один маленький класс:
public static class List
{
private class RangeList : IList<int>
{
private int _start;
private int _count;
public RangeList(int start, int count)
{
_start = start;
_count = count;
}
#region IList<int> Members
public int IndexOf(int item)
{
int pos = item — _start;
if (pos >= 0 && pos < _count)
return pos;
else
return -1;
}
public void Insert(int index, int item)
{
throw new InvalidOperationException("Range is read-only");
}
public void RemoveAt(int index)
{
throw new InvalidOperationException("Range is read-only");
}
public int this[int index]
{
get
{
if (index >= _count || index < 0)
throw new ArgumentOutOfRangeException("index", index, "out of range");
return _start + index;
}
set
{
throw new InvalidOperationException("Range is read-only");
}
}
#endregion
#region ICollection<int> Members
public void Add(int item)
{
throw new InvalidOperationException("Range is read-only");
}
public void Clear()
{
throw new InvalidOperationException("Range is read-only");
}
public bool Contains(int item)
{
return IndexOf(item) >= 0;
}
public void CopyTo(int[] array, int arrayIndex)
{
for (int i = _start; i < _count; i++)
array[i + arrayIndex] = i;
}
public int Count
{
get { return _count; }
}
public bool IsReadOnly
{
get { return true; }
}
public bool Remove(int item)
{
throw new InvalidOperationException("Range is read-only");
}
#endregion
#region IEnumerable<int> Members
public IEnumerator<int> GetEnumerator()
{
for (int i = _start; i < _count; i++)
yield return i;
}
public static IList<Int32> Range(int start, int count)
{
long num = (start + count) — 1L;
if ((count < 0) || (num > 2147483647L))
{
throw new ArgumentOutOfRangeException("count", count, "out of range");
}
return new RangeList(start, count);
}
} S>Делать ленивый список из Range — и правда дурь
S>Гораздо интереснее для подобных целей (чем Enumerable.Range) ленивый список принимающий размер и Func<int, T>. Но цели слишком экзотичны, чтобы вставлять такое в FCL.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, AndrewVK, Вы писали:
AVK>Это было бы очень плохо. Потому что от ленивого энумератора перейти к списку очень легко, а вот в обратном направлении все намного печальнее.
Не понял, в чем печаль. Для "ленивого" списка никаких проблем реализовать ленивый GetEnumerator я не вижу. А результат Range вполне может быть именно ленивым списком. Пример я тут где-то в ветке привел.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, samius, Вы писали: S>>Да я не возражаю. И не предлагаю ничего переписывать. Когда понадобится — можно и ToList позвать и если напряжет перфоманс, то написать самому этот ленивый список. S>Я только одного не понимаю — что нам мешает добавить в проект один маленький класс: S>public static class List
[skipped] S>}
Ничего не мешает, при необходимости.
Просто кое-что вызывает у меня недоумение: часть методов класса Enumerable заточена на работу со списками и коллекциями (Count, ElementAt, Contains, ...). А часть методов возвращает именно перечислители, но в этих перечислителях (Range, Repeat, ...) есть вся необходимая информация для реализации ленивых списков, но она не используется.
Range мог бы возвращать ленивый список (без изменения типа результата метода). Вреда бы от этого (имхо) не было, но и польза была бы не сильно велика. Вот и все. Т.е. на месте разработчиков класса Enumerable я бы сделал ленивые списки, а не ленивые перечислители. Но т.к. они этого не сделали, приколю булавочку и при необходимости буду делать это сам. Претензий-то в общем нет.
Здравствуйте, samius, Вы писали: S>Ничего не мешает, при необходимости.
Ну, тогда, имхо, у вас всё в порядке. S>Просто кое-что вызывает у меня недоумение: часть методов класса Enumerable заточена на работу со списками и коллекциями (Count, ElementAt, Contains, ...).
Нет. Всё наоборот — эти методы заточены на работу с ленивыми списками. Они как раз помогают перейти от ленивого списка к энергичному.
S>Range мог бы возвращать ленивый список (без изменения типа результата метода). Вреда бы от этого (имхо) не было, но и польза была бы не сильно велика.
Пользы, очевидно, не было бы совсем. Кто бы там занимался приведением результата к IList?
S>Вот и все. Т.е. на месте разработчиков класса Enumerable я бы сделал ленивые списки, а не ленивые перечислители. Но т.к. они этого не сделали, приколю булавочку и при необходимости буду делать это сам. Претензий-то в общем нет.
Вопрос, на самом деле, по большой части философский. А надо ли было вообще делать Range в IEnumerable?
Или было бы достаточно List.Range, который я привел?
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>>Вот и все. Т.е. на месте разработчиков класса Enumerable я бы сделал ленивые списки, а не ленивые перечислители. Но т.к. они этого не сделали, приколю булавочку и при необходимости буду делать это сам. Претензий-то в общем нет. S>Вопрос, на самом деле, по большой части философский. А надо ли было вообще делать Range в IEnumerable? S>Или было бы достаточно List.Range, который я привел?
Тут надо разобраться с тем, как предполагается использовать List.Range и Enumerable.Range.
Что-то мне подсказывает, что задачи, в которых потребуется именно List.Range не будут связаны с linq-ом, а будут иметь отношение к каким-то более низкоуровневым операциям.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, Sinclair, Вы писали:
S>И для многих сценариев (например, со вставками в середину) массивы в чистом виде непригодны.
Не так все просто. Все зависит от размера массива и, что важно, размера его элементов.
Вставка в начало/середину массива гораздо лучше оптимизируется современными процессорами.
Для эффективной вставки в середину список кстати должен быть двунаправленным.
Что еще больше усугубляет проблему выбора.
S>Также ограничением может служить доступный объем адресного пространства, так что для совсем-совсем больших структур массивы малопригодны.
И даже в этом случае массивы могут оказаться лучшим выбором ибо у них наименьшие накладные расходы из всех коллекций — больше информации влезет в "доступный объем адресного пространства".
Здравствуйте, c-smile, Вы писали:
CS>Вставка в начало/середину массива гораздо лучше оптимизируется современными процессорами.
А можно мне как-то пояснить, что за оптимизации имеются в виду?
CS>Для эффективной вставки в середину список кстати должен быть двунаправленным.
Не обязательно.
CS>И даже в этом случае массивы могут оказаться лучшим выбором ибо у них наименьшие накладные расходы из всех коллекций — больше информации влезет в "доступный объем адресного пространства".
Если рассматривать дерево массивов, то накладные расходы можно свести к пренебрежимому минимуму. При этом остается возможность прозрачной подгрузки листьев в кэш, что позволяет таки выйти за пределы адресного пространства.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
