1

У меня есть большой набор простых числовых значений (1,3,23,32,2,4,10 ...). Всего в наборе около тысячи значений. Мне нужно организовать быструю проверку на наличие ключа в наборе. Каждый раз перебирать в массиве тысячу значений не выглядит хорошим решением. Сейчас использую Dictionary и в value устанавливаю 0. Возможно есть более хорошее решение? Что-нибудь наподобие hashset в c#.

1 ответ 1

2

массив сортируете (если данные статические - то лучше сразу хранить отсортированный массив) и применяете бинарный поиск. Код на делфи - http://www.delphisources.ru/pages/faq/base/binary_int_array_search.html

Сложность поиска - логарифмическая.

В некоторых случаях можно применить радикс поиск. То есть, массив делим на группы (1-9, 10-99, 100-999 или по первой цифре). Каждую с вложенных групп делим также или просто применяем бинарный поиск.

Если скорости бинарного поиска будет недостаточно (ну мало чего), а памяти достаточно, то просто заводим массив булевых значений размером по максимальному элементу. Потом пробегаем по массиву и исходных элементов, и используя их как индексы проставляем true в новосозданном массиве. Теперь поиск будет константный.

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.