Повысит ли производительность бинарный поиск по LinkedList<T> для вставки значения в середину списка отсортированных значений?

Question

Мне нужно создать отсортированный список, добавляя по одному элементу за раз. Поэтому я решил пойти с LinkedList<T>, Поскольку он эффективен в операциях вставки. Но при поиске нужного места, кажется, это займет гораздо больше времени. Я использую линейный поиск, чтобы получить местоположение. Если я использую бинарный поиск, чтобы получить правильное местоположение с помощью ElementAt метод, это увеличит производительность? Согласно этому, все еще это - операция O(n). Как вы думаете? Если это так, есть ли какая-либо другая лучшая структура данных для работы? Потому что, если я использую другую структуру данных, при вставке нового значения в середину мне придется сместить все данные после этого местоположения на одну позицию, что, очевидно, нежелательно.

Answer 1

Ваш вопрос имеет несколько заблуждений.

Увеличит ли производительность двоичный поиск по LinkedList для вставки значения в середину списка отсортированных значений?

Бинарный поиск имеет смысл только для отсортированной коллекции. LinkedList<T> не один Это порядок вставки, относящийся к коллекции. Чтобы выполнить бинарный поиск на LinkedList<T>:

• вам придется либо отсортировать связанный список, что не только очень неэффективно (операция со связанным списком), но и слишком много работы для простой вставки

• или вам придется поддерживать порядок сортировки во время самой вставки, вставляя в правильное положение, что является слишком большой работой снова.

Из вашего вопроса я понимаю, что вы хотите, чтобы порядок сортировки относился к коллекции, но вставки должны иметь более быструю (в отличие от O(n) характеристику, скажем, типичную List<T>). Мое предложение будет использовать отсортированный тип коллекции в.NET. E сть SortedSet<T> в system.dll, Это не позволит вам иметь дубликаты, так как это набор, и в этом случае вы можете реализовать пользовательский SortedBag<T> (или же SortedList<T> или как там), как показано здесь.

Я использую линейный поиск, чтобы получить местоположение.

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

Если я использую бинарный поиск, чтобы получить правильное местоположение с помощью ElementAt метод, это увеличит производительность

ElementAt Метод не выполняет бинарный поиск. В лучшем случае он проверяет, является ли тип коллекции IList<T> и использует индексатор соответственно. Нет, в вашем случае это не имеет значения для производительности.

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

Вы правы, вставляя в середине структуры на основе массива, как List<T> является операцией O(n). Я не уверен, если вам нужна операция с индексами, но это будет дороже. Вы можете либо иметь отсортированный тип коллекции с эффективными вставками, которые не будут иметь смысла в индексах, либо вы можете иметь индексированный отсортированный тип коллекции, но вставки будут O(n). Это обмен вы должны заплатить.

Answer 2

Для вашей цели вам, вероятно, будет лучше использовать класс SortedDictionary (или, возможно, SortedList)

SortedDictionary дает O(log n) время вставки и извлечения.