Я пытаюсь вычислить среднее значение средней разницы для набора данных.У меня есть две (предположительно эквивалентные) формулы, которые вычисляют это, одна из которых более эффективна (O ^ n), чем другая (O ^ n2).
Проблема в том, что, хотя неэффективная формула дает правильный результат, эффективная - нет.Просто взглянув на обе формулы, я понял, что они не эквивалентны, но списал их, потому что вывод был сделан статистом из научного журнала.Я предполагаю, что проблема в моем переводе.Может ли кто-нибудь помочь мне правильно перевести эффективную функцию?
Неэффективная формула: 
Неэффективный перевод формул (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):
Эффективный перевод производной формулы (Java):
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), при условии, что все ваши данные имеют значения, ограниченные относительно небольшим набором. Формула придерживается методологии первого метода и, следовательно, дает идентичныерезультаты к нему (в отличие от производной формулы).Если он соответствует вашему варианту использования, я предлагаю людям использовать его вместо производной эффективной формулы, особенно если последняя, по-видимому, дает отрицательные значения, когда 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)));
}