我最近尝试使用 C++ 实现最近对算法，我的大部分代码都受到了我在 GeeksforGeeks 上发现的启发。但是，我似乎无法运行具有较大 n 值的代码。我之前尝试输入 5,000,000 作为 n 值，然后进程在几秒钟后终止，没有显示任何输出。我需要能够达到至少 n = 5,000,000。现在，我的程序似乎停留在 n = 100,000 左右。它确实可以生成直到 n = 250,000 的随机数，但它会在进行最接近的配对计算之前终止。
这是我的代码。我真的更喜欢使用数组来收集值，但如果不可能，请赐教（我应该使用向量还是其他任何东西）。
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <random>
using namespace std;
//declares a class for a point with coordinates (x and y)
class Point
{
public:
unsigned long int x,y;
};
class Result
{
public:
Point a,b;
long double d;
};
//utility void function to swap values in an array to assist with the sorting functions
void swaps(Point *a, Point *b)
{
Point temp;
temp.x = a->x;
temp.y = a->y;
a->x = b->x;
a->y = b->y;
b->x = temp.x;
b->y = temp.y;
}
unsigned long int partition (Point arr[], unsigned long int low, unsigned long int high)
{
unsigned long int pivot = arr[high].x; //set pivot as the x value of the last element in the array
unsigned long int i = (low - 1); //the index of the smaller element
for (unsigned long int j = low; j <= high - 1; j++)
//swap current element if it is smaller than pivot
if (arr[j].x < pivot)
{
i++; //increment index of smaller element
swaps(&arr[i], &arr[j]);
}
swaps(&arr[i + 1], &arr[high]);
return (i + 1);
}
//void function to sort the Point array P according to the x values of its elements
void xsort(Point arr[], unsigned long int low, unsigned long int high)
{
if (low < high)
{
unsigned long int pi = partition(arr, low, high);
xsort(arr, low, pi - 1);
xsort(arr, pi + 1, high);
}
}
//function to calculate distance between 2 points
long double dist(Point p1, Point p2)
{
return (sqrt((p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y)));
}
//brute force function to find the closest distance between points by one-to-one comparing
Result bruteForce(Point P[], unsigned long int n)
{
Result tempresult;
tempresult.d = dist(P[0], P[1]);
tempresult.a = P[0];
tempresult.b = P[1];
for (unsigned long int i=0; i<n; i++)
{
for (unsigned long int j=i+1; j<n; j++)
if (dist(P[i], P[j]) < tempresult.d)
{
tempresult.d = dist(P[i], P[j]);
tempresult.a = P[i];
tempresult.b = P[j];
}
};
return tempresult;
}
//function to return the minimum value between 2 values entered
long double min(long double v1, long double v2)
{
if (v1<=v2) return v1;
else return v2;
}
//function to calculate the minimum distance between points across midpoint borders
Result crossFunction(Point P[], unsigned long int n, Result tempresult)
{
for (unsigned long int i=0; i<n; ++i)
for (unsigned long int j = i+1; j < n && (P[j].x - P[i].x) < tempresult.d; j++)
if (dist(P[i],P[j]) < tempresult.d)
{
tempresult.d = dist(P[i], P[j]);
tempresult.a = P[i];
tempresult.b = P[j];
}
return tempresult;
}
//function that includes the critical code of divide-and-conquer to solve the problem
Result closestUtil(Point P[], unsigned long int n)
{
if (n<=3)
return bruteForce(P, n);
Result tempresult, crossresult, finalresult;
//determine the middle point of the array
unsigned long int mid = n/2;
Point midPoint = P[mid];
//breaks the array recursively until it reaches n<=3
Result half1 = closestUtil(P, mid);
Result half2 = closestUtil(P + mid, n - mid);
//compares the two closest distances found in both halves and find the minimum of both
tempresult.d = min(half1.d, half2.d);
if (tempresult.d == half1.d)
{
tempresult.a = half1.a;
tempresult.b = half1.b;
}
else
{
tempresult.a = half2.a;
tempresult.b = half2.b;
}
//creates an array to store all points closer to the midpoint than the current local closest value
Point cross[n];
unsigned long int j=0;
for (unsigned long int i=0; i<n-1; i++)
if (abs(dist(P[i], midPoint)) < tempresult.d)
{
cross[j] = P[i];
j++;
}
crossresult = crossFunction(cross, j, tempresult);
finalresult.d = min(tempresult.d, crossresult.d);
if (finalresult.d == tempresult.d)
{
finalresult.a = tempresult.a;
finalresult.b = tempresult.b;
}
else
{
finalresult.a = crossresult.a;
finalresult.b = crossresult.b;
}
return finalresult;
}
Result closestPair(Point P[], unsigned long int n)
{
xsort(P,0,n-1);
return closestUtil(P,n);
};
int main()
{
unsigned long int n, x, y;
cout << "Enter the number of points: "; cin >> n;
cout << "Enter grid size (x y): "; cin >> x >> y;
Point P[n];
Result closest;
srand((unsigned)time(NULL));
for(long int i=0; i<n; i++)
{
P[i].x=rand()%x+1;
P[i].y=rand()%y+1;
}
cout << "\nPOINT \t\t X \t Y " << endl << "----------------------------------" << endl;
for (unsigned long int i=0; i<n; i++)
cout << i+1 << "\t|\t" << P[i].x << "\t" << P[i].y << "\n";
closest = closestPair(P,n);
cout << endl << "The closest distance between points is " << closest.d << " and it is found "
<< "between point (" << closest.a.x << ", " << closest.a.y << ") and point (" << closest.b.x << ", "
<< closest.b.y << ").";
return 0;
}
更新：感谢您的建议！我修复了我的代码并使用了向量。它工作得很好。但是，当我尝试在大 n 值上使用大边框进行点随机化时，有时它们会显示非常不准确的结果。它只会计算点的 x 坐标之间的距离，而不是考虑 y 坐标。这是我修改后的代码。我想知道错误可能在哪里。提前致谢！
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
//declares a class for a point with coordinates (x and y)
struct Point
{
unsigned long int x,y;
};
class Result
{
public:
Point a,b;
long double d;
};
bool compareX(Point a, Point b)
{
return a.x < b.x;
}
//function to calculate distance between 2 points
long double dist(Point p1, Point p2)
{
return (sqrt((p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y)));
}
//brute force function to find the closest distance between points by one-to-one comparing
Result bruteForce(vector<Point> points, unsigned long int n)
{
Result tempresult;
tempresult.d = dist(points[0], points[1]);
tempresult.a = points[0];
tempresult.b = points[1];
for (unsigned long int i=0; i<n; i++)
{
for (unsigned long int j=i+1; j<n; j++)
if (dist(points[i], points[j]) < tempresult.d)
{
tempresult.d = dist(points[i], points[j]);
tempresult.a = points[i];
tempresult.b = points[j];
}
};
return tempresult;
}
//function to return the minimum value between 2 values entered
long double min(long double v1, long double v2)
{
if (v1<=v2) return v1;
else return v2;
}
//function to calculate the minimum distance between points across midpoint borders
Result crossFunction(vector<Point> cross, unsigned long int n, Result tempresult)
{
for (unsigned long int i=0; i<n; i++)
for (unsigned long int j = i+1; j < n && (cross[j].x - cross[i].x) < tempresult.d; j++)
if (dist(cross[i],cross[j]) < tempresult.d)
{
tempresult.d = dist(cross[i], cross[j]);
tempresult.a = cross[i];
tempresult.b = cross[j];
}
return tempresult;
}
//function that includes the critical code of divide-and-conquer to solve the problem
Result closestUtil(vector<Point> points, unsigned long int n)
{
if (n<=3)
return bruteForce(points, n);
Result tempresult, crossresult, finalresult;
//determine the middle point of the array
unsigned long int mid = n/2;
Point midPoint = points[mid];
vector<Point> points_half1(points.cbegin(), points.cbegin() + mid);
vector<Point> points_half2(points.cbegin() + mid, points.cend());
//breaks the array recursively until it reaches n<=3
Result half1 = closestUtil(points_half1, mid);
Result half2 = closestUtil(points_half2, n - mid);
//compares the two closest distances found in both halves and find the minimum of both
tempresult.d = min(half1.d, half2.d);
if (tempresult.d == half1.d)
{
tempresult.a = half1.a;
tempresult.b = half1.b;
}
else
{
tempresult.a = half2.a;
tempresult.b = half2.b;
}
//creates an array to store all points closer to the midpoint than the current local closest value
vector<Point> cross;
for (int i=0; i<n; i++)
if (abs(points[i].x - midPoint.x) < tempresult.d) cross.push_back(points[i]);
crossresult = crossFunction(cross, cross.size(), tempresult);
finalresult.d = min(tempresult.d, crossresult.d);
if (finalresult.d == tempresult.d)
{
finalresult.a = tempresult.a;
finalresult.b = tempresult.b;
}
else
{
finalresult.a = crossresult.a;
finalresult.b = crossresult.b;
}
return finalresult;
}
Result closestPair(vector<Point>& points)
{
sort(points.begin(), points.end(), compareX);
return closestUtil(points,int(points.size()));
};
int main()
{
unsigned long int n, x, y;
cout << "Enter the number of points: "; cin >> n;
cout << "Enter grid size (x y): "; cin >> x >> y;
if ((n > 1) && (x >= 0) && (y >= 0))
{
vector<Point> points;
Result closest;
random_device rd;
default_random_engine generator(rd());
uniform_int_distribution<long long unsigned> distributeX(0,x);
uniform_int_distribution<long long unsigned> distributeY(0,y);
for(long int i=0; i<n; i++)
{
Point p;
p.x = distributeX(generator);
p.y = distributeY(generator);
points.push_back(p);
}
closest = closestPair(points);
cout << endl << "The closest distance between points is " << closest.d << " and it is found "
<< "between point (" << closest.a.x << ", " << closest.a.y << ") and point (" << closest.b.x << ", "
<< closest.b.y << ").";
}
else cout << "Invalid value(s) entered." << endl;
return 0;
}