Существует мнение, что программу двоичного поиска тяжело написать без ошибок
Существует мнение, что программу двоичного поиска тяжело написать без ошибок. Подробно мы изучим ее в главе 4.
Программа последовательного поиска выполняет в среднем около п/2 сравнений при поиске в наборе из п элементов, тогда как двоичный поиск всегда делает не более log2 п. Этот факт может очень сильно повлиять на производительность системы. Вот пример, относящийся к системе бронирования билетов авиакомпании TWA:
«Одна из программ осуществляла последовательный поиск в огромном объеме памяти примерно 100 раз в секунду. По мере роста сети среднее время обработки сообщения возросло до 0,3 мс, что оказалось для нас слишком много. Мы установили,
что проблема заключается в использовании процедуры последовательного поиска, заменили ее процедурой двоичного поиска, и проблема исчезла».
Я часто сталкивался с этим и в других системах. Программисты начинают с простой структуры данных и последовательного поиска, который поначалу оказывается достаточно быстрым. Когда производительности подобной программы начинает не хватать, можно отсортировать таблицу и воспользоваться двоичным поиском, что устраняет проблему.
Однако поле применения двоичного поиска не ограничивается быстрым поиском в отсортированных массивах. Рой Вейл (Roy Weil) применил этот метод для нахождения некорректной строки во входном файле, содержащем более 1000 строк. К сожалению, строку эту нельзя было обнаружить по ее внешнему виду; узнать о ее наличии можно было, лишь обработав файл (начальную часть до произвольного места) некой программой и получив некорректный ответ, па что требовалось несколько минут. Его предшественники, пытавшиеся найти ошибку, пробовали обрабатывать несколько строк за один проход, благодаря чему продвигались к цели со скоростью улитки. Попробуйте догадаться, как удалось Вейлу найти ошибку за десять попыток?
Опубликовал vovan666
April 16 2013 23:34:30 ·
0 Комментариев ·
3761 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
