我正在为我个人的粒子物理研究做一个矢量排序算法,但我对编码非常陌生。
对于更大数量的网络矢量元素,通过蛮力遍历单个场景(特定矢量大小和组合)会变得非常混乱,特别是因为整个代码将循环多达1 e5次。
取“风味”A和B的四个向量:A+、A-、B+和B-。我需要找到总共两对元素,使得某个值k(V+,V-)在不同风味不能组合的限制下最大化!(V只是风味占位符)
例如:
A+ = {a1+} A- = {a1-}
B+ = {b1+,b2+} B- = {b1-}
因为A+和A-各只有一个元素,所以值k(A+,A-)-〉k(a1+,a1-)。但是对于风味B,有两种可能的组合。
k(b1+,b1-)或k(b2+,b1-)
我想确保k值较大的元素的组合被保留下来。正如我之前所说的,这个具体的例子并不太糟糕,但假设B+和B-各有两个元素?可能的值将是:
k(b1+,b1-)或k(b2+,b2-)或k(b1+,b2-)或k(b2+,b1-)
其中只有一个是正确的。此外,假设这四个B+B-组合中的两个具有比A+A-更大的k。这也将是有效的!
任何帮助都将不胜感激!!!我可以澄清,如果上面的任何东西是过于混乱!
我试过这样的方法,
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static bool sortbypair(const pair<double, double> &a, const pair<double, double> &b)
{
return (k(a.first, a.second) > k(b.first, b.second)) && k(a.first, b.second) < k(a.second, b.first);
}
但我不能具体描述。
2条答案
按热度按时间ttvkxqim1#
如果我没理解错你的问题,
k
,它将两个double
(或一个std::pair<double, double>
) Map到一个double
。* 我假设是double
,这在问题中并不清楚,严格来说,它也不是问题的核心。*std::vector<double>
:第一个元素是aplus
,第二个元素是aminus
,第三个元素是bplus
和第四个元素是bminus
。std::pair<double, double>
,你可以通过组合aplus
和aminus
中的元素以及分别来自bplus
和bminus
的所有组合来形成。k
最大化的对k
的值排序我说的对吗?你在问题里说
我需要找到两个总对的元素,使某个值k(V+,V-)最大化[...]
这让我有点困惑。
我的建议是把你的问题分解成三个子任务:
1.创建向量
Vplus
和Vminus
中元素的所有组合的范围,通常表示为笛卡尔积Vplus x Vminus
。1.连接步骤1中为
aplus x aminus
和bplus x bminus
创建的范围,以获得域中所有可行对的范围。1.最大化/排序步骤2中的范围。
使用范围-v3实现
range-v3库为这类任务提供了一些非常方便的工具。
向量看起来像这样:
让我们定义一个表示域的范围:
pairs_view
示例实际上并不在内存中的任何地方创建数据对,它只是一个适配器对象,让你可以迭代所有你能以指定方式构造的数据对。当你(或算法)迭代数据对时,数据对是“懒洋洋地”动态创建的。让我们打印域中的所有对:
输出量:
查找最大元素
让我们先定义一个方便函数 (这里是lambda expression的形式),该函数计算
k
的一个双精度元组:你可以在域中找到一个最大化
k
的对的迭代器,只需一行代码:输出量:
函数
max_element
得到两个额外的参数。第一个是比较函数,如果两个元素按顺序排列,则返回true。我们提供了默认的less
函子。第二个参数是可选的投影,在比较之前应用于每个元素。我们传递k_proj
。将上面的代码行读为 “在
pairs_view
中找到投影到其k
值最大的元素,其中我们要将投影值与标准less函数进行比较。"获取域的排序范围
如果你想在你的域中拥有所有对的排序范围,我们必须先为你的域创建一个
std::vector<std::pair<double, double>>
,然后再排序它。你不能对用range-v3库创建的视图进行排序,因为它们只是一个现有对象的视图,它们不能被改变。另外,我们必须将cartesian_product
函数中的range-v3库创建的特殊对类型Map到实际的std::pair<double, double
,以便将值复制到新容器中:注意,“管道”运算符
|
是函数组合to_vector(view::transform(pairs_view, to_std_pair))
的简写。排序算法的调用与max_element算法的调用非常相似:
让我们打印结果:
输出量:
以下是完整的实时代码示例:https://godbolt.org/z/6zo8oj3ah
如果您不想使用range-v3库,您有两个选择:
1.您可以等待。range-v3库的大部分已经被添加到C20的标准库中。相关函数
concat
、cartesian_product
和to_vector
可能会被添加到即将到来的标准C23中。1.标准库有
max_element
和sort
,所以你可以自己实现级联和笛卡尔积:https://godbolt.org/z/7Y5dG16WKwqnecbli2#
谢谢每一个评论的人!!!我真的很感谢你的努力。解决方案最终比我想象的要简单得多。
从本质上讲,从我使用的物理程序,粒子是以列表的形式给出的(即533 e-,534 p+,535 e+等)。我不知道如何让range-v3工作(或任何外部库,但谢谢你的建议),所以我想出了一个元组的索引组合粒子和他们的相关k值。
这不是很完美,但因为我只寻找前两个最高的k值,它的工作刚刚好。再次感谢!