Implementación más rápida de CompareText para D2009

Question

Estoy utilizando de forma extensiva estructuras de datos de mapa hash en mi programa. Estoy usando una implementación de mapa hash por Barry Kelly publicada en los foros de Codegear. Esa implementación utiliza internamente la función CompareText de RTL. La elaboración de perfiles me hizo darme cuenta de que se dedica MUCHO tiempo en la función Comparar Texto de SysUtils.

He echado un vistazo a la

sitio de Fastcode

y encontré algunas implementaciones más rápidas de CompareText. Lamentablemente, parece que no funcionan para D2009 y sus cadenas Unicode.

Ahora, para la pregunta: ¿hay una versión más rápida similar que admita cadenas D2009? Las funciones CompareText se llaman mucho cuando se usan mapas hash (al menos en la implementación que estoy usando actualmente), por lo que las pequeñas mejoras de rendimiento realmente podrían hacer una diferencia. ¿O deberían las implementaciones presentadas allí funcionar también para cadenas Unicode?

Answer 1

Muchas de las funciones de FastCode probablemente se compilarán y parecerán que funcionan bien en Delphi 2009, pero no serán correctas para todas las entradas. Los implementados en el ensamblador fallarán porque asumen que los caracteres tienen solo un byte cada uno. A los implementados en Delphi les irá un poco mejor, pero seguirán obteniendo resultados incorrectos a veces debido a la antigua noción de " insensible a mayúsculas y minúsculas en CompareText se basa en ASCII, mientras que el nuevo debe basarse en Unicode. Las reglas para las que los caracteres se consideran iguales, excepto para el caso, son mucho diferentes para Unicode de cómo son para ASCII.

Andreas dice en un comentario a continuación que Unicode CompareText todavía usa las reglas de comparación de casos ASCII, por lo que varias funciones de FastCode deberían funcionar bien. Solo eche un vistazo antes de usarlos para asegurarse de que no están haciendo suposiciones del tamaño de un personaje. Me parece recordar que algunas funciones FastCode ya estaban incorporadas en el Delphi RTL. No tengo idea de si CompareText fue uno de ellos.

Si está llamando mucho a CompareText en una tabla hash, eso sugiere que su tabla hash no está haciendo un buen trabajo. CompareText solo debe llamarse cuando el hash de lo que está buscando designó un depósito no vacío en la tabla de hash. A partir de ahí, una tabla hash usualmente usará una búsqueda lineal para encontrar el elemento correcto en el cubo, y llamará a CompareText para cada elemento durante esa búsqueda. No sé si es así como funciona la que estás usando.

Puede resolver esto utilizando una función hash diferente que distribuya sus resultados de manera más equitativa entre los grupos disponibles. Si sus cubos ya están llenos de manera uniforme, es posible que necesite más cubos (y luego asegúrese de que la función de troceo todavía se distribuya uniformemente sobre el número que también).

Si la clase de hash-map que está utilizando se basa en TBucketList , entonces hay espacio para mejoras en el almacenamiento del contenedor. Esa clase no calcula un hash en toda la entrada. Utiliza la entrada solo para determinar el grupo que se usará. Si la clase también realiza un seguimiento del hash completo computado para una cadena, las comparaciones durante la búsqueda lineal podrían ser mucho más rápidas. Simplemente compare los hashes, y solo compare las cadenas cuando los hashes coincidan completamente. (Para una lista de cubetas de 256 compartimientos, el tamaño más grande admitido, solo un byte de la entrada determina el compartimiento, y el resto de los bytes se ignoran). He escrito sobre TBucketList aquí antes.