Фильтры диапазона данных в C ++

Question

Я хочу позволить пользователю иметь возможность определять диапазоны, которые будут фильтровать данные.Определенные диапазоны могут быть смежными, перекрывающимися или разделенными (например, пользователь вводит следующие диапазоны: 1-10, 5-10, 10-12, 7-13 и 15-20).

Iзатем хотите отфильтровать данные так, чтобы пользователь отображал только то, что находится в этих диапазонах.

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

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

Существует ли структура данных (или некоторый алгоритм), которая могла быбыть использованы для достижения этой цели?

Answer 1

Вы можете использовать для этого filter_iterator .

Answer 2

Это не так сложно, если ваши данные уже отсортированы.Используйте комбинацию

• нижняя граница
• верхняя граница

Для каждого из ваших поддиапазонов [min, max] вы можете найти итераторы i_min и i_max и использовать их как

std::make_pair(i_min, i_max)

, чтобы сделать его совместимым с «диапазоном».Затем используйте boost :: join, чтобы объединить все поддиапазоны в один диапазон (конечно, лениво), а затем использовать этот диапазон при обработке в нисходящем потоке.

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

Answer 3

Я думаю, то, что вы хотите сделать, известно как Минимальный диапазон запросов .

Answer 4

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

Конструкция на основе классов позволит вам перегрузить operator += для синтаксического сахара, но голое растровое изображение будет работать так же хорошо.Например:

# original bitmap
bits = [ 0,0,0,0,0,0,0,0,0,0 ]

# add 1-5
bits = [ 0,1,1,1,1,1,0,0,0,0 ]

# add 4 - 6
bits = [ 0,1,1,1,1,1,1,0,0,0 ]

# Look for 3
bits[3] == 1 ?

Answer 5

Решение в целом зависит от границ диапазона.

1. Если max - min не так велико (например, вы определяете границы в [1..1024]), вы можетеиспользуйте только массив, который указывает каждый X на список диапазонов.Для вашего примера, массив должен быть:

ranges=[0:(1,10), 1:(5,10), 2:(10,12), 3:(7,13), 4:(15-20)]
points=[1:[0],2:[0],3:[0],4:[0],5:[0,1],...,7:[0,1,3],...10:[0,1,2,3],...15:[4],...20:[4],21:[]...]

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

Вы можете использовать Дерево интервалов - менее эффективно, но более эффективно для памяти (конечно, более эффективно, чем решение методом перебора)

Answer 6

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

НТН.

Answer 7

Вы можете использовать итераторы в ваших контейнерах. Например, std :: vector предоставляет метод at. Эти итераторы могут быть смежными, перекрывающимися или разделенными.

Answer 8

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