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

Question

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

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

Fastcode site

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

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

Answer 1

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

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

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

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

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