Как найти диапазон из множества смежных диапазонов для заданного числа

Проще говоря, это то, что я пытаюсь сделать:

У меня есть коллекция объектов Range, которые являются смежными (не перекрываются, без пропусков между ними), каждый из которых содержит start и end int и ссылка на другое объект obj. Эти диапазоны не имеют фиксированного размера (первый может быть 1-49, второй 50-221 и т. Д.). Эта коллекция может стать довольно большой.

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

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

Спасибо.

7 голосов | спросил IgnisFatuus 29 J000000Tuesday14 2014, 00:40:52

3 ответа


0

Если звучит так, как будто вы хотите использовать ---- +: = 0 =: + ---- , где ключ - это нижняя часть диапазона, а значение - TreeMap объект.

Затем, чтобы определить правильный диапазон, просто используйте метод Range, чтобы очень быстро получить ближайший (меньший или равный) floorEntry(), который должен содержать ключ, например:

Range

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

Вы захотите добавить некоторую проверку работоспособности, когда ваш ключ полностью выходит за пределы (например, когда они находятся за пределами карты, он возвращает последний TreeMap<Integer, Range> map = new TreeMap<>(); map.put(1, new Range(1, 10)); map.put(11, new Range(11, 30)); map.put(31, new Range(31, 100)); // int key = 0; // null // int key = 1; // Range [start=1, end=10] // int key = 11; // Range [start=11, end=30] // int key = 21; // Range [start=11, end=30] // int key = 31; // Range [start=31, end=100] // int key = 41; // Range [start=31, end=100] int key = 101; // Range [start=31, end=100] // etc. Range r = null; Map.Entry<Integer, Range> m = map.floorEntry(key); if (m != null) { r = m.getValue(); } System.out.println(r); на карте), но это должно дать вам представление о том, как действовать.

ответил azurefrog 29 J000000Tuesday14 2014, 01:12:23
0

Предполагая, что поиск имеет первостепенное значение, и вы можете сэкономить O (N) памяти и приблизительно O (N ^ 2) время предварительной обработки, алгоритм будет выглядеть так:

  • ввести класс ObjectsInRange, который содержит: начало диапазона (int startOfRange) и набор объектов (Set<Object> objects)
  • введите ArrayList<ObjectsInRange> oir, который будет содержать ObjectsInRange отсортировано по startOfRange
  • для каждого Range r, убедитесь, что существует ObjectsInRange (назовем их a и b) такой, что a.startOfRange = r.start и b.startOfRange = b.end. Тогда для всех ObjectsInRange x между a, и до (но не включая) b не добавляйте r.obj в их x.objects set

Таким образом, поиск выглядит следующим образом:

  • для целого числа x, найдите такой i что oir[i].startOfRange <= x и oir[i+1].startOfRange > x
  • примечание: i можно найти с разделением пополам за O (log N)!
  • ваши объекты oir[i].objects
ответил kzagar 29 J000000Tuesday14 2014, 01:01:15
0

Если коллекция в порядке, то вы можете реализовать двоичный поиск, чтобы найти правильный диапазон за O (log (n)) времени. Это не так эффективно, как хеширование для очень больших коллекций, но если у вас менее 1000 диапазонов, это может быть быстрее (потому что это проще).

ответил Ypnypn 29 J000000Tuesday14 2014, 01:04:52

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132