这是我遇到的问题的简化版本.假设我有一个向量
p = [1 5 10]
还有一个
q = [.75 .85 .95].
我想提出以下矩阵:
res = [1,.75; 1,.85; 1,.95; 5,.75; 5,.85; 5,.95; 10,.75; 10,.85; 10,.95].
这也称为笛卡尔积.我怎样才能做到这一点？
非常感谢
我最终确信这个问题有一个答案,但是对于我的生活来说无法弄清楚如何去做.
假设我有三套:
A = [ 'foo', 'bar', 'baz', 'bah' ]
B = [ 'wibble', 'wobble', 'weeble' ]
C = [ 'nip', 'nop' ]
而且我知道如何计算笛卡尔/十字架产品,(蚂蚁它覆盖了整个地方,在这个网站和其他地方)所以我不会在这里讨论它.
我正在寻找的是一种算法,它允许我简单地从笛卡尔积中选择一个特定项而不生成整个集或迭代直到我到达第n个项.
当然,我可以很容易地迭代一个像这样的小例子集,但我正在处理的代码将使用更大的集合.
因此,我正在寻找一个功能,我们称之为'CP',其中:
CP(1) == [ 'foo', 'wibble', 'nip' ]
CP(2) == [ 'foo', 'wibble', 'nop' ]
CP(3) == [ 'foo', 'wobble', 'nip' ]
CP(4) == [ 'foo', 'wobble', 'nop' ]
CP(5) == [ 'foo', 'weeble', 'nip' ]
CP(6) == [ 'foo', 'weeble', 'nop' ]
CP(7) == [ 'bar', 'wibble', 'nip' ]
...
CP(22) …有人可以为我演示一个比我目前使用的更有效的笛卡尔积算法(假设有一个).我环顾四周,谷歌搜索了一下,但看不到任何明显的东西,所以我可能会遗漏一些东西.
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
从前一个问题我学到了一些有趣的东西.如果Python itertools.product是由一系列迭代器提供的,那么这些迭代器将在笛卡尔积开始之前转换为元组.相关 问题查看源代码,itertools.product得出结论:虽然没有中间结果存储在内存中,但是在产品迭代开始之前创建了原始迭代器的元组版本.
问题:当(元组转换的)输入太大而无法保存在内存中时,有没有办法为笛卡尔积创建迭代器？琐碎的例子:
import itertools
A = itertools.permutations(xrange(100))
itertools.product(A)
一个更实际的用例将采用一系列(*iterables[, repeat])类似于函数的原始实现 - 上面只是一个例子.它看起来不像你可以使用当前的实现itertools.product,所以我欢迎在纯python中提交(虽然你不能击败C后端itertools!).
我试图从两个潜在的无限流中召唤一个笛卡尔积，然后我通过limit().
到目前为止，这（大约）是我的策略：
@Test
void flatMapIsLazy() {
Stream.of("a", "b", "c")
.flatMap(s -> Stream.of("x", "y")
.flatMap(sd -> IntStream.rangeClosed(0, Integer.MAX_VALUE)
.mapToObj(sd::repeat)))
.map(s -> s + "u")
.limit(20)
.forEach(System.out::println);
}
这不起作用。
显然，我的第二个流在第一次在管道上使用时就被当场进行了最终评估。它不会产生我可以按照自己的节奏使用的惰性流。
我认为.forEach这段代码中的原因ReferencePipeline#flatMap是：
@Override
public void accept(P_OUT u) {
try (Stream<? extends R> result = mapper.apply(u)) {
if (result != null) {
if (!cancellationRequestedCalled) {
result.sequential().forEach(downstream);
}
else {
var s = result.sequential().spliterator();
do { } while (!downstream.cancellationRequested() && s.tryAdvance(downstream));
}
}
}
}
我希望上面的代码返回 20 …
我想在Perl中进行排列.例如,我有三个数组:["big", "tiny", "small"]然后我有["red", "yellow", "green"],也有["apple", "pear", "banana"].
如何得到:
["big", "red", "apple"] ["big", "red", "pear"] ..etc.. ["small", "green", "banana"]
我理解这叫做排列.但我不知道该怎么做.另外我不知道我可以拥有多少阵列.可能有三个或四个,所以我不想做嵌套循环.
我被给了一个谜题作为礼物.它由4个立方体组成,并排排列.每个立方体的面是四种颜色之一.
为了解决难题,立方体必须定向,以便所有四个立方体的顶部不同,它们的所有前沿都不同,它们的背部都是不同的,并且它们的底部都是不同的.左右两边无所谓.
我的伪代码解决方案是:
我使用F#中的伪代码实现解决了这个难题,但我对第3步的处理方式并不满意:
let problemSpace =
seq { for c1 in cube1Orientations do
for c2 in cube2Orientations do
for c3 in cube3Orientations do
for c4 in cube4Orientations do
yield [c1; c2; c3; c4] }
上面的代码非常具体,只能得出四个方向序列的笛卡尔积.我开始考虑为n个方向序列编写它的方法.
我提出了(从现在开始的所有代码应该在F#interactive中执行得很好):
// Used to just print the contents of a list.
let print =
Seq.fold (fun s i -> s + i.ToString()) "" >> printfn "%s"
// Computes the product of two sequences - kind of; the 2nd argument is …我正在尝试实现一个方法,该方法将获取列表列表并返回这些列表的笛卡尔积.
这是我到目前为止所拥有的:
(defn cart
([] '())
([l1] (map list l1))
([l1 l2]
(map
(fn f[x] (map
(fn g [y] (list x y))
l2))
l1)
)
)
(defn cartesian-product [& lists]
(reduce cart lists)
)
;test cases
(println (cartesian-product '(a b) '(c d))) ; ((a c) (a d) (b c) (b d))
(println (cartesian-product ())) ;()
(println (cartesian-product '(0 1))) ; ((0) (1))
(println (cartesian-product '(0 1) '(0 1))) ; ((0 0) (0 1) (1 0) (1 1))
(println (apply cartesian-product …我有两张桌子,custassets和tags.为了生成一些测试数据,我想做INSERT INTO一个多对多的表,SELECT每个表从每个表中获取随机行(这样一个表中的随机主键与第二个表中的随机主键配对).令我惊讶的是,这并不像我最初想的那么容易,所以我坚持用这个来自学.
这是我的第一次尝试.我选择10 custassets和3 tags,但两者在每种情况下都相同.第一个表被修复后我会没事的,但是我想随机分配分配的标签.
SELECT
custassets_rand.id custassets_id,
tags_rand.id tags_rand_id
FROM
(
SELECT id FROM custassets WHERE defunct = false ORDER BY RANDOM() LIMIT 10
) AS custassets_rand
,
(
SELECT id FROM tags WHERE defunct = false ORDER BY RANDOM() LIMIT 3
) AS tags_rand
这会产生:
custassets_id | tags_rand_id
---------------+--------------
9849 | 3322 }
9849 | 4871 } this pattern of tag PKs is repeated
9849 | 5188 } …我试图创建一些工具来创建基于其他类型组合的类型列表。
可以说我们有三种类型
struct A{};
struct B{};
struct C{};
我想获得一个元组列表，其中包含N，A，B或C个类型的所有可能组合。
对于N = 2的情况，这将是
std::tuple<A,A>
std::tuple<A,B>
std::tuple<A,C>
std::tuple<B,A>
std::tuple<B,B>
std::tuple<B,C>
std::tuple<C,A>
std::tuple<C,B>
std::tuple<C,C>
这个想法是创建一个元组来容纳所有这些类型的容器，因此我以后可以在容器列表中存储任何这些类型。
template <typename ...Combinations>
using CombinationList = std::tuple<std::vector<Combinations>...>;
我已经有一种机制可以在适合的容器中插入一个特殊的元素，但是我对如何创建组合一无所知。
在人们建议使用的评论上std::vector<Combination<std::variant<A,C,B>, std::variant<A,B,C>>>。尽管这从技术上解决了问题，但我不喜欢使用它，因为A，BC的大小非常不同，并且我不想在运行时访问变体。另外，在某些时候，我需要将所有数据上传到
std::tuple<std::vector<Combination>...>
到GPU，所以我不能在这里使用std :: variant。
我该怎么办？
谢谢！
PD：这与一个问题有关（一个枚举值（729个组合...）的组合爆炸）。 在这个问题中，我问我如何轻松生成将放入容器内的类型。现在我需要生成容器。
c++ cartesian-product template-meta-programming variadic-templates c++14