高效的笛卡尔积算法

Question

请问有没有比我目前使用的笛卡尔积算法更高效的演示（如果有的话）？我已经在SO和谷歌上搜索了一些东西，但是没有看到任何明显的线索，所以可能我遗漏了什么。

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

这是我在代码中所做的高度简化版本。这两个整数是用于检索一个或多个对象的查找键，所有来自这两个查找的对象都会成对组合成新对象。

在更复杂的系统中，这个小代码块会成为性能瓶颈，特别是当它作用于大型数据集时。改善用于存储对象和查找的数据结构可能会缓解其中一些问题，但我认为主要问题仍然是计算笛卡尔积本身。

编辑

因此，为了让Marc理解，我需要提供有关我的特定用途的更多背景信息，看看是否有任何技巧可以使用。整体系统是一个SPARQL查询引擎，可处理对图形数据集的SPARQL查询。 SPARQL是一种基于模式的语言，因此每个查询由一系列模式组成，这些模式与图形匹配。如果两个连续模式没有共同的变量（它们是不相交的），则必须计算由两个模式产生的解的笛卡尔积，以获取整个查询的可能解集。模式可能有任意数量，并且我可能需要多次计算笛卡尔积，如果查询由一系列不相交的模式组成，则可能导致可能解的指数级扩展。

从现有答案中，我怀疑是否有任何技巧可供应用

更新

所以我想发布一个更新，关于我实施的最小化需要执行笛卡尔积以优化查询引擎的方法。请注意，并非总是完全消除产品的需求，但通常可以对其进行优化，使要连接的两个集合的大小更小。

由于每个BGP（基本图案模式），即三元组模式集合，都被视为块（本质上），引擎可以自由地重新排列BGP中的模式以获得最佳性能。例如，请考虑以下BGP：

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

执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不重叠，所以前两个模式的结果是它们各自结果的笛卡尔积。这个结果将包含比我们实际需要的更多的结果，因为第三个模式限制了第一个模式的可能结果，但我们直到后来才应用这个限制。但是如果我们重新排序如下：

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

我们仍然需要进行一个笛卡尔积来获取最终结果，因为第二个和第三个模式仍然是不相交的，但通过重新排序我们限制了第二个模式结果的大小，这意味着我们的笛卡尔积的大小将会小得多。

还有一些其他的优化，但我不会在这里发布它们，因为这涉及到 SPARQL 引擎内部的相当详细的讨论。如果有人对进一步的细节感兴趣，请留言或发送推文@RobVesse。

- RobV

---

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx - tugberk

Answer 1

笛卡尔积的时间复杂度为O(n²), 没有捷径。

在特定情况下，迭代两个轴的顺序是很重要的。例如，如果您的代码正在访问数组中的每个槽位或图像中的每个像素，则应尝试以自然顺序访问槽位。 图像通常按“扫描行”布局，因此任何Y上的像素都是相邻的。因此，您应该在外部循环中迭代Y，在内部循环中迭代X。

您需要笛卡尔积还是更高效的算法取决于您正在解决的问题。

- Will

---

准确地说，笛卡尔积的输出是O(n^2)，这意味着仅在内存中写下输出就需要O(n^2)次操作，因此没有算法可以更快。 - ldog

Answer 2

如果没有额外的知识，你无法真正改变嵌套循环的性能，但这将是使用特定的。 如果在is中有n个项目，并且在js中有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<>中，则要注意内存影响。同样，OrderBy等也要避免不当使用。

- Marc Gravell

---

如果你正在使用C# 4.0或者PLINQ版本，并且有一台多核机器，你可以添加一个.AsParallel()，例如from i in is.AsParallel()。 - Rubens Farias

我为我的情况添加了更多背景，但我怀疑是否有任何技巧可以应用。 - RobV

当然你可以混合使用LINQ和检查（checks），不过问题在于这个点。注意Rubens的观点——我喜欢那个；-p - Marc Gravell

我实际上转向了C# 4.0，并发现AsParallel()实际上会使我的性能变差，因为产品中的逻辑非常简单，但所有线程都必须写回到一个共同的数据结构中，线程同步意味着AsParallel()最终会恶化而不是提高性能。我可能可以重构以避免线程同步，但我还没有机会尝试。 - RobV

另一个更新，经过一些尝试，我成功地通过更改底层数据结构来存储结果，从而使得 PLINQ 提高了性能，因此不需要线程同步。 - RobV

Answer 3

我无法提供比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 个集合的笛卡尔积中查找只需要在您免费获得的 m 个哈希表中查找。构建笛卡尔积和 IsInSet 查找每个都需要 O(m) 时间，其中 m 是您要乘以的集合数量，并且它比每个集合的大小 n 小得多。

- P Shved

---

不幸的是，必须拥有整个产品集，所以你的想法在我的情况下行不通，尽管它很好。 - RobV

@RobV，那么，哎呀，你被n平方了！ :-) - P Shved

Answer 4

问题已添加附加信息。

如果记录已计算过的内容以避免重复计算，则可以避免重复项 - 假定这种簿记成本 - hashmap或简单列表的成本小于计算重复项的成本。

C#运行时非常快，但对于极端的重负载，您可能需要转到本机代码。

您还可能注意到此问题的必要并行性。如果产品的计算不会影响任何其他产品的计算，则可以直接使用多个处理器核心并行执行工作。请查看ThreadPool。QueueUserWorkItem。

- Will

---

就我的情况而言，重复是必要的，某种形式的并行可能会起到作用。 - RobV

Answer 5

如果缓存局部性（或维护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...
}

请注意，这种访问模式将自动充分利用所有级别的自动缓存；这种技术被称为cache-oblivious算法设计。

- comingstorm

Answer 6

我不知道如何在C#中编写类似Java的迭代器，但也许你知道并且可以将我的解决方案从这里转换成C#。

如果您的组合太大而无法完全保存在内存中，则可能会很有趣。

然而，如果您按属性过滤集合，则应在构建组合之前进行过滤。例如：

如果您有从1到1000的数字和随机单词，并将它们组合起来，然后过滤那些数字可被20整除且单词以'd'开头的组合，您可能需要搜索1000 *（26 * x）= 26000 * x个组合。

或者您可以先过滤数字，这将为您提供50个数字和（如果均匀分布）1个字符，最终只有50 * x个元素。

- user unknown

---

是的，理论上这是可能的，但在我的架构中并不容易应用。同意尽可能早地进行过滤，我们实际上会在产品计算中尽可能地加入过滤器，并且总是尝试先应用仅适用于产品一侧的过滤器，然后再计算产品。 - RobV