Лучшая структура данных для ближайшего соседа в 1 измерении

Question

У меня есть список значений (1-мерный), и я хотел бы знать лучшую структуру данных / алгоритм для нахождения ближайшего к значению запроса, которое у меня есть.Большинство решений (все?), Которые я нашел для вопросов здесь, предназначены для двух или более измерений.Кто-нибудь может предложить мне подход для моего случая?

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

Answer 1

Если вам нужно что-то быстрее, чем O (log (n)), которое вы можете легко получить с помощью отсортированного массива или двоичного дерева поиска, вы можете использовать van Emde Boas Tree .Деревья vEB дают вам O (log (log (n))) для поиска ближайшего элемента с обеих сторон.

Answer 2

Если время вставки не имеет значения, то бинарный поиск в отсортированном массиве является самым простым способом достижения времени запроса O (log N).Каждый раз, когда элемент добавляется, сортируйте все.Для каждого запроса выполните бинарный поиск.Если совпадение найдено, верните его.В противном случае двоичный поиск должен возвращать индекс элемента, в который он должен был быть вставлен.Используйте этот индекс, чтобы проверить два соседних элемента и определить, какой из них ближе к точке запроса.

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

Answer 3

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

Answer 4

Сортируйте список и используйте бинарный поиск, чтобы найти искомый элемент, а затем сравните ваших левых и правых соседей.Вы можете использовать массив с доступом O (1).

Что-то вроде:

int nearest(int[] list, int element) {

    sort(list);
    int idx = binarySearch(element, list);

    // make sure you are accessing elements that exist
    min = (element - list[idx-1] <= list[idx+1] - element) ? idx-1 : idx+1;

    return list[min];
}

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

РЕДАКТИРОВАТЬ: Для этого вам придется переместить сортировку из этого метода

Answer 5

Использование OCaml's Set:

module S = Set.Make(struct type t = int let compare = compare end)

let nearest xs y =
  let a, yisin, b = S.split y xs in
  if yisin then y
  else
      let amax, bmin = S.max_elt a, S.min_elt b in
      if abs (amax - y) < abs (bmin - y) then amax else bmin

Кстати, вы можете оценить мой n-й ближайший соседний образец из OCaml для ученых и .Журнал F # .NET статья Обходные сети: n-е ближайшие соседи .