@Otakukz17

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

Есть txt список, состоящий из 4 миллионов значений.
Требуется определить, есть ли заданное значение в этом списке.
Как понять сколько времени будет занимать поиск заданного значения и каким способом эффективнее парсить файл?
  • Вопрос задан
  • 85 просмотров
Пригласить эксперта
Ответы на вопрос 3
@deliro
Как понять сколько времени будет занимать поиск заданного значения и каким способом эффективнее парсить файл?

Что известно о файле кроме того, что он есть?

Если значения в случайном порядке, то сложность будет всегда O(N) в худшем случае

Если в нём значения отсортированы по какому-то признаку и есть явный разделитель (перевод каретки, например), то можно сделать аналог бинарного поиска (за O(logN)). Ну то есть, тыкаем в середину файла (seek(file_size_in_bytes / 2)), ищем вперёд ближайший разделитель (например, перевод каретки), читаем до следующего разделителя (получается строка), сравниваем ну и дальше как обычно. Но нужно учесть, что если это HDD, то движения головки диска не бесплатные и рандомный seek будет медленней последовательного, так что сравнивать "количество строк в секунду" в лоб не выйдет.

Если ОЗУ позволяет, то можно вычитать весь файл туда и закинуть в структуру, которая больше подходит. Будь то дерево, сортированный массив или хэш-таблица. Если требуется только ответ на вопрос "есть?", то хэш-таблица будет самым производительным вариантом со сложностью O(1)

Если ОЗУ не позволяет и большинство запросов заведомо будут "мимо", можно сделать фильтр Блума и сканировать файл только если он "возможно есть" и никогда не сканировать, если его "точно нет" (собственно, эти ответы и даёт фильтр Блума)

Если ОЗУ не позволяет, но файл можно менять, то можно отсортировать его единоразово и дальше бинарный поиск

Да можно даже содержимое файла в sqlite залить и решить все проблемы, пусть драйвер сам разбирается, что хранить в ОЗУ
Ответ написан
Комментировать
Jacen11
@Jacen11
Ответ написан
Комментировать
@Dmtm
Android
это задача поиска подстроки и для нее есть быстрые специализированные алгоритмы
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы