2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8);
function CountBits2(B : byte): byte;
begin
Result := BitCounts[B];
end;
Здесь за счет статического 256-байтного массива значений функция намного упростилась. Более того, приведенный алгоритм не содержит цикла. Независимо от значения входного параметра, количество установленных битов вычисляется за один простой шаг. (Обратите внимание, что значения для статического массива были вычислены автоматически с помощью простой программы, использующей первую функцию.)
На компьютере автора книги последний алгоритм оказался в 10 раз быстрее, чем первый: 10 вызовов второй функции занимает столько же времени, сколько один вызов первой. (Обратите внимание, что здесь речь идет о среднем случае. В лучшем случае для первой функции значение параметра равно 0 и функция практически не будет требовать времени на выполнение.)
Таким образом, за счет введения 256-байтного массива мы разработали алгоритм, который быстрее в 10 раз. Увеличение скорости было достигнуто за счет увеличения требуемого объема памяти: можно получить быструю функцию, использующую большой статический массив (который будет скомпилирован в выполняемый файл, об этом также следует помнить), или более медленную функцию, не требующую больших объемов памяти. (Существует еще одна альтернатива. Можно заполнять массив значениями в процессе выполнения функции, при ее первом вызове. В этом случае массив не будет компилироваться в выполняемый файл, но первый вызов функции займет достаточно длительное время.)
Этот простой пример служит демонстрацией выбора компромиссного варианта между требуемым объемом памяти и быстродействием. Часто для увеличения скорости работы приходится вычислять все возможные результаты заранее, однако это требует дополнительной памяти.
Длинные строки
Дискуссию о быстродействии алгоритмов нельзя считать законченной без краткого рассмотрения длинных строк. С ними связан целый ряд проблем, касающихся эффективности. Длинные строки появились в Delphi 2 и присутствовали во всех последующих компиляторах Delphi и Kylix (программисты, работающие в Delphi1, могут не беспокоиться о длинных строках и без последствий пропустить этот раздел).
Длинная строковая переменная string - это всего лишь указатель на специальным образом отформатированный блок памяти. Другими словами, sizeof(stringvar) - sizeof(pointer). Если указатель содержит nil, строка считается пустой. В противном случае указатель указывает непосредственно на последовательность символов, составляющих строку. Функции для работы с длинными строками в библиотеке времени выполнения гарантируют, что строка всегда завершается нулем (null-символом). Благодаря этому, строковую переменную всегда можно легко привести к типу PChar, используемому при вызове API-функций системы. Но, наверное, не все знают, что блок памяти, на который указывает указатель, содержит и некоторую дополнительную информацию. Четыре байта, расположенные до последовательности символов, представляют собой целочисленное значение - длину строки (за исключением завершающего нуля). Предшествующие четыре байта содержат целочисленное значение, представляющее собой счетчик ссылок (для постоянных строк это значение равно -1). Если память для строки выделена из кучи, то предшествующие четыре байта содержат целочисленное значение, представляющее собой полный объем используемого строкой блока памяти, включая все скрытые целочисленные поля, последовательность символов, составляющих строку, и скрытый завершающий null- символ, округленные до ближайших четырех байтов.
Счетчик ссылок присутствует в блоке памяти, поэтому операция
MyOtherString := MyString выполняется очень быстро. Компилятор преобразует это присвоение за два шага: сначала он увеличивает на 1 счетчик ссылок для строки, на которую указывает MyString, а затем устанавливает указатель MyOtherString равным указателю MyString.
Вот и все, что можно сказать об увеличении быстродействия приложения при использовании длинных строк. Все остальные операции со строками будут требовать выделения памяти.
Использование ключевого слова const
Если функции передать строку, которая в процессе выполнения функции не будет изменяться, объявляйте ее как const. В большинстве случаев это исключает скрытое добавление блока try..finally. Если не использовать ключевое слово const, компилятор будет считать, что значение, возможно, будет изменяться, и поэтому вводит скрытую локальную переменную для хранения строки. В начале выполнения функции счетчик ссылок будет увеличен на 1, а в конце - уменьшен на 1. Чтобы гарантировать, что значение счетчика всегда будет уменьшаться, компилятор вставляет скрытый блок try..finally.
В листинге 1.5 приведена функция определения количества гласных в строке.
Листинг 1.5. Подсчет количества гласных в строке
function CountVowels(const S : string): integer;
var
i : integer;
begin
Result := 0;
for i := 1 to length (S) do
if upcase(S[i]) in ['A', 'E', 'I', 'O', 'U'] then
inc(Result);
end;
Если из строки объявления функции убрать ключевое слово const, ее быстродействие снизится приблизительно на 12% - это и есть влияние скрытого блока try..finally.
Осторожность в отношении автоматического преобразования типов
Часто мы используем совместно символы и строки, не обращая на это никакого внимания. Преобразованием типов занимается компилятор, и программист зачастую не подозревает, что происходит на самом деле. Возьмем, например, функцию Pos. Как вы знаете, эта функция возвращает положение подстроки в строке. Если использовать ее для поиска символа:
PosOfCh := Pos(SomeChar, MyString);
нужно помнить, что компилятор автоматически преобразует символ в длинную строку. Он выделит память для строки из кучи, установит длину равной 1 и скопирует в строку символ. Затем вызывается
