I'm trying to devise a way to calculate the mean differences (the absolute average differences between any two values in a set), of sub-arrays (starting from arbitrary indices) in an int
array. I'll be placing the bounds of each subarray in to "buckets" of differing mean difference magnitudes.
The problem is, I can't find an efficient (better than \$O(n^3)\$) way of doing this. Would anyone mind helping me make the code more efficient (at least better than \$O(n^2)\$)?.
The calculations are performed server-side upon user request from my web-app. If making it more efficient isn't possible, would it be advisable to adopt a solution that doesn't involve modifying the computation, such as:
- Keep this inefficient implementation and include a disclaimer stating it may take some time to complete
- Transfer the calculations to several daemon threads which will perform the process on the entire user base and store the results in the database, which will be returned to the users (returned results may not be up-to-date)
I'm currently at a crossroads and am not sure which route I should take.
Pseudocode of main function:
/*The purpose of the main function is to store the mean differences of sub-arrays in a given array, making the sure the stored sub-arrays are as long as possible*/ for i in dataArray loop through all j (j starting from i + 1) in dataArray get mean difference of values in between indexes i and j get int value of mean difference (bucket) if bucket != (bucket of mean difference of values in between indexes i and j - 1), store i and j in bucket
Main function:
public static HashMap<Integer, Stack<HashMap<String, Integer>>> calculateMeanDifferences(ArrayList<Integer> dataArrayList)
{
//Each key maps to a stack which will hold HashMaps containing the bounding indices of subArrays which have mean differences that round to the key
HashMap<Integer, Stack<HashMap<String, Integer>>> meanDifferenceBucketHashMap = new HashMap<Integer, Stack<HashMap<String, Integer>>>();
long size = dataArrayList.size();
Integer previousMeanDifferenceBucket = null;
Integer currentMeanDifferenceBucket = null;
double currentMeanDifference = 0;
//Major loop which starts the mean difference calculations from every index
for(int i = 0; i < size; i++)
{
//Minor loop which calculates the mean differences for sub-arrays of increasing length starting from i.
for(int j = i + 2; j < size + 1; j++)
{
currentMeanDifference = calculateMeanDifference(new ArrayList(dataArrayList.subList(i, j)));
currentMeanDifferenceBucket = (int)Math.round(currentMeanDifference);
//Ensure longest possible sub-array is recorded (so, for all i and j, if both subList(i,j-1) and subList(i, j) are recorded, they will be in different buckets)
if((previousMeanDifferenceBucket != null && previousMeanDifferenceBucket != currentMeanDifferenceBucket) || j == size)
{
HashMap<String, Integer> previousSubArrayBoundsHashMap = new HashMap<String, Integer>();
previousSubArrayBoundsHashMap.put("start", i);
previousSubArrayBoundsHashMap.put("onePastEnd", j);
if(!meanDifferenceBucketHashMap.containsKey(previousMeanDifferenceBucket))
meanDifferenceBucketHashMap.put(previousMeanDifferenceBucket, new Stack<HashMap<String, Integer>>());
else
meanDifferenceBucketHashMap.get(previousMeanDifferenceBucket).push(previousSubArrayBoundsHashMap);
}
previousMeanDifferenceBucket = currentMeanDifferenceBucket;
}
previousMeanDifferenceBucket = currentMeanDifferenceBucket = null;
}
return meanDifferenceBucketHashMap;
}
Sub-function (not necessary to look over, just know it is \$O(n)\$ for my use case (all values guaranteed to be in the set [0,5])):
public static double calculateMeanDifference(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)));
}