c# - generate - Opciones de estructura de datos para detección de alta velocidad y eficiencia de la memoria de duplicados de cadenas

sha256 c#

Question

Tengo un problema interesante que se puede resolver de varias maneras:

• Tengo una función que toma una cadena.
• Si esta función nunca ha visto esta cadena antes, necesita realizar algún procesamiento.
• Si la función ha visto la cadena antes, necesita omitir el procesamiento.
• Después de un período de tiempo específico, la función debe aceptar cadenas duplicadas.
• Esta función se puede llamar miles de veces por segundo y los datos de cadena pueden ser muy grandes.

Esta es una explicación muy abstraída de la aplicación real, simplemente tratando de llegar al concepto central para el propósito de la pregunta.

La función necesitará almacenar estado para detectar duplicados. También necesitará almacenar una marca de tiempo asociada para caducar los duplicados.

NO es necesario almacenar las cadenas, un hash exclusivo de la cadena estaría bien, siempre que no haya falsos positivos debido a colisiones (¿Usar un hash perfecto?), Y la función hash fue lo suficientemente eficiente.

La implementación ingenua sería simplemente (en C #):

 Dictionary<String,DateTime>

aunque con el interés de reducir la huella de memoria y aumentar potencialmente el rendimiento, estoy evaluando una estructura de datos personalizada para manejar esto en lugar de una tabla hash básica.

Entonces, dadas estas limitaciones, ¿qué usarías?

EDIT, alguna información adicional que podría cambiar las implementaciones propuestas:

• 99% de las cadenas no serán duplicados.
• Casi todos los duplicados llegarán de regreso, o casi secuencialmente.
• En el mundo real, la función se llamará desde múltiples hilos de trabajo, por lo que la gestión del estado deberá sincronizarse.

Answer 1

un hash único de la cadena estaría bien, siempre que no haya falsos positivos debido a colisiones

Eso no es posible, si quieres que el código hash sea más corto que las cadenas.

El uso de códigos hash implica que hay falsos positivos, solo que son lo suficientemente raros como para no ser un problema de rendimiento.

Incluso consideraría crear el código hash a partir de solo una parte de la cadena, para hacerlo más rápido. Incluso si eso significa que obtiene más falsos positivos, podría aumentar el rendimiento general.

Answer 2

No creo que sea posible construir " hash perfecto " sin conocer primero el conjunto completo de valores (especialmente en el caso de C # int con un número limitado de valores). Por lo tanto, cualquier tipo de hash requiere capacidad para comparar valores originales también.

Creo que el diccionario es lo mejor que se puede obtener con estructuras de datos sin caja. Dado que puede almacenar objetos con comparaciones personalizadas definidas, puede evitar fácilmente guardar cadenas en memeory y simplemente guardar la ubicación donde se puede obtener una cadena completa. Es decir, objeto con los siguientes valores:

stringLocation.fileName="file13.txt";
stringLocation.fromOffset=100;
stringLocation.toOffset=345;
expiration= "2012-09-09T1100";
hashCode = 123456;

Donde cutomom comparer devolverá el hashCode guardado o recuperará la cadena del archivo si es necesario y realizará la comparación.

Answer 3

Si la huella de memoria para almacenar cadenas enteras no es aceptable, solo tiene dos opciones:

1) Almacene solo hashes de cadenas, lo que implica la posibilidad de colisiones hash (cuando el hash es más corto que las cadenas). La buena función hash (MD5, SHA1, etc.) hace que esta colisión sea casi imposible de realizar, por lo que solo depende si es lo suficientemente rápida para su propósito.

2) Use algún tipo de compresión sin pérdida. Las cadenas generalmente tienen una buena relación de compresión (aproximadamente 10%) y algunos algoritmos como ZIP le permiten elegir entre la compresión rápida (y menos eficiente) y la compresión lenta (con una alta compresión). Otra forma de comprimir cadenas es convertirlas a UTF8, lo cual es rápido y fácil de hacer, y tiene una relación de compresión de casi el 50% para cadenas que no son unicode.

De cualquier forma que elija, siempre hay una compensación entre la huella de memoria y la velocidad de hash / compresión. Probablemente necesites hacer una evaluación comparativa para elegir la mejor solución.

Answer 4

Siempre que la huella de memoria sea tolerable, sugeriría un Hashset<string> para las cadenas y una cola para almacenar un Tuple<DateTime, String> . Algo como:

Hashset<string> Strings = new HashSet<string>();
Queue<Tuple<DateTime, String>> Expirations = new Queue<Tuple<DateTime, String>>();

Ahora, cuando entra una cuerda:

if (Strings.Add(s))
{
    // string is new. process it.
    // and add it to the expiration queue
    Expirations.Enqueue(new Tuple<DateTime, String>(DateTime.Now + ExpireTime, s));
}

Y, en algún lugar, deberá verificar los vencimientos. Quizás cada vez que recibes una nueva cadena, haces esto:

while (Expirations.Count > 0 && Expirations.Peek().Item1 < DateTime.Now)
{
    var e = Expirations.Dequeue();
    Strings.Remove(e.Item2);
}

Sería difícil superar el rendimiento de Hashset aquí. De acuerdo, estás almacenando las cadenas, pero esa será la única forma de garantizar que no haya falsos positivos.

También podría considerar usar una marca de tiempo que no sea DateTime.Now . Lo que normalmente hago es iniciar un Stopwatch cuando se inicia el programa y luego utilizar el valor de ElapsedMilliseconds . Eso evita los problemas potenciales que ocurren durante los cambios de horario de verano, cuando el sistema actualiza automáticamente el reloj (usando NTP), o cuando el usuario cambia la fecha / hora.

Si la solución anterior funciona para usted dependerá de si puede soportar el golpe de memoria de almacenar las cadenas.

Se agregó después de que se publicó "Información adicional":

Si a esto se accede por varios hilos, sugeriría usar ConcurrentDictionary lugar de Hashset , y BlockingCollection lugar de Queue . O bien, puede usar el lock para sincronizar el acceso a las estructuras de datos no concurrentes.

Si es verdad que el 99% de las cadenas no serán duplicadas, seguramente necesitarás una cola de vencimiento que puede eliminar cosas del diccionario.