给定:给定2D平面中的一组N个点(x和y坐标),以及对应于每个点的一组N个半径.我们将参考一个点的光盘,因为光盘以其半径为中心.
问题:聚集点.点簇使得每个点EITHER落入簇中至少一个其他点的盘内,或者簇中的至少一个其它点落入其盘内.单点集群不计为集群.
我需要一种算法来有效地计算它(最好不要求助于复杂的空间散列技术,如kd-trees).我可以满足O(N ^ 2)运行时间但绝对不超过O(N ^ 3).我觉得这应该很简单但是我已经陷入了我的聚类条件的非互惠性质.
本质上,我希望填写C函数原型:
int cluster_points(
size_t n,
point_t *pt, // length n list of points
double *radius, // length n list of radii for each point
int *cluster, // length n list of cluster indexes; -1 if not clustered
size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster)
);
这不是功课.我需要这个作为聚类复数的矩阵算法的一部分.
我主要使用C++进行科学计算,最近我一直把自己局限于一个类似C语言的C++子集; 也就是说,除了复杂和STL之外没有类/继承,模板只用于查找/替换各种替换,还有一些其他的东西我不能放在我的脑海里.我想知道在我选择和选择使用哪些功能时,是否有任何正式或有文档记录的C++语言子集供我参考(以及基本原理).
我有一组简单的(没有洞,没有自交叉)多边形,我需要检查它们是否相互交叉(一个可以完全包含在另一个中;这没关系).我可以通过简单地检查一个多边形与其他多边形的每个顶点内部的关系来检查这一点.
我还需要确定包含树,它是一组关系,说明哪个多边形包含任何给定的多边形.由于没有多边形可以与任何其他多边形相交,因此任何包含的多边形都具有唯 "下一个更大的".换句话说,如果A包含B包含C,则A是B的父亲,B是C的父亲,我们不认为A是C的父亲.
问题:如何有效地确定包含关系并检查非交叉标准？我问这个问题是因为组合算法可能比单独解决每个问题更有效.该算法应该将多边形列表作为输入,由它们的顶点列表给出.它应该产生一个布尔B,表明没有多边形与任何其他多边形相交,如果B =真,则产生一对(P,C)的列表,其中多边形P是子C的父.
这不是功课.这是我正在做的一个爱好项目.
我刚刚问了一个与编译器如何优化某些C++代码有关的问题,我正在寻找有关如何验证编译器是否已执行某些优化的任何问题.我试图查看用g ++(g++ -c -g -O2 -Wa,-ahl=file.s file.c)生成的汇编列表,可能会看到底层发生了什么,但输出对我来说太神秘了.人们使用什么技术来解决这个问题,是否有任何关于如何解释优化代码的汇编列表或特定于GCC工具链的文章的讨论这个问题的参考？
假设我有类似的课程
class Empty{
Empty(int a){ cout << a; }
}
然后我用它来调用它
int main(){
Empty(2);
return 0;
}
这是否会导致在堆栈上分配任何内存以创建"空"对象？显然,参数需要被推入堆栈,但我不想产生任何额外的开销.基本上我使用构造函数作为静态成员.
我想这样做的原因是因为模板.实际的代码看起来像
template <int which>
class FuncName{
template <class T>
FuncName(const T &value){
if(which == 1){
// specific behavior
}else if(which == 2){
// other specific behavior
}
}
};
这让我可以写出像
int main(){
int a = 1;
FuncName<1>(a);
}
这样我就可以专门化一个模板参数,而不必指定类型T.此外,我希望编译器将优化构造函数内的其他分支.如果有人知道这是真的还是如何检查,那将非常感激.我还假设投掷模板进入情况不会改变上面的"空类"问题,是吗？
我正在寻找合并两个排序列表的算法,但它们缺少一个列表的元素和另一个列表的元素之间的比较运算符.生成的合并列表可能不是唯一的,但是满足每个列表的相对排序顺序的任何结果都可以.更确切地说:
鉴于:
{a_1, ..., a_m},和B = {b_1, ..., b_n}.(它们也可以被视为集合).<在每个列表的元素之间定义
的优先级运算符a_i < a_{i+1},以及b_j < b_{j+1}for 1 <= i <= m和for 1 <= j <= n.a_i < b_j未定义任何有效i和j.=在A或B的所有元素之间定义的相等运算符(它在A中的元素和B中的元素之间定义).产生:
列表C = {c_1, ..., c_r}这样:
C = union(A, B); C的元素是A和B元素的联合.c_p = a_i,c_q = a_j和a_i < a_j,那么c_p < c_q.(应保留对应于集合A和B的C的子列表的元素顺序.i …我目前有类层次结构
MatrixBase -> DenseMatrix
-> (other types of matrices)
-> MatrixView -> TransposeView
-> DiagonalView
-> (other specialized views of matrices)
MatrixBase是一个抽象类,它强制实现者定义operator()(int,int)等等; 它代表二维数字数组.MatrixView表示一种(可能是可变的)查看矩阵的方式,例如转置它或采用子矩阵.关键MatrixView是能够说出类似的话
Scale(Diagonal(A), 2.0)
其中Diagonal返回DiagonalView对象,它是一种轻量级的适配器.
现在这是问题所在.我将使用一个非常简单的矩阵运算作为例子.我想定义一个像这样的函数
template <class T>
void Scale(MatrixBase<T> &A, const T &scale_factor);
这就是名字暗示的显而易见的事情.我希望能够传递一个诚实到善的非视图矩阵,或者一个子类的实例MatrixView.上面写的原型不适用于诸如此类的语句
Scale(Diagonal(A), 2.0);
因为DiagonalView返回的对象Diagonal是临时的,并且Scale采用非const引用,这不能接受临时的.有没有办法让这项工作？我试图使用SFINAE,但我不太了解它,我不确定这是否能解决问题.对我来说很重要的是,可以在不提供显式模板参数列表的情况下调用这些模板化函数(我想要隐式实例化).理想情况下,上述陈述可以按照书面形式运作
编辑:(后续问题)
由于sbi在下面回答了关于右值引用和临时值的问题,有没有办法定义两个版本的Scale,一个为非视图采用非const rvalue引用,另一个采用按值传递视图？问题是在编译时区分这两者,使隐式实例化起作用.
更新
我已经将类层次结构更改为
ReadableMatrix
WritableMatrix : public ReadableMatrix
WritableMatrixView
DenseMatrix : public WritableMatrix
DiagonalView : public WritableMatrixView
原因WritableMatrixView不同于WritableMatrix …
我需要生成N位整数的(伪)随机序列,其中连续的整数与前一个整数的差别仅为1位,并且序列从不重复.我知道格雷码会产生只有1位差异的非重复序列,而LFSR会产生非重复的随机序列,但我不知道如何将这些想法结合起来产生我想要的东西.
实际上,N会非常大,比如说1000.我想随机抽样这个2 ^ 1000整数的大空间,但我需要生成类似随机游走的东西,因为应用程序只能从一个数字跳到另一个数字翻了一下.
我有兴趣使用MPI(消息传递接口)实现一种事件驱动的调度队列.我想解决的基本问题是:我有一个主进程将作业插入全局队列,每个可用的从进程检索队列中的下一个作业(如果有).
从我读到的关于MPI的内容来看,发送和接收进程似乎必须就发送和接收的时间达成一致.如同,假设一个进程发送消息但另一个进程不知道它需要接收,反之亦然,那么一切都会死锁.有没有办法让每个过程更加独立？
我正在寻找一个很好的例子,说明如何重载流输入操作符(operator >>)以使用简单的文本格式解析一些数据.我已阅读本教程,但我想做一些更先进的事情.在我的情况下,我有固定的字符串,我想检查(和忽略).假设链接中的2D点格式更像
Point{0.3 =>
0.4 }
其中预期的效果是解析数字0.3和0.4.(是的,这是一个非常愚蠢的语法,但它包含了我需要的几个想法).大多数情况下,我只是想看看如何正确检查是否存在固定字符串,忽略空格等.
更新: 哎呀,我在下面做的评论没有格式化(这是我第一次使用这个网站).我发现可以用类似的东西跳过空格
std::cin >> std::ws;
为了吃掉我的食物
static bool match_string(std::istream &is, const char *str){
size_t nstr = strlen(str);
while(nstr){
if(is.peek() == *str){
is.ignore(1);
++str;
--nstr;
}else{
is.setstate(is.rdstate() | std::ios_base::failbit);
return false;
}
}
return true;
}
现在能够获得解析错误的位置(行号)会很好.
更新2: 获得行号和注释解析工作,只使用1个字符前瞻.最终结果可以在AArray.cpp中的函数parse()中看到.该项目是一个(de)可序列化的C++ PHP类数组类.