¿Puede alguien, por favor, demostrarme un algoritmo de producto cartesiano más eficiente que el que estoy usando actualmente (asumiendo que hay uno)? Miré a mi alrededor y busqué en Google un poco, pero no veo nada obvio, por lo que podría faltar 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 / 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 grande y complejo se convierte en un importante cuello de botella de rendimiento a medida que el conjunto de datos se está ejecutando en escalas. Algo de esto podría ser mitigado mejorando las estructuras de datos utilizadas para almacenar los objetos y las búsquedas involucradas, pero el problema principal que siento es el cálculo del producto cartesiano en sí.

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 consultas SPARQL que procesa consultas SPARQL sobre conjuntos de datos de Gráficos, SPARQL es un lenguaje basado en patrones, por lo que cada consulta consta de una serie de patrones que se comparan con los Gráficos. En el caso de que dos patrones subsiguientes no tengan variables comunes (son desunidas), 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 cantidad de patrones y es posible que tenga que calcular los 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, a partir de las respuestas existentes, dudo que haya 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 completamente la necesidad de productos, pero casi siempre es posible optimizarlos, por lo que el tamaño de los dos conjuntos que se unen es mucho menor.

Dado que cada BGP (Patrón de gráfico básico), que es un conjunto de Patrones triples, se ejecuta como un bloque (en esencia), el motor es libre de reordenar los patrones dentro de un BGP para un rendimiento óptimo. Por ejemplo, considere el siguiente BGP:

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

La ejecución como se hace en la consulta requiere un producto cartesiano, ya que los resultados del primer patrón están separados 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í:

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

Todavía necesitaremos un producto cartesiano para obtener los resultados finales, ya que los patrones 2 y 3 aún están desarticulados, pero al reordenar restringimos el tamaño de los resultados del patrón 2, lo que significa que el tamaño de nuestro producto cartesiano será mucho menor.

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