Rob*_*obV 15 c# algorithm performance cartesian-product
有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法(假设有一个).我环顾四周,谷歌搜索了一下,但看不到任何明显的东西,所以我可能会遗漏一些东西.
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
Wil*_*ill 32
笛卡尔积的复杂度为O(n 2),没有捷径.
在特定情况下,迭代两个轴的顺序很重要.例如,如果您的代码访问数组中的每个插槽 - 或者访问图像中的每个像素 - 那么您应该尝试按自然顺序访问插槽.图像通常以"扫描线"布局,因此任何Y上的像素都是相邻的.因此,您应该遍历外部循环上的Y和内部上的X.
无论您是需要笛卡尔积还是更高效的算法取决于您正在解决的问题.
Mar*_*ell 10
如果没有一些额外的知识,你无法真正改变嵌套循环的性能,但这将是特定于用途的.如果你有n物品is和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等(如果使用不当).