Tag: 笛卡尔积

C＃高级置换场景

我试图找出如何找到所有组合给出以下信息： 我从一个JSON数据集开始： var choices = { 1: {‘Q’: 100, ‘R’: 150, ‘W’ : 250, ‘T’, 30}, 2: {‘Q’: 90, ‘R’: 130, ‘W’ : 225, ‘T’, 28}, 3: {‘Q’: 80, ‘R’: 110, ‘W’ : 210, ‘T’, 25}, 4: {‘Q’: 70, ‘R’: 90, ‘W’ : 180, ‘T’, 22}, 5: {‘Q’: 60, ‘R’: 70, ‘W’ : 150, ‘T’, […]

高效的笛卡尔积算法

有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法（假设有一个）。 我环顾四周，谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。 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 . ?ba :Class . 按原样执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不相交，因此前两个模式的结果是其各自结果的笛卡尔积。 这个结果将包含比我们实际需要的结果更多的结果，因为第三个模式限制了第一个模式的可能结果，但我们直到之后才应用此限制。 但如果我们这样重新排序： ?ba :Class . ?a :someProperty ?b […]