Есть ли в C # своего рода SortedList <double>, который позволяет быстро запрашивать (с LINQ) ближайшее значение?

Question

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

Я посмотрел на SortedList<double, double>, и он вполне мне подходит. Однако, поскольку мне не нужны явные пары ключ / значение. мне кажется, это излишне, и мне интересно, смогу ли я сделать быстрее.

Условия:

• Структура инициализируется только один раз и никогда не изменяется (без вставки / удаления)
• Количество значений находится в диапазоне 100 тыс.
• Структура часто запрашивается с новыми ссылками, которые должны выполнить fast .
• Для простоты и скорости может быть возвращено значение набора чуть ниже эталона, а не ближайшее значение
• Я хочу использовать LINQ для запроса, если возможно, для простоты кода.
• Я хочу использовать сторонний код, если это возможно. Доступен .NET 3.5.
• Скорость важнее, чем объем памяти

В настоящее время я использую следующий код, где SortedValues является вышеупомянутым SortedList

    IEnumerable<double> nearest = from item in SortedValues.Keys
                                  where item <= suggestion
                                  select item;
    return nearest.ElementAt(nearest.Count() - 1);

Могу ли я сделать быстрее?

Также я не уверен на 100%, действительно ли этот код безопасен. IEnumerable, тип возврата моего запроса по определению больше не сортируется. Тем не менее, модульное тестирование с большой базой данных испытаний показало, что это на практике, так что это работает для меня. Есть ли у вас намеки относительно этого аспекта?

P.S. Я знаю, что есть много похожих вопросов, но ни один из них не отвечает моим конкретным потребностям. Особенно существует такая структура данных C #, как словарь, но без значения , но спрашивающий просто хочет проверить существование и ничего не найти.

Answer 1

То, как вы делаете это, невероятно медленно, так как он должен искать с начала списка каждый раз, чтобы получить производительность O (n).

Лучший способ - поместить элементы в список, а затем отсортировать список. Вы говорите, что вам не нужно менять содержимое после инициализации, поэтому достаточно один раз отсортировать.

Затем вы можете использовать List<T>.BinarySearch, чтобы найти элементы или найти точку вставки элемента, если он еще не существует в списке.

Из документов:

Возвращаемое значение

Начинающийся с нуля индекс пункт в отсортированном List<T>, если предмет найден; в противном случае отрицательное число, которое является побитовым дополнение индекса следующего элемент, который больше, чем элемент или, если нет большего элемента, побитовое дополнение графа.

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

Answer 2

Может быть не полезно для вас сейчас, но .Net 4 имеет класс SortedSet в BCL.

Answer 3

Я думаю, что это может быть более элегантным, как показано ниже: Если ваши товары не отсортированы:

double nearest = values.OrderBy(x => x.Key).Last(x => x.Key <= requestedValue);

Если ваши товары отсортированы, вы можете опустить вызов OrderBy ...