La forma más rápida de encontrar objetos de una colección igualada por la condición de miembro de cadena

Question

Supongamos que tengo una colección (de una matriz, Lista genérica, o lo que sea más rápido la solución a este problema) de una determinada clase, vamos a llamar ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
} 

Asumir que hay va a ser como 50.000 objetos de la colección, todos en la memoria.Ahora quiero obtener tan rápido como sea posible todas las instancias de la colección que obedecer a un estado en su miembro de la barra, como por ejemplo este:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

¿Cómo puedo obtener los resultados tan rápido como sea posible?Debo considerar algunos avanzadas técnicas de indización y datastructures?

El dominio de la aplicación para este problema es un autocompleter, que recibe una consulta y le da una colección de sugerencias como resultado.Suponga que la condición no hay nada más complejo que esto.Suponga también que va a haber un montón de búsquedas.

Answer 1

Con la restricción de que la cláusula de condición puede ser "nada", entonces usted está limitado a la digitalización de toda la lista y la aplicación de la condición.

Si existen limitaciones en la cláusula de condición, entonces usted puede mirar en la organización de los datos de una forma más eficiente de manejar las consultas.

Por ejemplo, el código de ejemplo con "byFirstLetter" diccionario no ayuda en absoluto con un "endsWith" de la consulta.

Por lo tanto, realmente se reduce a lo que las consultas que usted desea hacer con los datos.

En las Bases de datos, este problema es la carga de "optimizador de consultas".En un ejemplo típico de la base de datos, si usted tiene una base de datos con índices, obviamente cada consulta va a ser un examen de la tabla.Como agregar los índices de la tabla, el optimizador puede utilizar los datos para hacer más sofisticado de los planes de consulta para llegar mejor a los datos.Ese es el problema que describes.

Una vez más concreto subconjunto de los tipos de consultas, a continuación, usted puede tomar una mejor decisión en cuanto a qué estructura es la mejor.También, es necesario considerar la cantidad de datos.Si usted tiene una lista de 10 elementos cada uno menos de 100 bytes, un análisis de todo lo que puede muy bien ser el más rápido de lo que puede hacer ya que tienen una pequeña cantidad de datos.Obviamente que no escala a un 1M elementos, pero incluso ingeniosas técnicas de acceso conllevan un costo en la instalación, mantenimiento (como el índice de mantenimiento), y la memoria.

EDITAR, basado en el comentario

Si es un auto que consuma, si los datos son estáticos, a continuación, ordenar y utilizar una búsqueda binaria.Realmente no va a conseguir más rápido que eso.

Si los datos son dinámicos, a continuación, guárdela en un árbol equilibrado, y que la búsqueda.Es, efectivamente, una búsqueda binaria, y le permite conservar agregar los datos al azar.

Otra cosa es cierta especialización en estos conceptos.

Answer 2

var Respuestas = milista.Donde(item => elemento.de la barra.StartsWith(consulta) || elemento.de la barra.EndsWith(consulta));

esa es la más fácil, en mi opinión, se debe ejecutar con bastante rapidez.

Answer 3

Seguro que no la entiendo...Todo lo que debes hacer es optimizar la regla, que es la parte que necesita ser más rápido.No se puede acelerar el bucle sin tirar a más de hardware en ella.

Usted puede paralelizar si usted tiene múltiples núcleos o máquinas.

Answer 4

No estoy en mi Java ahora mismo, pero me gustaría pensar acerca de lo siguiente.

Cómo crear tu lista?Tal vez usted puede crear ya ordenadas en una forma que reduce el tiempo de comparación.

Si solo estás haciendo una escalera de bucle a través de su colección, usted no verá mucha diferencia entre el almacenamiento como una matriz o una lista enlazada.

Para almacenar los resultados, dependiendo de cómo usted está recogida de los mismos, la estructura podría hacer una diferencia (pero suponiendo Java estructuras genéricas son inteligentes, no).Como ya he dicho, no estoy en mi Java, pero supongo que los genéricos de la lista enlazada mantener una cola de puntero.En este caso, no realmente hacer una diferencia.Alguien con más conocimientos de la matriz subyacente vs vinculado lista de la aplicación y cómo se termina buscando en el código de bytes probablemente podría decirle si añadiendo a una lista enlazada con la cola de un puntero o insertar en una matriz es más rápido (supongo que sería la matriz).Por otra parte, usted necesita saber el tamaño de su conjunto de resultados o sacrificar algo de espacio de almacenamiento y hacerla tan grande como toda la colección está iteración si se desea utilizar una matriz.

La optimización de la consulta de comparación por averiguar que la comparación es más probable que sea cierto y haciendo que uno de los primeros, también podría ayudar.es decir:Si en general el 10% del tiempo de un miembro de la colección se inicia con su consulta, y un 30% del tiempo de un miembro termina con la consulta, se quiere hacer la comparación final primera.

Answer 5

Para su caso en particular, la clasificación de la colección que la ayuda que usted podría binarychop para el primer elemento que se inicia con la consulta y de la terminación anticipada, al llegar a la siguiente que no;usted también podría producir una tabla de punteros a los objetos de la colección ordenada por el reverso de cada cadena para la segunda cláusula.

En general, si se conoce la estructura de la consulta por adelantado, usted puede ordenar tu colección (o crear varios índices ordenados para su colección, si hay varias cláusulas) de forma adecuada;si no lo hace, usted no será capaz de hacerlo mejor que la búsqueda lineal.

Answer 6

Si es algo que usted rellenar la lista una vez y, a continuación, hacer muchas búsquedas (en miles o más), entonces usted podría crear algún tipo de búsqueda de diccionario de mapas que comienza con/termina con los valores de sus valores reales.Que sería una búsqueda rápida, pero uso mucho más la memoria.Si usted no está haciendo que muchas búsquedas o sabes que vas a ser la repoblación de la lista al menos semi-frecuentemente me gustaría ir con la consulta LINQ que CQ sugerido.

Answer 7

Usted puede crear algún tipo de índice y se podría llegar más rápido.

Podemos construir un índice como este:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

A continuación, utilice el como esta:

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

Ahora nos posiblemente no tenga que recorrer como muchos ClassFoo como en tu ejemplo, pero de nuevo tenemos que mantener el índice hasta la fecha.No hay ninguna garantía de que es más rápido, pero es definitivamente más complicado.

Answer 8

Depende.Son todos los objetos siempre van a ser cargado en memoria?¿Tiene un límite finito de objetos que se pueden cargar?Serán sus consultas han de considerar los objetos que no se han cargado todavía?

Si la colección se agrandarán, definitivamente, me gustaría utilizar un índice.

De hecho, si la colección puede crecer hasta un tamaño arbitrario y no está seguro de que usted será capaz de encajar todo en la memoria, me vería en un ORM, una base de datos en memoria, o de otra base de datos incrustada.XPO de DevExpress para ORM o SQLite.Net para la base de datos en memoria viene a la mente.

Si no quieres ir tan lejos, hacer un índice simple que consiste en el "bar" referencias a miembros de asignación de referencias de clase.

Answer 9

Si el conjunto de posibles criterios es fijo y pequeño, puede asignar una máscara de bits para cada elemento en la lista.El tamaño de la máscara de bits es el tamaño del conjunto de los criterios.Cuando se crea un elemento/agregar a la lista, marque qué criterios se satisface y, a continuación, establezca los correspondientes bits en la máscara de bits de este elemento.La coincidencia de los elementos de la lista va a ser tan fácil como la coincidencia de sus máscaras de bits con el objetivo de máscara de bits.Un método más general es la Flor de filtro.