Структура данных для «интерполированного» поиска в таблице

Question

У меня есть коллекция двумерных точек, которые представляют функцию с 1 переменной. Учитывая случайное входное значение, я должен выбрать ближайшее значение. Пример:

Curve: (1,5) (2,8) (5,9)

Вход: 3 Выход: 8

Мое главное беспокойство - скорость, пространство не так важно. Какая структура данных будет лучше?

РЕДАКТИРОВАТЬ : таблица статическая, она не изменится во время выполнения

Answer 1

Это зависит от того, является ли таблица статической или динамической.

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

Если данные являются динамическими, я бы выбрал вариант B + Tree (хотя любая сбалансированная древовидная структура должнаРабота).По сути, тот же алгоритм, но вы будете проверять узлы-братья, а не просто проверять соседние ячейки массива.

Answer 2

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

result = (x < 3.5
            ? (x < 1.5
                ? 5
                : 8
              )
            : 9
         );

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

Если вы не возражаете против использования макроса, вы можете немного упростить его написание, например:

#define M(a,middle,b) (x < (middle) ? (a) : (b))

result = M( M(5, 1.5, 8), 3.5, 9);

Единственный способ победить - это жестко запрограммированный поиск по хешу (с помощью оператора switch).

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