Постоянное время биннинга значений

Скажем, у меня есть вектор значений, которые представляют верхние границы классов для классификации (bin) значений. Так, например, вектор { 1, 3, 5, 10 } представляет бины [0, 1[, [1, 3[, [3], 5[и [5,10[. Как реализовать классификацию случайного значения V в одном из этих классов (0,1,2,3) за постоянное время? Тривиально пройти список границ и остановиться, как только V превысит верхнюю границу корзины; но это O(n) по числу бинов; Я хочу сделать это в постоянное время.

Я думал, что это было тривиально, прежде чем я на самом деле набрал код, создав таблицу поиска, разделив каждое V на определенное значение в зависимости от границ класса, а затем используя (округленный) результат деления, чтобы найти номер корзины в Справочная таблица. Но я нахожу это намного сложнее, чем я думал, чтобы сделать это универсальным способом, который минимизирует размер таблицы поиска, оставаясь при этом точным, независимо от пропорционального расстояния между границами бина; и таким образом, который работает для всех реальных ценностей. С Google'ing я нахожу только алгоритмы, которые определяют границы корзин, по крайней мере, используя термины, которые я сделал.

2 ответа

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


Таблица поиска - хорошая идея, но значения с плавающей запятой затрудняют это. Если число цифр конечно, вы можете рассмотреть вопрос о том, чтобы таблица поиска была представлена ​​как по существу три (дерево, где каждый уровень представляет цифру).

Таким образом, для {1, 2.5, 5, 9}ваше дерево будет выглядеть примерно так:

                              root
  /   /          /          /  |  \   \   \   \   \
 0   1          2          3   4   5   6   7   8   9
          /     |     \
       2.0 ... 2.5 ... 2.9

Каждый листовой узел будет содержать значение, указывающее, к какому интервалу он принадлежит, поэтому
0 будет установлен на 0,
1, 2.0 - 2.4 все будут установлены в 1,
2,5 - 2,9, 3 - 4 будут установлены на 2,
5 - 9 будет установлен на 3

Запрос будет просто начинаться с корня и многократно переходить к дочернему узлу, соответствующему следующей цифре в номере, который мы ищем (если вы посмотрите вверх на 2,65 в приведенном выше дереве, сначала перейдите к 2, затем к 2.6, затем к, так как это лист, вы останавливаетесь и возвращаете его значение, которое равно 1).

Временная сложность для запроса будет O(d), где d число значащих цифр в вашем векторе, а сложность пространства O(nd),

Это может показаться не особенно эффективным, но имейте в виду, что d количество цифр - например, это будет d = log m с m быть максимально возможным значением, если мы говорим о натуральных числах.


O(log n) Это довольно тривиально, если вы просто настраиваете двоичное дерево поиска (BST), содержащее все значения в векторе, сопоставленные с их исходными индексами.

Поиск будет выглядеть очень похоже на то, как вы будете искать BST - начните с корня и двигайтесь влево или вправо, пока не найдете значение, за исключением того, что в этом случае вы отмечаете каждый посещаемый вами узел и возвращаете сопоставленный индекс ближайшего значения. это не больше Некоторые API имеют методы, которые в основном делают это для вас (например, std::map в C++).

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

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

  1. Ожидаемые числа являются целыми числами или границы являются целыми числами или имеют ограниченную точность. Это позволяет округлять (пол) число перед проверкой по таблице соответствия и резко сокращает необходимые записи для таблицы.

  2. Разница между максимальной и минимальной границами не может быть слишком большой. Допустим, мы знаем, что точность границ равна 0,5, а min равно 1, а max равно 10, тогда для таблицы поиска требуется (10-1)/0.5 = 18 записей.

Проверка для первой и последней группы (меньше min и больше max) выполняется с помощью простых проверок if, которые не влияют на сложность.

Другие вопросы по тегам