的Java：距離度量算法設計

我試圖找出在Java中，以下問題（雖然它可以在幾乎做任何其他語言）：的Java：距離度量算法設計

我給整數值的兩個數組，xs和ys ，代表x軸上的數據點。它們的長度可能不完全相同，但都是> 0，並且它們不需要排序。我想要計算的是兩個數據點之間的最小距離度量。我的意思是，對於每個x我找到ys集合中最接近的y並計算距離，例如(x-y)^2。例如：

xs = [1,5] 
ys = [10,4,2]

應該返回（1-2）^ 2 +（5-4）^ 2 +（5-10）^ 2

距離度量並不重要，它的算法我我正在考慮將這兩個數組中的數組和排序索引排序，以便實現比bruteforce更好的效果（對於x中的每個元素，掃描ys中的所有元素以找到最小值），這是O(len1 * len2)。

這是我自己的問題，我正在努力，而不是一個家庭作業問題。所有的提示將不勝感激。

來源

2012-06-11 Bober02

在你的例子中，它實際上看起來好像每個'y'你都找到最接近的'x' - 你可能意味着對於更大集合中的每個元素，你可以找到更小集合中最接近的元素，期望在距離計算中存在與更大集合中的元素一樣多的項。 –

是的，它是較大的一套我比較小的一套。任何想法如何使它比O（len1 * len2）更好？ – Bober02

我假設HighPerformanceMark（對你的問題的第一條評論）是正確的，而你實際上採用了更大的陣列，爲每個元素找到最小的陣列中最接近的一個，並在這些距離上總結一些f（dist）。

我建議你的方法：

Sort both arrays 
indexSmall=0 

// sum up 
for all elements e in bigArray { 
    // increase index as long as we get "closer" 
    while (dist(e,smallArray(indexSmall)) > dist(e,smallArray(indexSmall+1)) { 
    indexSmall++ 
    } 
    sum += f(dist(e,smallArray(indexSmall))); 
}

這是O(max(len1,len2)*log(max(len1,len2)))的排序。其餘與較大陣列長度成線性關係。現在dist(x,y)就像abs(x-y)和f(d)=d^2或者任何你想要的東西。

來源

2012-06-11 13:48:29 brimborium

您需要確保'indexSmall + 1'不會過度索引'smallArray' – Attila

當然，這只是僞代碼......但這對於實現者來說是一個有用的提示...;） – brimborium

你提出的想法聽起來不錯。您可以在O（n logn）時間對列表進行排序。然後，您可以使用另一個滑動索引對較長的列表執行一次迭代，以找到「對」。當你通過更長的列表進行搜索時，你將永遠不必在另一個上退路。所以現在你的整個算法是O（n logn + n）= O（n logn）。

來源

2012-06-11 13:31:52 jeff

您的方法非常好，並且具有時間複雜性。

如果陣列具有不同的長度，另一種方法是：較短的陣列

排序;
從開始到結束遍歷較長的數組，使用二分查找找到排序後的短陣列中最近的項目。

這有O((n1+n2)*log(n1))時間複雜度，其中n1是較短數組的長度。

來源

2012-06-11 13:37:09 NPE

的Java：距離度量算法設計

回答

相關問題