高效笛卡尔积算法

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

回答：

笛卡尔积的复杂度为O（ n 2），没有捷径。

在特定情况下，迭代两个轴的顺序很重要。例如，如果您的代码正在访问数组中的每个插槽或图像中的每个像素，那么您应该尝试以自然顺序访问这些插槽。图像通常以“扫描线”布局，因此任何

Y 上的像素都相邻。因此，您应该迭代外部循环上的 Y 和内部循环上的 X。

是否需要笛卡尔乘积或其他哪种更有效的算法取决于您要解决的问题。

以上是 高效笛卡尔积算法 的全部内容， 来源链接： utcz.com/qa/426683.html

回到顶部