Если есть список, который после заполнения необходимо отсортировать.
Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

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

P>Если есть список, который после заполнения необходимо отсортировать.
P>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

В среднем, имхо так:

Структура SortedList скорее всего будет реализована на базе дерева и будет иметь дополнительный overhead как по памяти, так и по быстродействию.
Быстрее будет создать список, а затем его отсортировать.

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

Б>В среднем, имхо так:

Б>Структура SortedList скорее всего будет реализована на базе дерева и будет иметь дополнительный overhead как по памяти, так и по быстродействию.
Б>Быстрее будет создать список, а затем его отсортировать.

Вставкой у нас точно будет nlogn, а сортировкой можем на n^2 нарватся.

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

S>Вставкой у нас точно будет nlogn, а сортировкой можем на n^2 нарватся.
среднее время сортировки вствками n²

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

P>Если есть список, который после заполнения необходимо отсортировать.
P>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

Большой ли список, часто ли повторяется процесс, список чего именно, какой язык? О каких вообще порядках размеров и о каком типе данных речь?

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

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

P>>Если есть список, который после заполнения необходимо отсортировать.
P>>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

S>Большой ли список, часто ли повторяется процесс, список чего именно, какой язык? О каких вообще порядках размеров и о каком типе данных речь?
Размер списка от 0 до 400, процесс повторяется часто, List<(string,decimal)>, C#.

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

P>>>Если есть список, который после заполнения необходимо отсортировать.
P>>>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

S>>Большой ли список, часто ли повторяется процесс, список чего именно, какой язык? О каких вообще порядках размеров и о каком типе данных речь?
P>Размер списка от 0 до 400, процесс повторяется часто, List<(string,decimal)>, C#.

Маленький сравнительно. Я бы сказал заполнять список и потом сортировать, да и всё. Хорошо было бы радикально переработать как-то алгоритм, так, чтобы вообще не нужен был ни список, ни заполнение, ни сортировка. Я всегда считал самым классным вариантом — переработать алгоритм так, чтобы он стал вообще не нужен, а сразу получался ответ. Но здесь, если этого нельзя сделать, ничего особо не получится выиграть.

Нормальный вариант, либо взять List и сортировать, либо взять SortedDictionary (а повторы бывают в данных?), набить его и потом переписать в List или куда тебе его надо. SortedList бестолковый, он устроен на двух массивах внутри, у него вставки не алё. SortedDictionary лучше, устроен как дерево массивов или ещё какая-то такого типа каракатица, но на этом размере я сомневаюсь, что будет выигрыш какой-то.

Если довольно часто повторяется, в смысле, скажем, от миллиона раз, то можно подумать аллокации поэкономить (например, никогда не делать новый List<>, а только делать .Сlear старому), ну и вообще подумать, что можно повторно использовать.

Распараллеливать процесс, где всего 400 элементов, и обработки никакой нету, не выглядит перспективно.

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

P>Если есть список, который после заполнения необходимо отсортировать.
P>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

Если список хранится, как линейный, то построить список, сразу вставляя элемент в нужное место, будет стоить O(n^2), а отсортировать можно за время O(n * Ln(n))

А вот если кранить его не списком, а сбалансированным деревом, то построение списка со вставкой элементов на нужное место будет стоить O(n * Ln(n)).

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

Pzz>А вот если кранить его не списком, а сбалансированным деревом, то построение списка со вставкой элементов на нужное место будет стоить O(n * Ln(n)).

Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?

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

S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?

Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для каждой вставки.

Здравствуйте, Sharov, Вы писали:
S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?
Конечно.

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

P>Если есть список, который после заполнения необходимо отсортировать.
P>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?

Если под "быстрее" имеется в виду время в секундах, то надо сделать и сравнить. Рассуждения про O() к ответу в секундах не приведут. Тем более что O() имеет смысл при N стремящемся в бесконечность, а 400 — это далеко не бесконечность.

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

S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?

Речь изначально шла о списке.

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

P>Если есть список, который после заполнения необходимо отсортировать.
P>Что быстрее: сразу вставлять элемент в нужное место в списке или после заполнения всего списка его сортировать?
В свое время делал Б+ деревья http://rsdn.org/article/alg/tlsd.xml

Автор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.

Заполнения и последующая сортировка однозначно быстрее (правда нужно конечно учитывать объемы, на больших объемах уже сортировка слиянием может быть выгодна http://rsdn.org/forum/philosophy/577195.1

Автор: Serginio1
Дата: 22.03.04

)

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

S>>Большой ли список, часто ли повторяется процесс, список чего именно, какой язык? О каких вообще порядках размеров и о каком типе данных речь?
P>Размер списка от 0 до 400, процесс повторяется часто, List<(string,decimal)>, C#.

Вероятно (полагаю, но не замерял), значительное время сортировки тратится на перепихивание ValueTuple по значению в метод сравнения. Потому, решение вопроса сортировать ли после вставки, или делать вставку в отсортированный список, не сильно повлияют на скорость исполнения.

Предлагаю сравнить время сортировки List<(string,decimal)> с List<Tuple<string, decimal>> и List<int>, где int — индекс в массиве (string, decimal).