Быстрый поиск в памяти в диапазоне от + 5M записей таблицы

Question

У меня есть таблица базы данных с + 5M статические записи на месте. Простая структура: (начало int, завершение int, result int). Поэтому у меня есть определенный INT, и мне нужно найти соответствующий результат (int). В настоящее время таблица поиска находится в БД, но она должна находиться в памяти, скорее всего, в среде без доступа к базе данных.

Мое решение должно выполнять эту логику без доступа к базе данных в памяти и сверхбыстро, поскольку мне нужно обрабатывать 1000 транзакций в секунду. Размер набора немного меньше 50 МБ, поэтому я мог бы перебросить все это в память и запустить поиск по нему, за этот пост: Doing a range lookup in C# - how to implement. Но я не знаю, как это будет работать в таком масштабе.

• Я предварительно загружаю этот стол «при запуске»? Это может занять некоторое время.
• Любой способ загрузить таблицу в некоторый .dat-файл и иметь суперэффективный просмотр во время выполнения?

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

Answer 1

Бинарные поиски очень быстрые. Для поиска ответа двоичный поиск по 50M-записи требует только 27 сравнений. Просто загрузите его в память и используйте привязку Range, которую вы связали.

Если вы нашли это очень медленный процесс, начать оптимизацию:

• Изменить объект Range на структуру вместо класса
• Hand-кода свой собственный двоичный алгоритм поиска, который (а) реализует компаратор равенство непосредственно вместо вызова в IEqualityComparer и (b) использует указатели и другие небезопасные трюки, чтобы отключить проверку границ массива при выполнении поиска.

Answer 2

Диапазона код поиска связывание выполняет бинарный поиск, поэтому производительность будет O(log n). Я не думаю, что вы можете сделать лучше, чем для поиска диапазона. Поиск HashSet<T> - это O (1), но вы не можете использовать эту структуру для поиска диапазона.

5 миллионов записей на самом деле не огромная сумма. Я предлагаю вам внедрить доказательство концепции с кодом, на который вы ссылаетесь, на оборудование, которое вы будете использовать в производстве, и измерять производительность.

Answer 3

Возможно, вы можете положить это в последовательный файл и загрузить его при запуске. 50 МБ выйдет из диска менее чем за секунду. И даже если вам пришлось анализировать его как текстовый файл, вы должны иметь возможность создать таблицу за секунду. 5 миллионов записей просто не так велики, когда вы обрабатываете их процессором с частотой 2 ГГц (или быстрее).

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

Должно быть достаточно легко загрузить что-то вроде этого. Просто запустите его, а затем посмотрите, сколько времени потребуется, скажем, 1,000,000 поисков. Что-то вроде:

var clock = Stopwatch.StartNew(); 
for (int i = 0; i < NumIterations; ++i) 
{ 
    int val = GetRandomValueToSearchFor(); // however you do that 
    Ranges.BinarySearch(val, RangeComparer); 
} 
clock.Stop(); 
// time per iteration is clock.TotalMilliseconds/NumIterations 

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