Поиск ключа из структуры данных на основе диапазона

Question

Например, если у меня есть следующий сценарий

1. Если ключ находится в диапазоне 1-4, выберите A.
2. Если ключ находится в диапазоне 5-6, товыберите B.

Если есть запрос на получение значения, скажем, key = 2, тогда я должен вернуть A, для 5, вернуть B и так далее.Что такое хорошая структура данных для удержания этой ассоциации?Я мог создать хэш-карту, сохранив 1-A, 2-A, 3-A, 4-A, 5-B и 6-B, но хотел проверить, есть ли лучший способ добиться этого.

Answer 1

использование хэш-карты для каждого элемента в диапазоне кажется слишком широким, что, если диапазон (1-2 ^ 20)?а что если это двойной?хранить их будет слишком дорого.

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

Теперь нам также нужно будет сохранить для каждого из них истинный диапазон (поэтомуесли у нас есть 1-4,8-9 и мы ищем 7, мы узнаем, что это недействительно, когда мы достигнем 4/8).поэтому, если ключ находится в допустимом диапазоне, мы достигнем его верхней / нижней границы при поиске!

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

ops должен быть примерно таким (псевдокод):

add (lower,upper,value):
   tree.add(lower/*key*/,(lower,upper,value))
   tree.add(upper/*key*/,(lower,upper,value))
search (key):
   node = tree.search(key)
   if node.lower <= key <= node.upper: 
      return node.value
   return KEY_NOT_IN_TREE_ERROR
del(lower,upper):
  tree.del(lower)
  tree.del (upper)

каждый из этих операций будет O (logn), медленнее, чем хеш, но он будет потреблятьнамного меньше места.

Answer 2

Амит верен.С диапазонами, которые не перекрываются, достаточно упорядоченной структуры данных.Чтобы быть немного более понятным:

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

Answer 3

Вы можете создать пары <interval,associated value> и построить дерево сегментов .Он будет работать нормально с перекрывающимися интервалами.

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

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

Answer 4

Лучше использовать объект класса для хранения в качестве ключа hashmap.

Здесь в классе вы можете определить поля как верхнюю, нижнюю и должны переопределять методы equals и hashCode.

В равных вы можете написать логику для сравнения верхней и нижней границ ключевого объекта между this.upperbound и this.lower границей.

Чтобы получить значение, создайте ключевой объект с таким же верхним пределом = нижний предел = ключ_вал;