eficiente algoritmo de producto cartesiano

Question

Puede alguien demostrar para mí un algoritmo de producto cartesiano más eficiente que el que estoy usando actualmente (suponiendo que hay uno). Miré alrededor de SO y busqué en Google un poco, pero no puedo ver nada obvio, así que podría perderme algo.

foreach (int i in is) { 
    foreach (int j in js) { 
     //Pair i and j 
    } 
} 

Esta es una versión muy simplificada de lo que hago en mi código. Los dos números enteros son las operaciones de búsqueda teclas que se utilizan para recuperar una/varias objetos y todos los objetos de las dos búsquedas se emparejen en nuevos objetos.

Este pequeño bloque de código en un sistema más complejo mucho más grande se convierte en un importante cuello de botella como el conjunto de datos se está operando en escalas. Algo de esto probablemente podría mitigarse mediante la mejora de las estructuras de datos utilizadas para almacenar los objetos y las operaciones de búsqueda involucrados, pero el principal problema que siento es todavía el cálculo del propio producto cartesiano.

Editar

Así algunos antecedentes más en mi uso específico del algoritmo para ver si puede haber algún truco que puedo usar en respuesta al comentario de Marc. El sistema global es un motor de consulta SPARQL que procesa consultas SPARQL sobre conjuntos de datos gráfica, SPARQL es un lenguaje basado patrón de modo que cada consulta consta de una serie de patrones que se compara con el gráfico (s). En el caso en que dos patrones subsiguientes no tengan variables comunes (son disjuntos), es necesario calcular el producto cartesiano de las soluciones producidas por los dos patrones para obtener el conjunto de soluciones posibles para la consulta general. Puede haber cualquier número de patrones y voy a tener que calcular cartesianas productos varias veces lo que puede conducir a una expansión bastante exponencial de las posibles soluciones si la consulta se compone de una serie de patrones disjuntos.

alguna manera de las respuestas existentes Dudo que haya ningún tipo de trucos que se podría aplicar

actualización

así que pensé que iba a publicar una actualización sobre lo que he implementado con el fin de reducir al mínimo la necesidad de hacer cartesiana productos y así optimizar el motor de consultas en general. Tenga en cuenta que no siempre es posible eliminar por completo la necesidad de productos, pero casi siempre es posible optimizarlo, por lo que el tamaño de los dos conjuntos que se unen es mucho menor.

Puesto que cada BGP (Patrón Gráfico básico), que es un conjunto de patrones triple es ejecutado como un bloque (en esencia) el motor es libre de cambiar el orden de patrones dentro de un BGP para un rendimiento óptimo. Por ejemplo, considere la siguiente BGP:

?a :someProperty ?b . 
?c :anotherProperty ?d . 
?b a :Class . 

Ejecutado como es la consulta requiere un producto cartesiano ya que los resultados del primer patrón son disjunta de la segunda patrón de lo que los resultados de los dos primeros patrones es un producto cartesiano de su resultados individuales Este resultado contendrá muchos más resultados de los que realmente necesitamos, ya que el tercer patrón restringe los posibles resultados del primer patrón, pero no aplicamos esta restricción hasta después. Pero si reordenamos así:

?b a :Class . 
?a :someProperty ?b . 
?c :anotherProperty ?d . 

Todavía necesitará un producto cartesiano para obtener los resultados finales, ya que la 2ª y 3ª patrones son todavía desunido pero reordenando se restringe el tamaño de los resultados del segundo patrón lo que significa que el tamaño de nuestro producto cartesiano será mucho más pequeño.

Existen algunas otras optimizaciones que hacemos, pero no las voy a publicar aquí ya que comienzan a entrar en una discusión bastante detallada de las partes internas del motor SPARQL. Si alguien está interesado en más detalles, simplemente dejar un comentario o enviarme un tweet @RobVesse

Answer 1

La complejidad del producto cartesiano es O (n ), no hay ningún atajo.

En casos específicos, el orden que iterar su dos ejes es importante. Por ejemplo, si su código visita cada ranura de una matriz, o cada píxel de una imagen, entonces debe intentar visitar las ranuras en orden natural. Una imagen está típicamente presenta en ‘líneas de exploración’, por lo que los píxeles en cualquier Y son adyacentes. Por lo tanto, debe iterar sobre la Y en el bucle exterior y la X en el interior.

Si necesita el producto cartesiano o si es un algoritmo más eficiente depende del problema que está resolviendo.

Answer 2

No se puede cambiar realmente el rendimiento de un bucle anidado sin algún conocimiento adicional, pero eso sería específico del uso. Si usted tiene n artículos en ism y artículos en js, siempre va a ser O (n * m).

Puede cambiar el aspecto de él sin embargo:

var qry = from i in is 
      from j in js 
      select /*something involving i/j */; 

Esto sigue siendo O (n * m), pero tiene nominal adicional sobrecarga de LINQ (no se dará cuenta que en condiciones normales uso, sin embargo).

¿Qué estás haciendo en tu caso? Puede haber trucos ...

Una cosa a definitivamente evitar es cualquier cosa que obliga a una cruzada unirse para amortiguar - el enfoque foreach está muy bien y no almacena - pero si se agrega cada elemento a un List<>, entonces ten cuidado con las implicaciones de la memoria. Ditto OrderBy, etc. (si se usa de forma inapropiada).

Answer 3

información adicional se ha añadido a la pregunta.

Se pueden evitar los duplicados si se graban los que ya se han computado para evitar duplicarlos nuevamente. Se supone que el costo de dicha contabilidad (un hashmap o una lista simple) es menor que el costo de calcular un duplicar.

El tiempo de ejecución de C# es realmente muy rápido, pero para cargas extremas extremas, es posible que desee ingresar al código nativo.

También se podría notar el paralelismo esencial de este problema. Si el cálculo de un producto no afecta el cálculo de ningún otro producto, podría usar directamente núcleos de múltiples procesadores para realizar el trabajo en paralelo. Mira ThreadPool. QueueUserWorkItem.

Answer 4

Si la localidad de caché (o la memoria local necesaria para mantener las j) es un problema, puede hacer que su algoritmo sea más fácil de almacenar en caché mediante la bisección de las matrices de entrada recursivamente.Algo así como:

cartprod(is,istart,ilen, js,jstart,jlen) { 
    if(ilen <= IMIN && jlen <= JMIN) { // base case 
    for(int i in is) { 
     for(int j in js) { 
     // pair i and j 
     } 
    } 
    return; 
    } 
    if(ilen > IMIN && jlen > JMIN) { // divide in 4 
    ilen2= ilen>>1; 
    jlen2= jlen>>1; 
    cartprod(is,istart,ilen2,   js,jstart,jlen2); 
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart,jlen2); 
    cartprod(is,istart+ilen2,ilen-ilen2, js,jstart+jlen2,jlen-jlen2); 
    cartprod(is,istart,ilen2,   js,jstart+jlen2,jlen-jlen2); 
    return; 
    } 
    // handle other cases... 
} 

Tenga en cuenta que este esquema de acceso automáticamente tomará bastante buena ventaja de todos los niveles de caché automático; este tipo de técnica se llama diseño de algoritmo cache-oblivious.

Answer 5

No puedo proponer nada mejor que O (n^2), porque ese es el tamaño de la salida, y el algoritmo por lo tanto no puede ser más rápido.

Lo que puedo sugerir es utilizar otro enfoque para saber si necesita calcular el producto. Por ejemplo, es posible que ni siquiera necesite el conjunto de productos P si solo va a consultar si ciertos elementos le pertenecen. Solo necesita la información sobre los conjuntos de los que está compuesta.

hecho (pseudocódigo)

bool IsInSet(pair (x,y), CartesianProductSet P) 
{ 
    return IsInHash(x,P.set[1]) && IsInHash(y,P.set[2]) 
} 

donde el producto cartesiano se calcula así:

// Cartesian product of A and B is 
P.set[1]=A; P.set[2]=B; 

Si implementa conjuntos como hashes, a continuación, las operaciones de búsqueda en un producto cartesiano de m conjuntos es sólo una búsqueda en hash m que obtienes de forma gratuita. La construcción del producto cartesiano y la búsqueda IsInSet cada toma O(m) tiempo, donde m es un número de conjuntos multiplica, y es mucho menos que n --size de cada conjunto.

Answer 6

No sé cómo escribir Java-like-Iterators en C#, pero tal vez usted conozca y pueda transferir my solution from here a C# usted mismo.

Puede ser interesante que sus combinaciones sean demasiado grandes para mantenerlas completamente en la memoria.

Sin embargo, si filtra por atributo sobre la colección, debe filtrar antes de generar la combinación. Ejemplo:

Si tiene números del 1 al 1000 y palabras aleatorias y los combina, y luego filtra esas combinaciones, donde el número es divisible entre 20 y la palabra comienza con 'd', podría tener 1000 * (26 * x) = 26000 * x combinaciones para buscar.

O primero filtra los números, lo que le da 50 números, y (si se distribuye por igual) 1 carácter, que son solo 50 * x elementos al final.