Карта от целочисленных диапазонов до произвольных одиночных целых

Question

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

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

Например, диапазонами могут быть [0, 70], называемые r_a, [101, 150], называемые r_b, и [201, 400], называемые r_c. Входы в r_a отображаются в 1, в r_b отображаются в 2, а r_c отображаются в 3. Все, что не в r_a, r_b, r_c отображается в 0.

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

Есть ли лучший способ выполнить сопоставление, чем алгоритм на основе бинарного поиска? Еще лучше, есть какая-нибудь библиотека C ++, которая это уже делает?

Answer 1

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

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

Например, это один из возможных подходов. Давайте предположим, что мы отображаем диапазон [ int, int ] на значение int. Давайте представим наши диапазоны как закрытые-открытые диапазоны, т.е. если исходный диапазон равен [0, 70], давайте вместо этого рассмотрим диапазон [0, 71). Кроме того, давайте используем значение 0 в качестве «зарезервированного» значения, которое означает «нет отображения» (как вы и просили в своем вопросе)

const int EMPTY = 0;

Все, что вам нужно сделать, это объявить карту от int до int:

typedef std::map<int, int> Map;
Map map;

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

map[0] = r_a;
map[71] = EMPTY;

map[101] = r_b;
map[251] = EMPTY;

map[260] = r_c; // 260 adjusted from 201
map[401] = EMPTY;

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

Вот и все для инициализации.

Теперь, чтобы определить, где заданное значение i отображается на все, что вам нужно сделать, это

Map::iterator it = map.upper_bound(i);

Если it == map.begin(), то i не находится ни в каком диапазоне. В противном случае, сделайте

--it;

Если it->second (для уменьшенного it) равно EMPTY, то i не находится ни в каком диапазоне.

Комбинированная проверка "пропустить" может выглядеть следующим образом

Map::iterator it = map.upper_bound(i);
if (it == map.begin() || (--it)->second == EMPTY)
  /* Missed all ranges */;

В противном случае it->second (для уменьшенного it) является вашим отображенным значением

int mapped_to = it->second;

Обратите внимание, что если исходные диапазоны были "касающимися", как в [40, 60] и [61, 100], то диапазоны закрытого открытия будут выглядеть как [40, 61) и [61, 101), означая, что значение 61 будет отображается дважды во время инициализации карты. В этом случае важно убедиться, что значение 61 сопоставлено с правильным целевым значением, а не со значением EMPTY. Если вы отобразите диапазоны, как показано выше, в порядке слева направо (т. Е. В порядке возрастания), он будет работать правильно сам по себе.

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

---

При желании вы можете добавить элемент «сторож» на карту во время инициализации

map[INT_MIN] = EMPTY;

(это соответствует "отрицательной бесконечности"), и проверка "пропустить" станет проще

Map::iterator it = map.upper_bound(i);

assert(it != map.begin());
if ((--it)->second == EMPTY)
  /* Missed all ranges */;

но это просто вопрос личных предпочтений.

Конечно, если вы просто хотите вернуть 0 для не отображенных значений, вам вообще не нужно выполнять какую-либо проверку. Просто возьмите it->second из уменьшенного итератора и все готово.

Answer 2

Я бы использовал очень простую вещь: std::map.

class Range
{
public:
  explicit Range(int item);  // [item,item]
  Range(int low, int high);  // [low,high]

  bool operator<(const Range& rhs) const
  {
    if (mLow < rhs.mLow)
    {
      assert(mHigh < rhs.mLow); // sanity check
      return true;
    }
    return false;
  } // operator<

  int low() const { return mLow; }
  int high() const { return mHigh; }

private:
  int mLow;
  int mHigh;
}; // class Range

Тогда давайте карту:

typedef std::map<Range, int> ranges_type;

И напишите функцию, которая ищет на этой карте:

int find(int item, const ranges_type& ranges)
{
  ranges_type::const_iterator it = ranges.lower_bound(Range(item));
  if (it != ranges.end() && it->first.low() <= item)
    return it->second;
  else
    return 0; // No mapping ?
}

Основные преимущества:

• Проверяет, что диапазоны эффективно не перекрываются во время вставки в набор (вы можете сделать так, чтобы он был только в режиме отладки)
• Поддержка редакции Ranges на лету
• Быстрый поиск (бинарный поиск)

Если диапазоны заморожены (даже если их значения нет), вы можете использовать Loki::AssocVector, чтобы уменьшить накладные расходы памяти и немного повысить производительность (в основном, это отсортированный вектор с интерфейсом карты).

Answer 3

Разве простого массива не будет достаточно? Вы не говорите, сколько у вас элементов, но самая быстрая структура данных - это простой массив.

Если диапазоны:

• 0..9 -> 25
• 10..19 -> 42

Тогда массив будет выглядеть так:

[25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42]

Answer 4

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

Answer 5

Вы можете иметь два отсортированных массива: один для нижних границ, один для верхних границ. Используйте std::lower_bound(lower_bound_array, value) и std::upper_bound(upper_bound_array, value). Если индекс обоих результатов одинаков, return index + 1. В противном случае return 0.

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

Answer 6

Может оказаться полезной функция минимального идеального хеширования, http://cmph.sourceforge.net/.

Answer 7

Это одномерный пространственный индекс. Например, бинарное дерево в стиле дерева квадратов подойдет - и есть несколько других широко используемых методов.

Answer 8

Запишите пределы в set (или map). Когда вы звоните insert, вы получите возвращаемое значение, которое является парой. Итератор и логическое значение. Если логическое значение true, то создается новый элемент, который вы должны удалить позже. После этого первого шага с итератором и посмотрите, что вы нашли.

http://www.cplusplus.com/reference/stl/set/insert/ См. Возвращаемое значение

Answer 9

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

Answer 10

Простой связанный список, содержащий записи диапазона, должен быть достаточно быстрым, даже для, скажем, 50-100 диапазонов. Более того, вы можете реализовать Skip List , скажем, в верхних границах, чтобы ускорить эти запросы диапазона. Еще одна возможность - Дерево интервалов .

В конечном итоге я выбрал бы самое простое: бинарный поиск.