algorithm - generación única de clave de hash entera/larga sobre cadenas para una comparación más rápida

string comparison

Question

Tengo curiosidad de cómo otros han resuelto este problema, y ​​qué problemas podrían esconderse detrás de la solución ingenua:

Tengo un sistema que procesa datos bursátiles. Hay decenas de miles de símbolos, con precios / tamaños asociados, que fluyen en el sistema a razón de varios miles cada milisegundo.

Una de las operaciones básicas que debe realizarse en cada tic es la comparación de cadenas para ver si la entrada coincide con el símbolo que nos interesa. Con tanta frecuencia, la optimización de estas comparaciones de cadenas puede hacer una diferencia medible en el rendimiento de todo el sistema .

Estoy pensando en generar un hash de la cadena del símbolo y almacenarlo con el registro. Para una comparación posterior, el sistema debe usar este hash (siendo un int o un long, la comparación debe ser una operación única, en lugar de iterar a través de cada carácter de la cadena hasta que se encuentre una discrepancia).

Vamos a ignorar el costo de generar el hash en sí (que, en realidad, en realidad puede ser prohibitivo). El único problema que puedo ver es que con una gran cantidad de símbolos únicos, una colisión hash (dos símbolos separados generan el mismo hash) sería devastador. ¿Hay un algoritmo hash que garantice que las cadenas que coinciden con ciertas restricciones (como el límite en el número de caracteres) sean únicas?

EDITAR: escribiré este código en Java. No estoy seguro de la calidad (de colisión) de hashCode o la velocidad con la que se calcula.

Answer 1

Apoyo la sugerencia anterior de una estructura Trie como el mejor enfoque para este caso. Computacionalmente equivalente a un hash perfecto, pero conceptualmente mucho más bonito. Esto supone que tus símbolos tienen un límite de longitud.

Answer 2

Cualquier función hash decente maneja bien las colisiones. Básicamente, si el hash resulta en un acierto para el que existen múltiples respuestas, hay una lista vinculada de posibles soluciones en ese segmento, y por necesidad, las cosas se ralentizan para encontrar la respuesta correcta (si existe).

Pero no escriba su propia función hash, use una que esté disponible.

Oh, y generar el hash debería hacerse solo una vez, creo. Porque tiene una tabla de búsqueda de las cosas que está rastreando, y la tabla hash solo debe cambiar cuando agrega una nueva cosa "interesante" para buscar.

Answer 3

Debería considerar usar una función hash perfecta , creo que se ajusta a sus requisitos

Answer 4

Editar: mejores comentarios que los míos fueron lanzados (y antes), haciendo que el mío sea redundante en el mejor de los casos.

Answer 5

FWIW, en el último proyecto de gran volumen de datos en el que estuve, encontramos que el filtrado, la agregación y la preclasificación de datos utilizando algún código C muy ajustado era la clave. Todos nuestros feeds entraron en este preprocesador y se encargó de la limpieza de datos simple antes de pasar la mayor parte de los datos a nuestro sistema basado en Java para su procesamiento. Básicamente, el pre-procesador hizo exactamente lo mismo que usted: identificar registros de interés, verificar que estaban completos y eliminar dups y vacíos. Durante las horas pico, el preprocesador podría eliminar hasta el 20% de los 8 millones de registros que obtendríamos por hora (probablemente no sea el volumen que imagino que obtendrá de las existencias del mercado de valores). Nuestra versión original de Java tuvo la suerte de obtener la mitad (¡pero al menos era "elegante")!

Answer 6

Funciones de hash criptográficas comunes como SHA-1 salidas de 20 bytes (160 bit). ¿Cuánto duran sus símbolos de acciones? Si hablamos de símbolos de cotización como "WMT" (Walmart), "KO" (Coca-Cola), etc., entonces parecen tener solo un par de bytes, por lo que debería ser más rápido compararlos directamente en su lugar. de lidiar con un hash de 20 bytes. Usted menciona colisiones hash: no me preocuparía por ellas, especialmente cuando las entradas son mucho más pequeñas que la salida hash.

Es posible que pueda convertir los bytes en int o long dependiendo del lenguaje de programación y la plataforma y luego hacer la comparación entre estos "números" en una instrucción de CPU. (No sé si los compiladores modernos pueden comparar un grupo de bytes igualmente rápido con una llamada a memcmp ?)

Answer 7

Lo que quiere es una función hash rápida que tenga un buen poder de discriminación. Para cada cadena, calcule la función hash asociada y guárdela con la cadena. Luego, para una comparación, codifique: if (Hash (s1) == Hash (s2) && s1 == s2) then {...} La comparación actual de cadenas no ocurrirá a menos que los hashes coincidan, lo que en la práctica es solo cuando las cuerdas coinciden.

Algunas personas te dirán que implementes un hash perfecto. Solo puede hacer eso cuando el conjunto de cadenas que quiere hash tiene un tamaño limitado, generalmente solo 10-1000. No puede hacer eso para un vocabulario arbitrariamente grande de cadenas. Como no puedes hacer eso, en realidad tienes que comparar las cuerdas para determinar la igualdad.

Los valores hash criptográficos tienen un gran poder de discriminación, pero no están diseñados para ser rápidos. Lo que generalmente es muy rápido y tiene un buen poder de discriminación son las funciones CRC, y la mayoría de los lenguajes han encontrado fácilmente bibliotecas que los computan rápidamente (usando una técnica de búsqueda de tabla en bytes). Usamos CRC-32 y es muy efectivo para esto (básicamente 1 probabilidad en 2 ^ 32 de que se produzca una colisión hash, cuando las cuerdas no coinciden). Puede usar CRC-64, pero la potencia de discriminación adicional que proporciona realmente no agregará ninguna funcionalidad real.

Answer 8

Por lo que vale. Resolví este problema específico a la simbología CMS (NYSE) y CQS (NASDAQ). Las raíces del símbolo tendrán como máximo 6 caracteres y estarán en mayúsculas. Mis requisitos fueron los siguientes:

• Los datos llegarían por un símbolo desconocido
• Al recibir los datos, calcule un valor hash que se utilizará para comparar
• Calcule el valor una vez, almacene el valor en un mapa para compararlo en el futuro
• Las comparaciones de valores serán igualdad
• Las comparaciones de valores estarán en contra de un rango.

Por ejemplo, si llegan datos para GOOG, será necesario procesarlos y distribuirlos a los procesos en el rango de símbolos [F-HAA]. (F <= GOOG <= HAA). Usé una clase de rango que tiene un valor bajo (F) y un valor alto (HAA). El concepto de función Mi Hash es similar a empaquetar los caracteres en bytes, pero para fines de registro, red y endian elegí unsigned long long como mi tipo de almacenamiento. Antes de llamar a esta función, los símbolos se rellenan con un carácter ''@''. (IBM @@@)

unsigned long long SymbolToVal(std::string& str)
{
 size_t maxlen = 6; // Symbology constraint
 if (str.length() != maxlen) return 0;
 unsigned long long val;
 unsigned long long retval=0;
 int expon = maxlen*2; // ASCII val range (65-90)
 double factor = std::pow(10.0,expon);
 expon-=2;
 for (size_t i = 0; i < maxlen; i++)
 {
    val = (unsigned long long)factor * str[i];
    retval += val;
    factor = (unsigned long long) std::pow(10.0,expon);
    expon-=2;
  }
  return retval;
 }

Un método de fuerza bruta consistiría en calcular todos los símbolos posibles, clasificarlos adecuadamente y asignarles un número entero, y luego almacenarlos en un mapa. Puede ser excesivo si los datos entrantes solo constan de una pequeña porción del dominio total (que es el caso normal).

Answer 9

Puede generar el hash tratando la cadena como un número Base-27 (suponiendo que los símbolos solo contengan letras). Esto generaría la singularidad que estás buscando. Por ejemplo:

(sin letra) = 0, A = 1, B = 2, ... Z = 26

AA = (1 x 27 ¹ ) + (1 x 27 ⁰ ) = 28

AAA = (1 x 27 ² ) + (1 x 27 ¹ ) + (1 x 27 ⁰ ) = 757

BBB = (2 x 27 ² ) + (2 x 27 ¹ ) + (2 x 27 ⁰ ) = 1514

GOOG = (7 x 27 ³ ) + (15 x 27 ² ) + (15 x 27 ¹ ) + (7 x 27 ⁰ ) = 149128

Esto funcionará bien hasta 6 caracteres en un int 32 bits.

Answer 10

Si está recibiendo símbolos de 4 letras, entonces cada letra debe ser representable como un solo byte. Pack los 4 juntos en un int de 32 bits, y listo, tienes tu "hash". Ahora puede comparar esto con la referencia usando una sola instrucción de máquina.

Si no estabas usando Java, eso es.

Realmente no recomendaría usar Java para nada de velocidad crítica, especialmente no miles de comparaciones de cadenas por milisegundo.

editar: si desea utilizar el código de 64 bits, puede empacar hasta 8 letras por int largo y luego comparar en 1 instrucción.

Answer 11

Si usa String.intern () o su propio agrupamiento de cadenas, puede utilizar == en lugar de .equals (): lo he hecho en un código crítico de rendimiento similar y ha marcado una gran diferencia. La cadena por defecto ya tiene un hashCode () que funciona con bastante eficacia.

Me acabo de dar cuenta de que no era una pregunta de Java, pero lo mismo se aplica. Sí, hashing y luego usar la verificación de identidad puede ahorrar tiempo. El algoritmo de hash de Java usa:

s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1]

Answer 12

Quizás las funciones hash no son el mejor enfoque aquí. Si está recibiendo un símbolo (y no el hash del símbolo), tendrá que calcular el hash cada vez que lo haga. Si se trata de un algoritmo hash sin colisiones, tendrá que mirar todos los caracteres del símbolo de todos modos. Entonces, podrías comparar directamente los personajes.

Sugiero construir una estructura de datos Trie de todos los tickers que le interesen (ver http://en.wikipedia.org/wiki/Trie ). Recorre el árbol para cada símbolo y si llegas al final del ticker sin encontrar una coincidencia, entonces no es un ticker interesante.

Con hashing, tendrás que hacer este recorrido de todos modos en el conjunto de todos los valores hash de los tickers interesantes.