Пользовательский параметр для поиска в отсортированном списке быстрее, чем обычный двоичный

Question

Ниже приведен сценарий использования :

• Сортированный список типа DateTime, с детализацией в миллисекундах
• Поиск ближайшего DateTime, который удовлетворяет предоставленному predicate делегату
• Производительность является проблемой, так как List имеет 100K + записей, общий промежуток времени от 10 до минимального и максимального индекса и множество частых вызовов (50+ / прогон), влияет на производительность

Что мы сейчас делаем, пользовательский бинарный поиск следующим образом?

 public static int BinaryLastOrDefault<T>(this IList<T> list, Predicate<T> predicate)
 {
            var lower = 0;
            var upper = list.Count - 1;

            while (lower < upper)
            {
                var mid = lower + ((upper - lower + 1) / 2);
                if (predicate(list[mid]))
                {
                    lower = mid;
                }
                else
                {
                    upper = mid - 1;
                }
            }

            if (lower >= list.Count) return -1;
            return !predicate(list[lower]) ? -1 : lower;
}

Могу ли я использовать Словарь , чтобы сделать его O (1)?

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

Ниже приводится вариант, который я рассматриваю

• Структура данных типа Dictionary<int,SortedDictionary<DateTime,int>>
• Общая продолжительность DateTime Продолжительность между самым высоким и самым низким значением составляет 10 часов ~ 10 *3600* 1000 мс = 36 миллионов мс
• Создано ведер по 60 секунд каждый, общее количество элементов ~ 36 million / 60 K = 600
• Для любого предоставленного значения DateTime теперь легко найти Bucket, где ограниченное количество значений может быть сохранено как SortedDictionary, с ключом в качестве значения DateTime и исходным индексом в качестве значения, таким образом, при необходимости данные могут быть перечислены для поиска ближайший индекс

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

Answer 1

Я провел несколько тестов производительности, используя собственный BinarySearch метод List<T>.Логика поиска ближайшего DateTime показана ниже:

public static DateTime GetNearest(List<DateTime> source, DateTime date)
{
    var index = source.BinarySearch(date);
    if (index >= 0) return source[index];
    index = ~index;
    if (index == 0) return source[0];
    if (index == source.Count) return source[source.Count - 1];
    var d1 = source[index - 1];
    var d2 = source[index];
    return (date - d1 < d2 - date) ? d1 : d2;
}

Я создал случайный список из 1 000 000 отсортированных дат, охватывающий промежуток времени от 10 до мин.Затем я создал список одинакового размера с несортированными случайными датами для поиска, охватывающий немного больший промежуток времени.Затем изменил сборку на Release и начал тестирование.Результат показал, что можно выполнить более 800 000 поисков менее чем за секунду, используя только одно ядро ​​относительно медленной машины.

Затем я увеличил сложность теста, выполнив поиск в List<(DateTime, object)> содержащий 1 000 000 элементов, поэтому для каждого сравнения требуется два дополнительных вызова функции dateSelector, которая возвращает свойство DateTime каждого ValueTuple.Результат: 350 000 запросов на поток в секунду.

Я еще больше усложнил задачу, используя ссылочные типы в качестве элементов, заполнив List<Tuple<DateTime, object>> 1 000 000 кортежей.Производительность все еще была довольно приличной: 270 000 запросов на поток в секунду.

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