Стиль словаря искать миллионы ключей, соответствующих небольшому набору значений?
У меня есть ряд показателей.
Существует определенная группа, которая соответствует диапазону показателей
Например:
Range Group
0-100 A
101-220 B
221-543 C
... ...
3K-40K DF
Мне нужен способ поиска соответствующей группы, учитывая определенный индекс.
Например, мне нужен метод:
(Group)groupForIndex:(index)
Так что если бы я позвонил groupForIndex:(115) результат будет B
Я ищу способ улучшить то, что у меня есть сейчас.
Я не буду использовать только NSDictionary (или карта), поскольку это будет запись для каждого идентификатора, которая может составлять миллионы, и пустая трата пространства, поскольку многие ключи будут иметь одинаковое значение.
Я решил использовать комбинацию массива и словаря.
Для каждого «верхнего предела» в массиве будет запись
Пример:
[0] = 100
[1] = 220
[2] = 543
И для каждого верхнего предела в словаре будет запись
Key Value
100 A
220 B
543 C
Таким образом, используя бинарный поиск, по индексу я могу найти верхний предел. Как только у меня есть верхний предел, у меня есть ключ для словаря.
Это самая эффективная схема поиска, которую я мог придумать. Что может быть более эффективным способом сделать это?
Решение
Бинарный поиск в (отсортированном) массиве очень быстр, поэтому ваш метод выглядит хорошо для меня, если группы и индексы фиксированы, так что массив должен быть построен только один раз (или нечасто, по сравнению с количеством поисков).
Если набор групп часто меняется затем другая структура данных (например, некоторые
дерево) может быть лучше, чем перестраивать массив при каждом изменении.
Как я сказал в комментарии, я бы заменил словарь другим массивом
(того же размера, что и первый)
[0] = "A"[1] = "B"[2] = "C"...
а затем просто сопоставить индекс, найденный в первом массиве с соответствующей группой
через второй массив.
Это может быть незначительно быстрее и легче поддерживать, потому что «верхние пределы» для каждой группы не хранятся в двух местах.
Другие решения
Других решений пока нет …