給定由 ( x i , y i , r i ) 描述的球體串列，表示球體i的中心在三維空間中的點 ( x i , y i , 0) 處，其半徑為r i , I想要計算所有z i其中z i = max { z | ( x i , y i , z ) 是任意球面上的一個點}。換句話說，z i是球心i上的最高點這是在任何領域。
我有兩個陣列
int **vs = (int **)malloc(num * sizeof(int *));
double **vh = (double **)malloc(num * sizeof(double *));
for (int i = 0; i < num; i ){
vs[i] = (int *)malloc(2 * sizeof(int)); // x,y
vh[i] = (double *)malloc(2 * sizeof(double)); r,z
}
目標是計算z每個點的最大值。x,y因此，我們應該檢查每個點上是否有更大的球體。最初我們看到vh[i][1]=vh[i][0]所有點，這意味著這z是r每個球體的。然后，我們檢查這些z值是否在更大的范圍內以最大化z值。
for (int i = 0; i < v; i ) {
double a = vh[i][0] * vh[i][0]; // power of the radius of sphere #1
for (int j = 0; j < v; j ) {
if (vh[i][0] > vh[j][1]) { // check only if r of sphere #1 is larger than the current z of #2
double b = a - (vs[j][0] - vs[i][0]) * (vs[j][0] - vs[i][0])
- (vs[j][1] - vs[i][1]) * (vs[j][1] - vs[i][1]);
// calculating the maximum z value of sphere #2 crossing sphere #1
// (r of sphere #1)**2 = (z of x_j,y_j)**2 (distance of two centers)**2
if (b > vh[j][1] * vh[j][1]) {
vh[j][1] = sqrt(b);// update the z value if it is larger than the current value
}
}
}
}
它作業得很好，但是當點數增加時嵌套回圈非常慢。我正在尋找一種方法來加快這個程序。
說明任務的插圖
uj5u.com熱心網友回復：
當你說
目標是計算每個點的最大 z。
我認為您的意思是，對于每個球體的中心 C，任何球體上z位于 C 正上方（沿 z 軸）的所有點之間的最大坐標。這基本上是一個 O(n 2 ) 問題——您無法阻止計算費用隨球體數量的平方而縮放。
但是您可以采取一些措施來降低縮放系數。以下是一些可能性：
使用真正的二維陣列（== 陣列陣列）而不是指標陣列。它更容易實作，記憶體效率更高，并且更適合參考的區域性：
int (*vs)[2] = malloc(num * sizeof(*vs)); double (*vh)[2] = malloc(num * sizeof(*h)); // no other allocations needed或者，它可能有助于使用結構陣列，每個球體一個，而不是兩個二維數字陣列。它肯定會讓你的代碼更清晰，但它也可能有助于通過改進參考的區域性來稍微提高速度：
struct sphere { int x, y; double r, z; }; struct sphere *spheres = malloc(num * sizeof(*spheres));至少在計算期間存盤
z2而不是。這將減少從 O(v 2z) 到 O(v)的昂貴sqrt呼叫的數量，假設您在最后進行單次傳遞以將所有結果轉換為s，它將為您節省 O(v 2 ) 乘法， 也。（如果您可以在沒有從z 2轉換為 z 的情況下逃脫，則更多。）z將每個值預初始化
vh[i][1]為球體 i 的半徑（或者如果您也在執行前一個選項，則為半徑的平方），并添加j != i到內回圈主體周圍的條件。按半徑按降序對球體進行排序可以幫助您
z更早地找到更大的臨時值，從而使內部回圈中的半徑測驗更有效地剔除不必要的計算。通過僅檢查每個不同的對一次，您可能會得到一些改進。也就是說，對于每個無序對
i,j，您只能計算一次中心間距離，根據相對半徑確定要檢查可能更新的高度，然后從那里開始。所涉及的額外邏輯可能會或可能不會通過減少其他計算來獲得回報。
此外，如果您對足夠大的輸入執行此操作，那么您可能能夠通過并行化計算來減少所消耗的時間。
請注意，順便說一句，此評論不正確：
// (r of sphere #1)**2 = (r of sphere #2)**2 (distance of two centers)**2
. However, it also not what you are relying upon. What you are relying upon is that if sphere 1 covers the center of sphere 2 at all, then its height, z, above the center of sphere 2 satisfies the relationship
r12 = z2 d1,22
. That is, where you wrote r of sphere #2 in the comment, you appear to have meant z.
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/438485.html
下一篇：獲取具有時間范圍的時間間隔