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

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

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

Условия:

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

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

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

Я могу сделать быстрее?

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

P.S. Я знаю, что существует много подобных вопросов, но ни один на самом деле не отвечает на мои определенные потребности. Особенно существует эта Структура данных C# Как Словарь, Но Без Значения, но корреспондент просто хочет проверить, существование не находит что-либо.

8
задан Community 23 May 2017 в 11:48
поделиться

3 ответа

[11386382-

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

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

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

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

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

индекс на основе нуля Пункт в сортировке список , Если товар найден; В противном случае А. Отрицательное число, которое побитовой дополнение индекса следующего элемент, который больше элемента или, Если нет большего элемента, побитовое дополнение к количеству.

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

9
ответ дан 5 December 2019 в 19:00
поделиться

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

1
ответ дан 5 December 2019 в 19:00
поделиться

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

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

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

-1
ответ дан 5 December 2019 в 19:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: