Мб лучше в алгоритмы, но хз... Исходные данные: есть набор чисел

Question

Мб лучше в алгоритмы, но хз... Исходные данные: есть набор чисел

в диапазоне [0, 65535] - uint16_t
На вход поступает набор поддиапазонов: например, {42, 80, [10000-10020]} - назовем их "допустимыми значениями"
Чаще всего отдельных допустимых значений немного - в пределах десятка, либо они описывают интервал
Т.е. ситуация {0, 1, 3, 5, ..., 65535} на практике не возникнет.

Задача: для произвольного числа x€[0,65535] ответить, входить ли оно в разрешенные.

Как оптимально хранить и искать в таком случае?

#c #embedded #programming #russian

0

21.05.2023

5 ответов

30 просмотров

Boris Usievich

Оптимально по какому критерию?

0

21.05.2023

Anton Kviatkovskii

Anton Kviatkovskii
Хранишь диапазоны в массиве отсортировано по начал...

Диапазон - это структура вида начало;конец

0

21.05.2023

Anton Kviatkovskii

Anton Kviatkovskii
Хранишь диапазоны в массиве отсортировано по начал...

По факту массив в данном случае это std::set Но я б перф померил, возможно на векторе будет быстрее

0

21.05.2023

Dmitriy [Отпуск] Автор вопроса

Boris Usievich
Оптимально по какому критерию?

Поиск - по скорости, хранение - по месту. Но лучше отсортированного массива структур вида [begin, end] я тоже не придумал. Правда, если много отдельных значений вида {80} aka [80, 80], все равно некоторый оверхед получится

0

21.05.2023

Anton Kviatkovskii · Accepted Answer

Anton Kviatkovskii

Хранишь диапазоны в массиве отсортировано по началу диапазона. на нем делаешь lower bound по ключу, где ключ - это начало диапазона, затем смотришь находится ли твое число внутри диапазона Сложность логарифм

0

21.05.2023

170 похожих чатов

Мб лучше в алгоритмы, но хз... Исходные данные: есть набор чисел

5 ответов

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