Более быстрая реализация CompareText для D2009

Question

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

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

сайт Fastcode

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

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

Answer 1

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

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

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

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

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