我試圖計算一組數據的平均差異平均值。我有兩個(據推測等價)公式來計算這一點,其中一個比另一個(O^n2)更高效(O^n)。將等效公式轉換爲代碼不會給出正確的結果
問題是,雖然效率低的公式給出了正確的輸出,但高效的公式並沒有。只要看兩個公式,我都有一種預感,他們並不相同,但是把它寫出來是因爲這個推導是由一個科學雜誌上的一個靜態學者所做出的。所以我假設問題是我的翻譯。任何人都可以幫助我正確地翻譯高效函數嗎?
低效公式:
低效公式翻譯(JAVA):
public static double calculateMeanDifference(ArrayList<Integer> valuesArrayList)
{
int valuesArrayListSize = valuesArrayList.size();
int sum = 0;
for(int i = 0; i < valuesArrayListSize; i++)
{
for(int j = 0; j < valuesArrayListSize; j++)
sum += (i != j ? Math.abs(valuesArrayList.get(i) - valuesArrayList.get(j)) : 0);
}
return new Double((sum * 1.0)/ (valuesArrayListSize * (valuesArrayListSize - 1)));
}
高效的推導公式:
其中(對不起,不知道如何在這裏使用MATHML) :
x(subscri PT 1)=第i個數據的order statistic設置
X(巴)=所述數據的平均值設置
高效推導公式翻譯(爪哇):
public static double calculateMean(ArrayList<Integer> valuesArrayList)
{
double sum = 0;
int valuesArrayListSize = valuesArrayList.size();
for(int i = 0; i < valuesArrayListSize; i++)
sum += valuesArrayList.get(i);
return sum/(valuesArrayListSize * 1.0);
}
public static double calculateMeanDifference(ArrayList<Integer> valuesArrayList)
{
double sum = 0;
double mean = calculateMean(valuesArrayList);
int size = valuesArrayList.size();
double rightHandTerm = mean * size * (size + 1);
double denominator = (size * (size - 1))/2.0;
Collections.sort(valuesArrayList);
for(int i = 0; i < size; i++)
sum += (i * valuesArrayList.get(i) - rightHandTerm);
double meanDifference = (2 * sum)/denominator;
return meanDifference;
}
我數據集由一組整數組成,每個整數都有一個由集[0,5]界定的值。
隨機生成這樣的集合並在它們上使用這兩個函數給出了不同的結果。效率低下的人似乎是與測量結果一致的結果:該組中任何兩個值之間的絕對平均差異。
誰能告訴我我的翻譯有什麼問題嗎?
編輯:我創建了一個更簡單的實現中的O(N)中提供的所有數據具有限於相對小set.The式粘在第一方法的方法值,從而,給出相同的結果,以它(不像派生的公式)。如果它符合你的用例,我建議人們用這個來代替派生的高效公式,尤其是當N很小時,後者似乎給出了負值。
高效,無衍生翻譯(JAVA):
public static double calculateMeanDifference3(ArrayList<Integer> valuesArrayList)
{
HashMap<Integer, Double> valueCountsHashMap = new HashMap<Integer, Double>();
double size = valuesArrayList.size();
for(int i = 0; i < size; i++)
{
int currentValue = valuesArrayList.get(i);
if(!valueCountsHashMap.containsKey(currentValue))
valueCountsHashMap.put(currentValue, new Double(1));
else
valueCountsHashMap.put(currentValue, valueCountsHashMap.get(currentValue)+ 1);
}
double sum = 0;
for(Map.Entry<Integer, Double> valueCountKeyValuePair : valueCountsHashMap.entrySet())
{
int currentValue = valueCountKeyValuePair.getKey();
Double currentCount = valueCountKeyValuePair.getValue();
for(Map.Entry<Integer, Double> valueCountKeyValuePair1 : valueCountsHashMap.entrySet())
{
int loopValue = valueCountKeyValuePair1.getKey();
Double loopCount = valueCountKeyValuePair1.getValue();
sum += (currentValue != loopValue ? Math.abs(currentValue - loopValue) * loopCount * currentCount : 0);
}
}
return new Double(sum/ (size * (size - 1)));
}
謝謝!我感到非常愚蠢。我實際上試着按照你提出的方式來擺弄順序,但它仍然產生了古怪的結果。然而,它現在可以工作! – Kevin
順便說一下,您的低效率公式的實現效率要低於它的效率,因爲'iArrayList.get(i) - valuesArrayList.get(j)'將在'i == j'時爲0,所以需要條件。 – MRAB
@MRAB:不太清楚你在做什麼。有一個條件表達式測試圍繞該語句 – Kevin