Более быстрая реализация CompareText для D2009 - PullRequest
3 голосов
/ 04 марта 2009

Я широко использую структуры данных хэш-карт в своей программе. Я использую реализацию карты хеша Барри Келли, размещенную на форумах Codegear. Эта реализация внутренне использует функцию RTL CompareText. Профилирование заставило меня понять, что в функции SysUtils CompareText тратится много времени.

Я посмотрел на

Fastcode site

и нашел несколько более быстрых реализаций CompareText. К сожалению, они не работают для D2009 и его строк в кодировке Unicode.

Теперь к вопросу: существует ли аналогичная более быстрая версия, которая поддерживает строки D2009? Функции CompareText, по-видимому, часто вызываются при использовании хеш-карт (по крайней мере, в той реализации, которую я сейчас использую), поэтому небольшие улучшения производительности могут реально изменить ситуацию. Или представленные там реализации также могут работать со строками Unicode?

1 Ответ

4 голосов
/ 04 марта 2009

Многие функции FastCode, вероятно, скомпилируются и, похоже, будут отлично работать в Delphi 2009, но они не будут подходящими для всех вводимых данных. Те, которые реализованы в ассемблере, потерпят неудачу, потому что они предполагают, что символы - только один байт каждый. Те, что реализованы в Delphi, получатся немного лучше, но они все равно будут иногда давать неправильные результаты, потому что старое CompareText понятие «без учета регистра» основано на ASCII, тогда как новое должно основываться на Unicode. Правила, для которых символы считаются одинаковыми, за исключением случая, сильно отличаются для Unicode от того, как они для ASCII.

Андреас говорит в комментарии ниже, что Unicode CompareText все еще использует правила сравнения регистров ASCII, поэтому некоторые функции FastCode должны работать нормально. Просто просмотрите их, прежде чем использовать их, чтобы убедиться, что они не делают никаких предположений о размере символов. Кажется, я вспоминаю, что некоторые функции FastCode уже были включены в Delphi RTL. Я понятия не имею, был ли CompareText одним из них.

Если вы звоните CompareText много в хеш-таблице, то это говорит о том, что ваша хеш-таблица не очень хорошо работает. CompareText должен вызываться только тогда, когда хэш того, что вы ищете, обозначает непустое ведро в хеш-таблице. Оттуда хеш-таблица будет часто использовать линейный поиск, чтобы найти нужный элемент в корзине, и она будет вызывать CompareText для каждого элемента во время этого поиска. Я не знаю, работает ли тот, который вы используете.

Вы можете решить эту проблему, используя другую хеш-функцию, которая более равномерно распределяет результаты по доступным сегментам. Если ваши сегменты уже заполнены равномерно, то вам может понадобиться больше блоков (и затем убедитесь, что хеш-функция все еще равномерно распределяется по этому номеру ).

Если используемый вами класс хэш-карты основан на TBucketList, то в хранилище корзины есть место для улучшения. Этот класс не вычисляет хеш для всего ввода. Он использует входные данные only для определения используемого сегмента. Если класс также будет отслеживать полный хеш, вычисленный для строки, то сравнения во время линейного поиска могут выполняться намного быстрее. Просто сравните хэши и сравнивайте строки только тогда, когда хэши полностью совпадают. (Для 256-сегментного списка сегментов, самый большой поддерживаемый размер, только один байт входных данных определяет сегмент, а остальные байты игнорируются.) Я писал о TBucketList здесь раньше.

...