c# - LINQ Performance para grandes colecciones

.net

Question

Tengo una gran colección de cadenas ordenadas alfabéticamente (hasta 1M). He experimentado con consultas LINQ contra esta colección utilizando HashSet, SortedDictionary y Dictionary. Estoy almacenando en caché estático la colección, tiene un tamaño de hasta 50 MB, y siempre estoy llamando a la consulta LINQ contra la colección en caché. Mi problema es el siguiente:

Independientemente del tipo de colección, el rendimiento es mucho menor que el de SQL (hasta 200 ms). Cuando se realiza una consulta similar contra las tablas SQL subyacentes, el rendimiento es mucho más rápido (5-10 ms). He implementado mis consultas LINQ de la siguiente manera:

public static string ReturnSomething(string query, int limit)
{
  StringBuilder sb = new StringBuilder();
  foreach (var stringitem in MyCollection.Where(
      x => x.StartsWith(query) && x.Length > q.Length).Take(limit))
  {
      sb.Append(stringitem);
  }

  return sb.ToString();
}

Tengo entendido que el HashSet, el Diccionario, etc. implementan búsquedas utilizando la búsqueda de árbol binario en lugar de la enumeración estándar. ¿Cuáles son mis opciones para las consultas LINQ de alto rendimiento en los tipos de colección avanzada?

Answer 1

Apuesto a que tiene un índice en la columna para que el servidor SQL pueda hacer la comparación en operaciones O (log (n)) en lugar de O (n). Para imitar el comportamiento del servidor SQL, use una colección ordenada y busque todas las cadenas s que s> = consulta y luego mire los valores hasta que encuentre un valor que no comience con s y luego haga un filtro adicional en los valores. Esto es lo que se denomina exploración de rango (Oracle) o búsqueda de índice (servidor SQL).

Este es un código de ejemplo que es muy probable que entre en bucles infinitos o que tenga errores puntuales porque no lo probé, pero debería tener una idea.

// Note, list must be sorted before being passed to this function
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) {
    int low = 0, high = list.Count - 1;
    while (high > low) {
        int mid = (low + high) / 2;
        if (list[mid] < query)
            low = mid + 1;
        else
            high = mid - 1;
    }

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length)
        yield return list[low];
        low++;
    }
}

Answer 2

Creo que el problema es que Linq no tiene forma de usar el hecho de que tu secuencia ya está ordenada. Especialmente no se puede saber que la aplicación de la función StartsWith mantiene el orden.

Yo sugeriría usar el método List.BinarySearch junto con un IComparer<string> que hace solo la comparación de los primeros caracteres de consulta (esto podría ser complicado, ya que no está claro si la cadena de consulta siempre será el primer o el segundo parámetro a () ).

Incluso podría usar la comparación de cadenas estándar, ya que BinarySearch devuelve un número negativo que puede complementar (usando ~) para obtener el índice del primer elemento que es más grande que su consulta.

Luego debe comenzar desde el índice devuelto (¡en ambas direcciones!) Para encontrar todos los elementos que coincidan con su cadena de consulta.

Answer 3

En su código actual no hace uso de ninguna de las características especiales de las colecciones Dictionary / SortedDictionary / HashSet , las está utilizando de la misma manera que usaría una List . Es por eso que no ves ninguna diferencia en el rendimiento.

Si usa un diccionario como índice donde los primeros caracteres de la cadena son la clave y una lista de cadenas es el valor, puede seleccionar de la cadena de búsqueda una pequeña parte de la colección completa de cadenas que tenga posibles coincidencias.

Escribí la siguiente clase para probar esto. Si lo lleno con un millón de cadenas y busco con una cadena de ocho caracteres, rasga todas las coincidencias posibles en aproximadamente 3 ms. La búsqueda con una cadena de un carácter es el peor de los casos, pero encuentra las primeras 1000 coincidencias en aproximadamente 4 ms. Encontrar todas las coincidencias para las cadenas de un carácter toma aproximadamente 25 ms.

La clase crea índices para las claves de 1, 2, 4 y 8 caracteres. Si observa sus datos específicos y lo que busca, debería poder seleccionar qué índices crear para optimizarlos para sus condiciones.

public class IndexedList {

    private class Index : Dictionary<string, List<string>> {

        private int _indexLength;

        public Index(int indexLength) {
            _indexLength = indexLength;
        }

        public void Add(string value) {
            if (value.Length >= _indexLength) {
                string key = value.Substring(0, _indexLength);
                List<string> list;
                if (!this.TryGetValue(key, out list)) {
                    Add(key, list = new List<string>());
                }
                list.Add(value);
            }
        }

        public IEnumerable<string> Find(string query, int limit) {
            return
                this[query.Substring(0, _indexLength)]
                .Where(s => s.Length > query.Length && s.StartsWith(query))
                .Take(limit);
        }

    }

    private Index _index1;
    private Index _index2;
    private Index _index4;
    private Index _index8;

    public IndexedList(IEnumerable<string> values) {
        _index1 = new Index(1);
        _index2 = new Index(2);
        _index4 = new Index(4);
        _index8 = new Index(8);
        foreach (string value in values) {
            _index1.Add(value);
            _index2.Add(value);
            _index4.Add(value);
            _index8.Add(value);
        }
    }

    public IEnumerable<string> Find(string query, int limit) {
        if (query.Length >= 8) return _index8.Find(query, limit);
        if (query.Length >= 4) return _index4.Find(query,limit);
        if (query.Length >= 2) return _index2.Find(query,limit);
        return _index1.Find(query, limit);
    }

}

Answer 4

Si está haciendo un "comienza con", solo le interesan las comparaciones ordinales, y puede ordenar la recopilación (nuevamente en el orden ordinal), entonces le sugiero que tenga los valores en una lista. Luego, puede realizar una búsqueda binaria para encontrar el primer valor que comienza con el prefijo correcto, luego bajar la lista de forma lineal y generar resultados hasta el primer valor que no comienza con el prefijo correcto.

De hecho, probablemente podría hacer otra búsqueda binaria para el primer valor que no comience con el prefijo, por lo que tendría un punto inicial y un punto final. Luego, solo debe aplicar el criterio de longitud a esa parte correspondiente. (Espero que si se trata de datos razonables, la coincidencia de prefijos se librará de la mayoría de los valores candidatos). La forma de encontrar el primer valor que no comienza con el prefijo es buscar el primer valor lexicográficamente que no - por ejemplo, con un prefijo de "ABC", busque "ABD".

Nada de esto usa LINQ, y todo es muy específico para su caso particular, pero debería funcionar. Déjame saber si algo de esto no tiene sentido.

Answer 5

Si está tratando de optimizar la búsqueda de una lista de cadenas con un prefijo dado, es posible que desee echar un vistazo a la implementación de una estructura de datos Trie (que no debe confundirse con un tree regular) en C #.

Los intentos ofrecen búsquedas de prefijos muy rápidas y tienen una sobrecarga de memoria muy pequeña en comparación con otras estructuras de datos para este tipo de operación.

Sobre LINQ a Objetos en general. No es raro tener una reducción de velocidad en comparación con SQL. La red está llena de artículos que analizan su rendimiento.

Answer 6

Solo mirando su código, diría que debería reordenar la comparación para aprovechar el cortocircuito cuando se usan operadores booleanos:

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit))

La comparación de longitud siempre será una operación O (1) (ya que la longitud se almacena como parte de la cadena, no cuenta cada carácter cada vez), mientras que la llamada a StartsWith será una O (N) operación, donde N es la longitud de la consulta (o la longitud de la cadena, la que sea menor).

Al realizar la comparación de la longitud antes de la llamada a StartsWith, si esa comparación falla, se ahorra algunos ciclos adicionales que podrían sumarse al procesar grandes cantidades de artículos.

No creo que una tabla de búsqueda te ayude aquí, ya que las tablas de búsqueda son buenas cuando estás comparando la clave completa, no partes de la clave, como hace con la llamada a StartsWith.

Más bien, puede que sea mejor utilizar una estructura de árbol que se divide según las letras de las palabras en la lista.

Sin embargo, en ese momento, simplemente está recreando lo que está haciendo SQL Server (en el caso de los índices) y eso solo sería una duplicación de esfuerzos por su parte.