manera eficiente de buscar cadenas en la lista de cadenas?

Tengo una lista de cadenas y necesito encontrar qué cadenas coinciden con un valor de entrada dado. ¿Cuál es la forma más eficiente (memoria frente a velocidad de ejecución) para que almacene esta lista de cadenas y pueda buscar a través de ella? La puesta en marcha y la carga de la lista de cadenas no es importante, pero el tiempo de respuesta para la búsqueda sí lo es.manera eficiente de buscar cadenas en la lista de cadenas?

¿Debería utilizar un List o un HashSet o solo un string básico [] o algo más?

Fuente

2011-12-28 MakkyNZ

¿Qué tan "grande" es la lista de cadenas? –

No se olvide de la clase StringCollection - http://msdn.microsoft.com/en-us/library/system.collections.specialized.stringcollection.aspx –

¿Puede una cadena ser un duplicado? ¿Es necesario que coincida con palabras/cadenas enteras o puede estar contenido dentro de una cadena? –

Depende en gran medida de la naturaleza de las cuerdas y el tamaño de la colección. Dependiendo de las características de la colección y las cadenas de búsqueda esperadas, hay formas de organizar las cosas muy inteligentemente para que la búsqueda sea muy rápida. No nos has dado esa información.

Pero esto es lo que haría. Establecí un requisito de rendimiento razonable. Entonces probaría un índice de n-gramas (¿por qué? Porque dijiste en un comentario que necesitas contabilizar las coincidencias parciales; un HashSet<string> no te ayudará aquí) y yo perfilaría las entradas razonables que espero contra esta solución y ver si cumple con mis requisitos de rendimiento o no. Si lo hace, aceptaría la solución y seguiré adelante. Si no es así, pensaría con mucho cuidado si mis requisitos de rendimiento son razonables o no. Si lo son, comenzaría a pensar si hay algo especial sobre mis entradas y colección que me permita usar algunas soluciones más inteligentes.

Fuente

2011-12-28 15:32:31 jason

Un HashSet no puede satisfacer sus necesidades de coincidencias parciales (y si las cadenas "se pueden duplicar" esto implica que hay alguna información para distinguir el duplicados, por lo que sería un diccionario de todos modos, en lugar de un HashSet) – Random832

@ Random832: ¡Su pregunta no dice nada sobre coincidencias parciales ni duplicados! – jason

Un comentario de seguimiento lo hizo, en su prisa por ser el FGITW, no se detuvo a preguntar qué era lo que se requería, la redacción original no implica un problema que pueda resolver un HashSet. Una lectura cuidadosa de "qué cadenas coinciden con un valor de entrada dado" revela que el plural implica coincidencias parciales (solo una cadena puede coincidir exactamente) – Random832

Utilice un Dictionary<string>() o un HashSet<string> es probablemente bueno para usted.

Fuente

2011-12-28 15:31:46

+1: eso también es lo primero que me vino a la mente al pensar en optimizar la cadena de búsqueda en la lista de cadenas: la primera solución común es "indexar", con un diccionario como la solución más común. –

@StephaneRolland Sí, la más simple es la mejor, pero incluso la solución gotafex vale la pena +1 –

-1

Diccionario y Hashtable van a ser los más rápidos en "buscar" porque es O (1) velocidad. Hay algunas caídas en Dictionaries y Hashtables en que no están ordenados.

Al utilizar un árbol de búsqueda binaria, podrá obtener la búsqueda O (Log N).

Al usar una lista no ordenada, tendrá O (N) velocidad de búsqueda.

Al utilizar una lista ordenada, obtendrá la búsqueda O (Log N), pero tenga en cuenta que la lista debe ordenarse de modo que agregue tiempo a la velocidad general.

En cuanto al uso de la memoria, solo asegúrese de inicializar el tamaño de la colección.

Por lo tanto, el diccionario o la tabla hash son los más rápidos de recuperar.

clasificaciones velocidad de mejor a peor son O (1) O (log n) O (n) O (n log n) O (n^2) O (2^n)

siendo n el número de elementos.

Fuente

2011-12-28 15:44:11 Odnxe

@FelicePollano. No creo que tenga el significado correcto de O (1). – Random832

@ Random832 es O (1) en la inserción. Al buscar, O (1) ubica la lista y luego realiza una búsqueda lineal. ¿Qué está mal para ti? –

El hecho de que la "lista" que debe buscarse linealmente [es decir la cadena de colisiones] es generalmente corta, y no en proporción con el número total de elementos en el diccionario (siempre que haya un número apropiado de cubos) significa que todavía está O (1) amortizado, a menos que haya un gran número de artículos con el mismo hash código [improbable a menos que sea deliberadamente construido de esta manera] se insertan. – Random832

Parece que la mejor manera es construir un árbol de sufijo de su entrada en el tiempo O (input_len) luego hacer consultas de sus patrones en el tiempo O (pattern_length). Entonces, si su texto es realmente grande en comparación con sus patrones, esto funcionará bien.

Consulte el algoritmo de Ukkonen para compilar un árbol de sufijos.

Si desea una correspondencia inexacta ... vea el trabajo de Gonzalo Navarro.

Fuente

2011-12-28 15:46:19

tx para editar. :) –

"basta con construir 256 o más matrices probables de 128 caracteres/byte para cada nodo en el trie". - la matriz sería de 256/128 _positores a nodos_, no a bytes. – Random832

O ... aún más correctamente ... una matriz, indexada por el código ascii (u otro juego de caracteres) del personaje, de referencias/punteros de objeto Nodo de nodo * = nodo nuevo [128]. Gracias Random832 por tu mejora. –

manera eficiente de buscar cadenas en la lista de cadenas?

Respuesta

Cuestiones relacionadas