.NET: ¿Cómo verificar eficientemente la exclusividad en una lista <string> de 50,000 artículos?

En algún código de biblioteca, tengo una lista que puede contener 50,000 elementos o más..NET: ¿Cómo verificar eficientemente la exclusividad en una lista <string> de 50,000 artículos?

Las personas que llaman a la biblioteca pueden invocar métodos que den como resultado la adición de cadenas a la lista. ¿Cómo controlo de manera eficiente la exclusividad de las cadenas que se agregan?

Actualmente, justo antes de agregar una cadena, escaneo toda la lista y comparo cada cadena con la cadena que se va a agregar. Esto comienza a mostrar problemas de escala por encima de 10.000 elementos.

Analizaré esto, pero estoy interesado en la información.

si reemplazo la Lista <> con un diccionario <>, se ContainsKey() ser apreciablemente más rápido que la lista crece hasta 10.000 artículos y más allá?
si difiero la verificación de exclusividad hasta que todos los artículos se hayan agregado, ¿será más rápido? En ese punto, necesitaría verificar cada elemento contra cualquier otro elemento, aún una operación n ^^ 2.

EDITAR

Algunos resultados básicos de referencia. Creé una clase abstracta que expone 2 métodos: Rellenar y Escanear. Fill simplemente llena la colección con n elementos (utilicé 50,000). El escaneo escanea la lista m veces (utilicé 5000) para ver si un valor dado está presente. Luego construí una implementación de esa clase para List y otra para HashSet.

Las cadenas utilizadas tienen uniformemente 11 caracteres de longitud y se generan aleatoriamente mediante un método en la clase abstracta.

Una micro-referencia muy básica.

Hello from Cheeso.Tests.ListTester 
filling 50000 items... 
scanning 5000 items... 
Time to fill: 00:00:00.4428266 
Time to scan: 00:00:13.0291180 

Hello from Cheeso.Tests.HashSetTester 
filling 50000 items... 
scanning 5000 items... 
Time to fill: 00:00:00.3797751 
Time to scan: 00:00:00.4364431

Así, para las cadenas de esa longitud, HashSet es aproximadamente 25 veces más rápido que la lista, al escanear la singularidad. Además, para este tamaño de colección, HashSet tiene cero penalización sobre la Lista al agregar elementos a la colección.

Los resultados son interesantes y no son válidos. Para obtener resultados válidos, necesitaría hacer intervalos de calentamiento, pruebas múltiples, con selección aleatoria de la implementación. Pero estoy seguro de que eso moverá el listón solo ligeramente.

Gracias a todos.

Edit2

Después de la adición de la aleatorización y multple ensayos, HashSet constantemente supera a la lista, en este caso, en alrededor de 20 veces.

Estos resultados no son necesariamente válidos para cadenas de longitud variable, objetos más complejos o diferentes tamaños de colección.

Fuente

2009-12-07 Cheeso

Un diccionario definitivamente será más rápido, ya que utiliza un hash debajo de las cubiertas. – Joe

+12

Un 'HashSet' será aún más rápido, ya que no usa espacio adicional para un valor. – SLaks

si difiere el cheque, puede ordenar la lista (o una copia) y verificar cada elemento con el vecino. no necesitarías cada elemento contra cada otro elemento entonces. –

Debe utilizar la clase HashSet<T>, que está diseñada específicamente para lo que está haciendo.

Fuente

2009-12-07 14:30:04 SLaks

Sí, el 'Add () 'método devolverá falso si el elemento ya estaba presente en la colección. –

Use HashSet<string> en lugar de List<string>, entonces debería escalar muy bien.

Fuente

2009-12-07 14:30:38

He leído que el diccionario <> se implementa como una matriz asociativa. En algunos idiomas (no necesariamente todo lo relacionado con .NET), los índices de cadenas se almacenan como una estructura de árbol que se bifurca en cada nodo en función del carácter en el nodo. Por favor, consulte http://en.wikipedia.org/wiki/Associative_arrays.

Una estructura de datos similar fue ideada por Aho y Corasick en 1973 (creo). Si almacena 50,000 cadenas en dicha estructura, entonces no importa cuántas cadenas esté almacenando. Importa más el longitud de las cadenas. Si tienen la misma longitud, es probable que nunca veas una ralentización en las búsquedas porque el algoritmo de búsqueda es lineal en tiempo de ejecución con respecto a la longitud de la cadena que estás buscando. Incluso para un árbol rojo-negro o árbol AVL, el tiempo de ejecución de búsqueda depende más de la longitud de la cadena que está buscando en lugar de la cantidad de elementos en el índice. Sin embargo, si elige implementar sus claves de índice con una función hash, ahora incurre en el costo de hash de la cadena (va a ser O (m), m = longitud de cadena) y también la búsqueda de la cadena en el índice, que probablemente estará en el orden de O (log (n)), n = número de elementos en el índice.

editar: No soy un gurú de .NET. Otras personas más experimentadas sugieren otra estructura. Yo tomaría su palabra sobre la mía.

edición2: su análisis está un poco apagado para comparar la singularidad. Si usa una estructura o diccionario hash, entonces no será una operación O (n^2) debido al razonamiento que publiqué anteriormente. Si continúa utilizando una lista, entonces tiene razón en que es O (n^2) * (longitud máxima de una cadena en su conjunto) porque debe examinar cada elemento de la lista cada vez.

Fuente

2009-12-07 14:34:15

FIY, en .NET, un diccionario se implementa como una tabla hash. No es una estructura de árbol. La longitud de la cadena solo es importante para calcular los valores hash. –

... y produce O (1) tiempo de búsqueda, por cierto. –

@Martinho hace este "hash" significa un tipo de hash molinero-rabin o el tipo de hash que veo en otros idiomas que usan el estilo de almacenamiento Aho-Corasick? Esa es mi pregunta. ¿podrías indicarme algunos documentos? Gracias por corregirme :) –

De mis pruebas, HashSet<string> no tiene tiempo en comparación con List<string> :)

Fuente

2009-12-07 14:37:09 mYsZa

¿De verdad necesitabas probar eso? Espero que sí, o la informática está construida sobre algunas teorías bastante sombrías. (Eso, o quienquiera que haya escrito la biblioteca .net lo perdió mucho) – mpen

@Mark, por supuesto que no estaba probando. Era un metaphore/sarcasmo :) – mYsZa

hace la función Contains(T) no funciona para usted?

Fuente

2009-12-07 14:42:24 Bobby

Probablemente sí, pero es lento con la Lista . – mYsZa

Sí, eso es correcto. Es lento. Pero en realidad la situación es un poco más complicada de lo que describí. Es una lista donde T contiene una propiedad que es una cadena. Por lo tanto, no es, de hecho, una lista . Además, el Contains() * que quiero * tiene que probar la equivalencia de valor, no la igualdad de objeto. Así que había estado usando una iteración para revisar todos los elementos de la lista y comparar la propiedad de la cadena en cada elemento con la propiedad Strnig en la instancia candidata para agregarla a la lista. Y eso es muy lento. – Cheeso

Posiblemente fuera del tema, pero si desea escalar conjuntos de cadenas únicos muy grandes (millones +) de una manera independiente del idioma, puede consultar Bloom Filters.

Fuente

2009-12-07 15:28:39

Discutí los filtros de floración en un documento que escribí sobre el examen de cantidades voluminosas de datos durante el proceso forense. Parecen ser buenos preprocesadores para descartar obvios faltas de coincidencia, y si su escenario lo justifica, puede construir un índice basado en los falsos positivos solo para verificar a partir de ese momento, pero ¿por qué no simplemente indexarlos desde el principio? y saltee ese paso y arroje el filtro de floración? –

Probablemente el espacio es la razón principal para implementar un filtro de floración, ¿no? –

Gracias por el aviso. Esta es exactamente la solución que estaba buscando. – gap

.NET: ¿Cómo verificar eficientemente la exclusividad en una lista <string> de 50,000 artículos?

Respuesta

Cuestiones relacionadas