Производительность
Теперь можно сравнить несколько вариантов программы. Мы засекали время счета на библейской Книге Псалмов (версия перевода King James Bible), в которой содержится 42 685 слов (5238 уникальных слов, 22 482 префикса). В тексте довольно много повторяющихся фраз ("Blessed is the…"), так что есть списки суффиксов, имеющие более 400 элементов, и несколько сотен цепей с десятками суффиксов, и это хороший набор данных для теста.
Blessed is the man of the net. Turn thee unto me, and raise me up, that I may tell all my fears. They looked unto him, he heard. My praise shall be blessed. Wealth and riches shall be saved. Thou hast dealt well with thy hid treasure: they are cast into a standing water, the flint into a standing water, and dry ground into watersprings.
Приведенная таблица показывает время в секундах, затрачиваемое на j генерацию 10 000 слов; тестирование проводилось на машине 250 MHz MIPS R10000 с операционной системой Irix 6.4 и на машине Pentium II 400 MHz со 128 мегабайтами памяти под Windows NT. Время выполнения почти целиком определяется объемом вводимого текста; генерация происходит несравненно быстрее.
В таблице приведен также примерный размер программы в строках исходного кода.
| 250 MHz RlOOOO(c) | 400 MHz Pentium II (c) | Строки исходного кода | |
|---|---|---|---|
| С | 0.36 | 0.30 | 150 |
| Java | 4.9 | 9.2 | 105 |
| C++/STL/deque | 2.6 | 11.2 | 70 |
| C++/STL/list | 1.7 | 1.5 | 70 |
| Awk | 2.2 | 2.1 | 20 |
| Perl | 1.8 | 1.0 | 18 |
Версии С и C++ компилировались с включенной оптимизацией, а программы Java запускались с включенным JIT-компилятором (Just-In-Time, "своевременная" компиляция). Время, указанное для версий С и C++ под Irix, – лучшее время из трех возможных компиляторов; сходные результаты были получены и для машин Sun SPARC и DEC Alpha.
Как видно из таблицы, версия на языке С лидирует с большим отрывом, следом за ней идет реализация на Perl. He надо забывать, однако, что результаты, указанные в таблице, относятся к нашим экспериментам с определенным набором компиляторов и библиотек, поэтому в своей среде вы можете получить несколько другие характеристики.
Что-то явно не так с версией STL/deque под Windows. Эксперименты показали, что дек, представляющий префиксы, поедает практически все время выполнения, хотя в нем никогда не содержится более двух элементов; казалось бы, большая часть времени должна уходить на основную структуру – отображение. Переход с дека на список (в STL это двухсвязный список) кардинальным образом улучшает время. Переход же с отображения (map) на (нестандартный) контейнер hash под Irix не приносит никаких изменений (на машине с Windows у нас не было реализации hash).
В пользу замечательного принципа проектирования библиотеки STL говорит тот факт, что для внесения этих изменений нам было достаточно заменить слово list на слово deque, а слово hash на слово тар в двух местах и скомпилировать программу заново. Мы пришли к выводу, что STL, которая является новым компонентом C++, все еще страдает некоторыми недоделками в реализации части своих элементов. Производительность при выборе различных версий STL или изменении используемых структур данных меняется непредсказуемым образом. То же самое можно отнести и к Java, где реализации также быстро меняются.
В тестировании программы, которая выдает в качестве результата что-то объемное, да к тому же выбранное случайным образом, есть доля творческого вызова. Как узнать, правильно ли программа работает? Всегда ли она работает правильно? В главе 6, посвященной тестированию, м: дадим ряд советов на этот счет и расскажем, как мы тестировали наш; программу.