同等の数式をコードに変換すると正しい結果が得られません

Question

データの平均の平均を計算しようとしています。私はこれを計算する2つの（おそらく同等の）数式を持っていますが、一方はもう一方（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

  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; 
  } 
  

  マイ：PTⅰ）データのorder statisticが

• X（バー）を設定し、i番目のデータの平均が

効率的な導出式変換（Javaの）設定= =データセットは、集合[0,5]で囲まれた値をそれぞれ有する整数の集合からなる。

このようなセットを無作為に生成し、それらの2つの関数を使用すると、異なる結果が得られます。非効率的なのは、測定されているものと一致する結果を生むものであると思われます。これは、セット内の任意の2つの値の絶対平均差です。

私の翻訳で何が問題なのか教えていただけますか？

EDIT： IはO（N）は、すべてのデータは、第一の方法の方法論に比較的小さなset.The式スティックに限定された値を有し、従って、同じ結果を与える提供される単純な実装を作成それ（派生した式とは異なります）。あなたのユースケースに合っていれば、特にNが小さいときに後者が負の値を与えるように見えるので、効率的な式の代わりにこれを使用することをお勧めします。

効率的、非派生翻訳（ジャワ）：

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))); 
} 

Answer 1

sum += (i * valuesArrayList.get(i) - rightHandTerm);のあなたの解釈が間違っている、それはsum += i * valuesArrayList.get(i);する必要があり、その後、あなたのfor、double meanDifference = ((2 * sum) - rightHandTerm)/denominator;

後の両方の式はほぼ同じ値で得しかし、それらは等しくはありません。それでも、これはあなたを少し助けるはずです。

Answer 2

各繰り返しでrightHandTermを減算すると、Nに掛けられます。

ノミネータのビッグシグマは、右手の言葉ではなく、（i x_i）にしか触れません。

もう1つのメモ：mean * size == sum。あなたはNで合計を除算する必要はありませんし、それを後で再計算する必要はありません。