18

有人可以为我演示一种比我目前使用的更有效的笛卡尔积算法（假设有一个）。我环顾四周，用谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。

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 .

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

我们还进行了一些其他优化，但我不打算在这里发布它们，因为它开始对 SPARQL 引擎内部进行相当详细的讨论。如果有人对更多细节感兴趣，请发表评论或给我发推文@RobVesse

4

6 回答 6

34

笛卡尔积的复杂度为 O( n 2 )，没有捷径可走。

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

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

于 2009-11-16T10:44:47.487 回答
11

如果没有一些额外的知识，你不能真正改变嵌套循环的性能，但这将是特定于使用的。如果你有n项目 inis和m项目js，它总是 O(n*m)。

你可以改变它的外观：

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

这仍然是 O(n*m)，但具有名义上的 LINQ额外开销（但在正常使用中您不会注意到它）。

你在做什么？可能有套路...

绝对要避免的一件事是任何强制交叉连接缓冲的事情 - 这种foreach方法很好并且不会缓冲 - 但是如果你将每个项目添加到 a List<>，那么请注意内存影响。同上OrderBy等（如果使用不当）。

于 2009-11-16T10:45:37.407 回答
4

我无法提出比 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的数量在哪里，而且它比每组的 --size少得多。n

于 2009-11-16T12:36:05.283 回答
3

附加信息已添加到问题中。

如果您记录您已经计算过的那些以避免再次重复它们，则可以避免重复 - 假设这种簿记的成本 - 哈希图或简单列表 - 低于计算重复的成本。

C# 运行时确实非常快，但是对于极其繁重的工作，您可能需要使用本机代码。

您可能还会注意到这个问题的基本并行性。如果一个产品的计算不影响任何其他产品的计算，您可以直接使用多个处理器内核并行完成工作。看看线程池。队列用户工作项。

于 2009-11-16T11:46:02.293 回答
1

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

请注意，这种访问模式将自动很好地利用所有级别的自动缓存；这种技术被称为缓存遗忘算法设计。

于 2009-11-16T12:23:27.377 回答
1

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

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

但是，如果您按集合上的属性进行过滤，则应在构建组合之前进行过滤。例子：

如果您有从 1 到 1000 的数字和随机单词并将它们组合，然后过滤这些组合，其中数字可被 20 整除并且单词以“d”开头，则可以有 1000*(26*x)=26000*要搜索的 x 个组合。

或者你先过滤数字，这会给你 50 个数字和（如果均匀分布）1 个字符，最后只有 50*x 个元素。

于 2012-06-04T15:34:27.927 回答