问题描述
在做求平面内最近点对的问题时，使用两种不同的比较方法求最小距离，算法效率在100000输入规模下相差2~3倍，很费解，想向大家求助。
具体来说只有求两点距离的方法是不一样的（然而却导致了不同）：
一是先一直用平方表示距离，最后输出算开根
if (s == e) return MAX; //如果只有一个点返回无限大 if (s + 1 == e) return square(ar[s], ar[e]);//如果只有两个点返回开根后的距离
二是每次都直接算出开根以后的距离
if (s == e) return MAX; //如果只有一个点返回无限大 if (s + 1 == e) return dis(ar[s], ar[e]);//如果只有两个点返回开根后的距离
以上两种情况都是递归到底后执行，此外还有比较中间是否有最小距离时需要用到
curmin = min(curmin, square(ar[sr[i]], ar[sr[j]]));curmin = min(curmin, dis(ar[sr[i]], ar[sr[j]]));//(当前求得的两边最小值,中间最小值）
double dis(Node a, Node b) { return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); } //返回点与点之间的距离double square(Node a, Node b) { return pow(a.x - b.x, 2) + pow(a.y - b.y, 2); } //square()和dis()除了是否开根以外没有任何差别。
两种方法在100000规模下运行20次取平均运行时间如图1和图2所示
图1 dis方法
图2 square方法
输入使用随机数，在随机数中规模大约平均在10的4次方，显然square产生的数字要比dis大得多，每次比较的数字也大的多，比较的复杂度是O(n)的。但是用同样的类型存储数据，也都没有溢出，占位应该是相同的，而且比较是大家都要比较的，dis方法只是数比较小，何况dis每次运算是通过计算平方再开根，多了开根这一步，为什么用dis方法反而会快呢？如何理解数据规模对比较的影响呢？
源码如下：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<time.h>using namespace std;double MAX = 1e10; //定义的最大距离，以在只有一个点的时返回无穷大int a, b; //用来记录下标，与题无关struct Node { double x, y; int key; //关键码，可有可无，与ab有关};Node ar[100005];int sr[100005];bool cmpx(Node a, Node b) { return a.x<b.x; } //x坐标升序bool cmpy(Node a, Node b) { return a.y<b.y; } //y坐标升序int listcmp(const void *a, const void *b){ if (ar[*(int*)a].y < ar[*(int*)b].y)//中间的是下标return -1; elsereturn 1;}double min(double a, double b) { return a<b ? a : b; } //返回最小值double dis(Node a, Node b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } //返回点与点之间的距离double square(Node a, Node b) { return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);}void create(int n) { srand((unsigned)time(NULL)); for (int i = 0; i<n; i++) {ar[i].key = i + 1; dr[i].x = rand();dr[i].y = rand();//cout << 'x ' << (ar[i].x = dr[i].x) << ' y ' << ((ar[i].y = dr[i].y)) << endl;//cout << 'x ' << (cr[i].x = dr[i].x) << ' y ' << ((cr[i].y = dr[i].y)) << endl;ar[i].x = dr[i].x; ar[i].y = dr[i].y;cr[i].x = dr[i].x; cr[i].y = dr[i].y; }} double shortest(int s, int e){ double d; //d表示点对之间的距离 int listlen = 0; if (s == e) return MAX; //如果只有一个点 if (s + 1 == e) return dis(ar[s], ar[e]);//如果只有两个点 long i, j, mid = (s + e) >> 1; double curmin = min(shortest(s, mid), shortest(mid + 1, e)); listlen = 0; for (i = mid; i >= s && ar[mid + 1].x - ar[i].x <= curmin; i--)sr[listlen++] = i; for (i = mid + 1; i <= e && ar[i].x - ar[mid].x <= curmin; i++)sr[listlen++] = i; qsort(sr, listlen, sizeof(sr[0]), listcmp);//对y进行排序 for (i = 0; i < listlen; i++)for (j = i + 1; j < listlen && ar[sr[j]].y - ar[sr[i]].y <= curmin; j++) curmin = min(curmin, dis(ar[sr[i]], ar[sr[j]])); return curmin;}void myRun (int n) { time_t start, end; double distance; double sum = 0.0; cout << '分治法在' << n << '规模耗时结果如下：' << endl; for (int i = 0; i < 20; i++) {create(n);sort(ar, ar + n, cmpx); //按x对ar排序start = clock();double distance = shortest(0, n);end = clock();//if (i == 0) cout << '分治法在'<<n<<'规模时下计算结果如下：'<<endl<<'最短距离为：' << distance << endl<<'时间分别为:';cout << (double)(end - start) << 'ms ';sum += (double)(end - start); } cout <<endl<< '平均耗时: ' << sum / 20.0 <<'ms'<< endl<<endl;} int main(){myRun(100);myRun(1000);myRun(10000);myRun(20000);myRun(40000);myRun(60000);myRun(80000);myRun(100000);system('pause'); return 0;}
问题解答
回答1：不知道你的其他部分。
我在很多情况下都是不开方开判断大小或者是其他，只有需要结果的时候才开方。
这样判断大小的时候少一次开方，可以节省很多。
个人觉得很有可能是你其他部分造成了你这个结果。
