Каким образом ваш компилятор ищет имя переменной в таблице символов? Каким образом справочная система быстро просматривает содержимое компакт-диска по мере ввода символов строки запроса? Как поисковые машины ищут фразы в сети? В этих важных задачах используются методы, рассмотренные нами на примерах этой главы.
Структуры данных для хранения строк
Мы изучили несколько наиболее важных структур, используемых для представления строк в памяти.
Хэширование
Хэш-структура является весьма быстрой и ее легко реализовать.
Сбалансированные деревья
Эти структуры гарантируют хорошую производительность даже в худшем случае. Они включены в большинство реализаций стандартной библиотеки шаблонов C++ STL (структуры set, map).
Массивы остатков
Создайте массив указателей, проинициализируйте его так, чтобы каждый элемент указывал на свой символ строки, затем отсортируйте его и получится массив остатков. Этот массив позволяет находить схожие строки или искать слова и фразы с помощью двоичного поиска.
В разделе 13.8 главы 13 показан пример использования некоторых других структур для представления слов в словаре.
Библиотеки или «самодельные» компоненты?
Наборы, таблицы и строки библиотеки C++ STL весьма удобны в использовании, но их общий и мощный интерфейс приводит к тому, что специализированная функция хэширования работает быстрее. Другие компоненты библиотеки очень эффективны: наша функция хэширования вызывала strcmp, а для реализации массива остатков мы воспользовались qsort. Чтобы написать функции двоичного поиска и сравнения слов в программе порождения марковского текста, я подсмотрел, как реализованы библиотечные функции bsearch и strcmp.
Опубликовал vovan666
April 17 2013 00:04:58 ·
0 Комментариев ·
3427 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
