相关疑难解决方法(0)

我有这个问题现在弯曲了一段时间(头冷也没有帮助!),基本上我有一个PHP数组,看起来像这个例子:

$array[0][0] = 'apples';
$array[0][1] = 'pears';
$array[0][2] = 'oranges';

$array[1][0] = 'steve';
$array[1][1] = 'bob';

而且我希望能够从这个表格中生成每种可能的组合,但不重复任何组合(无论它们的位置如何),所以例如这将输出

Array 0            Array 1
apples             steve
apples             bob
pears              steve
pears              bob

但我希望能够使用尽可能多的不同阵列.

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

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 .
?b a :Class .

按原样执行查询需要笛卡尔积,因为第一个模式的结果与第二个模式不相交,因此前两个模式的结果是其各自结果的笛卡尔积.这个结果将包含比我们实际需要的结果多得多的结果,因为第三个模式限制了第一个模式的可能结果,但我们直到之后才应用此限制.但如果我们这样重新排序:

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

我们仍然需要笛卡尔积来获得最终结果,因为第二和第三种模式仍然是不相交的,但通过重新排序我们限制第二种模式的结果大小意味着我们的笛卡尔积的大小将小得多.

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