Algoritmo eficiente del producto cartesiano

¿Puede alguien demostrarme un algoritmo de producto cartesiano más eficiente que el que estoy usando actualmente (suponiendo que exista 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 altamente simplificada de lo que hago en mi código. Los dos enteros son claves de búsqueda que se utilizan para recuperar uno o más objetos y todos los objetos de las dos búsquedas se emparejan en nuevos objetos.

Este pequeño bloque de código en un sistema mucho más complejo y más complejo se convierte en un importante cuello de botella de rendimiento ya que el conjunto de datos funciona sobre escalas. Algo de esto podría mitigarse mejorando las estructuras de datos usadas para almacenar los objetos y las búsquedas involucradas, pero el problema principal que siento es que todavía es el cálculo del producto cartesiano en sí mismo.

Editar

Así que más información sobre mi uso específico del algoritmo para ver si hay algún truco que pueda usar en respuesta al comentario de Marc. El sistema general es un motor de consulta SPARQL que procesa las consultas SPARQL sobre conjuntos de datos gráficos, SPARQL es un lenguaje basado en patrones, por lo que cada consulta consiste en una serie de patrones que se comparan con los gráficos. 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 varios patrones y es posible que deba calcular productos cartesianos varias veces, lo que puede conducir a una expansión bastante exponencial en posibles soluciones si la consulta se compone de una serie de patrones disjuntos.

De alguna manera, de las respuestas existentes dudo si hay algún truco que pueda aplicarse

Actualizar

Así que pensé en publicar una actualización sobre lo que implementé para minimizar la necesidad de hacer productos cartesianos 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.

Como cada BGP (Basic Graph Pattern) que es un conjunto de patrones triples se ejecuta como un bloque (en esencia), el motor puede reordenar patrones dentro de un BGP para un rendimiento óptimo. Por ejemplo, considere el siguiente BGP:

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

Ejecutar como es la consulta requiere un producto cartesiano ya que los resultados del primer patrón son disjuntos del segundo patrón, por lo que los resultados de los dos primeros patrones son un producto cartesiano de sus 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í:

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

Todavía necesitaremos un producto cartesiano para obtener los resultados finales, ya que los patrones segundo y tercero siguen siendo disjuntos, pero al reordenar, restringimos 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.

Hay algunas otras optimizaciones que hacemos, pero no voy a publicarlas aquí, ya que comienza a entrar en una discusión bastante detallada de las partes internas del motor SPARQL. Si alguien está interesado en más detalles solo deje un comentario o envíeme un tweet @RobVesse

La complejidad del producto cartesiano es O ( n 2 ), no hay atajos.

En casos específicos, el orden en que repites tus 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. Normalmente, una imagen se 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 externo 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.

Realmente no se puede cambiar el rendimiento de un ciclo nested sin algún conocimiento adicional, pero eso sería específico del uso. Si tiene n elementos en is m elementos en js , siempre va a ser O (n * m).

Sin embargo, puedes cambiar el aspecto :

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

Esto sigue siendo O (n * m), pero tiene una sobrecarga nominal adicional de LINQ (sin embargo, no lo notarás en el uso normal).

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

Una cosa que definitivamente debe evitarse es cualquier cosa que obligue a una combinación cruzada a búfer: el enfoque foreach es correcto y no búfer, pero si agrega cada elemento a una List<> , entonces tenga cuidado con las implicaciones de la memoria. Ditto OrderBy etc. (si se usa de forma inapropiada).

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, puede 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.

De 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 hash, la búsqueda en un producto cartesiano de m sets es solo una búsqueda en m hash que obtiene de forma gratuita. La construcción del producto cartesiano y la búsqueda de IsInSet toman O(m) tiempo, donde m es un número de conjuntos que se multiplican , y es mucho menor que n tamaño de cada conjunto.

Se agregó información adicional a la pregunta.

Los duplicados pueden evitarse si registra los que ya ha 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 duplicado.

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

También puede observar la paralelidad 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 .

Si la localidad de caché (o la memoria local requerida para mantener las j) es un problema, puede hacer que su algoritmo sea más amigable con la caché al dividir las matrices de entrada recursivamente. Algo 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 patrón de acceso aprovechará bastante bien todos los niveles de caché automático; este tipo de técnica se llama diseño de algoritmo de caché ajeno .

No sé cómo escribir Java-like-Iterators en C #, pero tal vez usted sepa y pueda transferir mi solución desde aquí a C # usted mismo.

Puede ser interesante si tus combinaciones son demasiado grandes para mantenerlas completamente en la memoria.

Sin embargo, si filtra por atributo sobre la colección, debe filtrar antes de construir 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.