高效的笛卡尔积算法
有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法（假设有一个）。 我环顾四周，谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。
foreach (int i in is) { foreach (int j in js) { //Pair i and j } } 这是我在代码中所做的高度简化的版本。 两个整数是查找键，用于检索一个/多个对象，两个查找中的所有对象一起配对到新对象中。
在一个更大更复杂的系统中，这个小块代码成为一个主要的性能瓶颈，因为它在规模上运行的数据集。 其中一些可能通过改进用于存储对象和所涉及的查找的数据结构来减轻，但我认为主要问题仍然是笛卡尔积本身的计算。
编辑
关于我对算法的具体用法的更多背景，看看是否有任何技巧可以用来回应Marc的评论。 整个系统是一个SPARQL查询引擎，它处理一组Graph数据的SPARQL查询，SPARQL是一种基于模式的语言，因此每个查询都包含一系列与Graph匹配的模式。 在两个后续模式没有公共变量（它们是不相交的）的情况下，有必要计算由两个模式产生的解的笛卡尔积，以获得整个查询的可能解的集合。 可能存在任何数量的模式，我可能需要多次计算笛卡尔积，如果查询由一系列不相交的模式组成，则可能导致可能的解决方案中相当指数级的扩展。
不知何故从现有的答案我怀疑是否有任何技巧可以应用
更新
所以我想我会发布我实施的内容的更新，以便最大限度地减少对笛卡尔积的需求，从而优化查询引擎。 请注意，并不总是可以完全消除对产品的需求，但几乎总是可以优化，因此连接的两组的尺寸要小得多。
由于作为一组三元模式的每个BGP（基本图形模式）作为一个块执行（实质上），引擎可以自由地重新排序BGP中的模式以获得最佳性能。 例如，考虑以下BGP：
?a :someProperty ?b . ?c :anotherProperty ?d . ?ba :Class .
按原样执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不相交，因此前两个模式的结果是其各自结果的笛卡尔积。 这个结果将包含比我们实际需要的结果更多的结果，因为第三个模式限制了第一个模式的可能结果，但我们直到之后才应用此限制。 但如果我们这样重新排序：
?ba :Class . ?a :someProperty ?b . ?c :anotherProperty ?d .
我们仍然需要一个笛卡尔积来得到最终结果，因为第二和第三个模式仍然是不相交的，但通过重新排序我们限制第二个模式的结果的大小意味着我们的笛卡尔积的大小将小得多。
我们做了一些其他的优化，但是我不打算在这里发布，因为它开始对SPARQL引擎内部进行相当详细的讨论。 如果有人对更多细节感兴趣，请发表评论或发送推文@RobVesse
笛卡尔积的复杂度为O（ n 2 ），没有捷径。
在特定情况下，迭代两个轴的顺序非常重要。 例如，如果您的代码访问数组中的每个插槽 – 或者访问图像中的每个像素 – 那么您应该尝试按自然顺序访问插槽。 图像通常以“扫描线”布局，因此任何Y上的像素都是相邻的。 因此，您应该遍历外部循环上的Y和内部上的X.
无论您是需要笛卡尔积还是更高效的算法都取决于您要解决的问题。
如果没有一些额外的知识，你无法真正改变嵌套循环的性能，但这将是特定于用途的。 如果在js有n项目和m项目，则它总是为O（n * m）。
你可以改变它的外观 ：
var qry = from i in is from j in js select /*something involving i/j */;
这仍然是O（n * m），但具有LINQ的标称额外开销（但在正常使用中你不会注意到它）。
你在做什么案件？ 可能有诡计……
绝对避免的一件事是强制交叉连接缓冲的任何事情 – foreach方法很好并且不缓冲 – 但是如果你将每个项目添加到List<> ，那么要注意内存含义。 Ditto OrderBy等（如果使用不当）。
我不能提出比O（n ^ 2）更好的建议，因为这是输出的大小，因此算法不能更快。
我可以建议使用另一种方法来确定是否需要计算产品。 例如，如果只是要查询某些元素是否属于它，您甚至可能不需要产品集P 您只需要有关它所组成的集合的信息。
确实（伪代码）
bool IsInSet(pair (x,y), CartesianProductSet P) { return IsInHash(x,P.set[1]) && IsInHash(y,P.set[2]) }
笛卡尔积计算如下：
// Cartesian product of A and B is P.set[1]=A; P.set[2]=B;
如果你将集合实现为哈希，那么在m集的笛卡尔积中查找只是一个你可以免费获得的哈希查找。 构造笛卡尔积和IsInSet查找每个都花费O(m)时间，其中m是您乘以的数集 ，并且它远小于每组的n大小。
该问题已添加其他信息。
如果您记录已经计算过的重复项，以避免重复它们，则可以避免重复项 – 假设这种簿记的成本 – 散列图或简单列表 – 小于计算重复项的成本。
C＃运行时非常快，但是对于极端繁重的工作，您可能希望使用本机代码。
您可能还会注意到此问题的基本并行性。 如果产品的计算不会影响任何其他产品的计算，则可以直接使用多处理器内核来并行执行工作。 看看ThreadPool 。 QueueUserWorkItem 。
如果缓存局部性（或维护j所需的本地内存）存在问题，则可以通过递归地对输入数组进行二等分来使算法更加缓存。 就像是：
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... }
请注意，此访问模式将自动充分利用所有级别的自动缓存; 这种技术称为缓存 – 遗忘算法设计。
我不知道如何在C＃中编写类似Java的迭代器，但也许你知道并且可以自己将我的解决方案从这里转移到C＃。
如果你的组合太大而无法将它们完全记忆在内，那就太有趣了。
但是，如果按属性对集合进行过滤，则应在构建组合之前进行过滤。 例：
如果您有1到1000之间的数字和随机单词并组合它们，然后过滤这些组合，其中数字可以被20整除，单词以’d’开头，您可以有1000 *（26 * x）= 26000 * x组合搜索。
或者您首先过滤数字，这将为您提供50个数字，并且（如果均匀分布）1个字符，最后只有50 * x个元素。