小编Joh*_*ith的帖子

是否有任何有效的技术可以进行以下求和？

给定有限集A,其包含n个整数A = {X1,X2,...,Xn},其中Xi是整数.现在有ň子集的一个,记为A1,A2,...,的.我们想要计算每个子集的总和.有一些有效的技术吗？

(注意,n通常大于A的所有子集的平均大小.)

例如,如果A = {1,2,3,4,5,6,7,9},A1 = {1,3,4,5},A2 = {2,3,4},则A3 = .. ..一种计算A1和A2总和的简单方法需要5个Flops来添加:

总和(A1)= 1 + 3 + 4 + 5 = 13

总和(A2)= 2 + 3 + 4 = 9

...

现在,如果首先计算3 + 4,然后记录其结果7,我们只需要3个Flops进行添加:

总和(A1)= 1 + 7 + 5 = 13

总和(A2)= 2 + 7 = …

给出一个 我们首先定义两个实值函数 和 如下:

我们还m(X)为每个矩阵定义一个值,X如下所示:

现在给出一个 ,我们有很多地区G,表示为.这里,G由子矩阵形成的区域是G从一些列和一些行中随机选择的G.我们的问题是计算尽可能少的操作.有没有像构建哈希表或排序以更快地获得结果的方法？谢谢!

========================

例如,如果G={{1,2,3},{4,5,6},{7,8,9}},那么

G_1 could be {{1,2},{7,8}}
G_2 could be {{1,3},{4,6},{7,9}}
G_3 could be {{5,6},{8,9}}

=======================

目前,对于每个G_i我们需要mxn比较来计算m(G_i).因此,m(G_1),...,m(G_r)应该有rxmxn比较.但是,我可以注意到G_i并且G_j可能重叠,因此会有一些更有效的方法.任何关注都将受到高度赞赏!

我有一组I = {P1,P2,...,Pm}和n个有限的I子集,由R1,R2,...,Rn表示如下:

R1 = {P1,P2}

R2 = {P2,P4}

R3 = {P2,P3,P4}

R4 = {P1,P2,P4}

....

其中Pi表示整数.

对于每个Ri,我想计算其所有元素的乘积.我的目标是通过在Ri(i = 1,2,...,n)之间共享一些公共部分来尽可能少地使用复用和除法.

例如,如果我可以先计算P2*P4,那么这个结果可用于计算R3和R4的所有元素的乘积.

请注意,也允许分割.例如,我可以首先计算A = P1*P2*P3*P4,然后使用A/P1计算R3的所有元素的乘积,并使用A/P3作为R4.

如果我想使用最小乘法和除法来计算I的每个子集的所有乘积,它是否是一个集合覆盖问题？NP完成？顺便说一句,你能给出一个整数线性程序公式来描述它就像这里一样.

任何建议将受到高度赞赏!

社区编辑:增加假设:

• 允许划分,与乘法相同的成本
• 给定集合中没有重复的元素.例如R5 = {P1, P1, P1, P2}是不允许的

我有一个数组:

a = [109, 894, 566, 453, 342, 25]

和另一个子索引的单元格数组a,表示为:

subs = { [1,3,4], [2,5,6], [1,3], [3,4], [2,3,4], [6] };    

我想避免for循环通过MATLAB计算以下求和:

for i=1:6
    sums_a(i) = sum(a(subs{i}));
end

有没有快速的方法arrayfun来实现这个？谢谢.

(我在这里敲我的头.让X = {x1,x2,...,xn}是一个整数集.让A1,A2,... Am是X的m个子集.对于任何i和j, Ai和Aj不一定是不相交的.现在的目标是有效地找到每个Ai(i = 1,...,m)的最大值,操作次数越少越好.

例如,给定X = {2,4,6,3,1},其子集A1 = {2,3,1},A2 = {2,6,3,1},A3 = {4,2, 3,1}.我们需要分别找到Max {A1},Max {A2},Max {A3}.

查找Max {A1},Max {A2},Max {A3}的强力方法是扫描每个Ai中的所有元素,并且需要(m*d)个操作,m为X的子集数量,和d是X的子集{Ai}的平均长度.

现在,我有一些观察:

(1)对于任何集合Y⊆X,max {Y}≤max{X},

例如,由于Max {X} = 6且6在A2中,因此可以直接找到Max {A2} = 6.

(2)对于任何两个集A和B,如果A∩B非空,则可以如下识别Max {A}和Max {B}:

首先,我们找到A和B之间的公共部分,取而代之的是c = max {A∩B}.

然后,我们发现Max {A} = Max {Max {A-(A∩B)},c}和Max {B} = Max {Max {B-(A∩B)},c}.

我不确定是否还有一些其他有趣的obervations来找到这些最大值.热烈欢迎任何想法!

我的问题是,如果对于一般情况,当X = {x1,x2,...,xn}并且有m个子集X时,表示为A1,A2,... Am,是否有一些更有效的技术可供查找这样的最大值Max {Ai}(i = 1,...,m)？

我们将非常感谢您的帮助!

昨天我了解到余弦相似度,定义为

可以有效地测量两个向量的相似程度.

我发现这里的定义使用L2范数来标准化和的点积,A而B我感兴趣的是为什么不使用A和B分母中的L1范数？

我的老师告诉我,如果我在分母中使用L1范数,那么余弦相似度不会是1 A=B.然后,我进一步问他,如果我修改余弦相似度定义如下,与原始模型相比,修改后的模型有哪些优缺点？

如果A!= B,则sim(A,B)=(A*B)/(|| A || 1*|| B || 1)

如果A == B,则sim(A,B)= 1

如果有人能给我一些解释,我将不胜感激.