Hi math01-ga,
Beneath you'll find a simple java program illustrating both kinds of
cumulative sums. I'll make the code available for download as well, as
the layout might change when posting this message.
The program calculates the cumulative sum in both ways on a number
list of increasing length and writes out the time it took to calculate
the sum (in milliseconds). The numbers of each list are generated
randomly. Only the short list (of 10 numbers) is printed to the
console, as printing 1000's of numbers to the console would be
confusing. As you'll see this time increases rapidly when using the
slow method and remains very low when using the fast method.
This is caused by the fact that the first method contains a nested
for-loop. Now look at the inner loop of the first method. You'll see
that the inner loop is traversed n-1 times, n-2 times, n-3 times ...
all the way down to one time. Put all together that is O(n-1)+ O(n-2)
+ O(n-3) + ... + O(1). There are n-1 terms here, and each is no worse
than O(n), so clearly the total is no worse than O((n-1)*n) = O(nē),
but many of the terms are much smaller than n, so we should be more
careful. Now, the sum 1 + 2 + 3 + ... + n = n(n+1)/2 = O(nē). Note
that we are interested in O(n-1)+ O(n-2) + O(n-3) + ... + O(1) =
O((n-1)+ (n-2) + (n-3) + ... + (1)), which is just the same as the sum
of 1 through n backwards, except we leave off the biggest term n, so
O(n-1)+ O(n-2) + O(n-3) + ... + O(1) = O(nē - n) = O(nē).
The fast method does not use a nested loop and therefore executes in a
runtime of O(n).
You can compile the code from the command line using: "javac
CumulativeSum.java"
and execute the program using: "java CumulativeSum"
I assume you know how to compile and run the program, but if you run
into any problem, just let me know and I'll do my best to assist.
The program:
--------------------------------------------------
public class CumulativeSum {
public static void main(String[] args) {
System.out.println("CUMULATIVE SUM WITH METHOD 1:");
// the first parameter determines the length of the list
// the second parameter (true/false) indicates whether or not the
list of numbers should be printed
slowCumulativeSum(getRandomIntArray(10),true);
slowCumulativeSum(getRandomIntArray(10000),false);
slowCumulativeSum(getRandomIntArray(20000),false);
slowCumulativeSum(getRandomIntArray(30000),false);
slowCumulativeSum(getRandomIntArray(40000),false);
slowCumulativeSum(getRandomIntArray(50000),false);
System.out.println("CUMULATIVE SUM WITH METHOD 2:");
slowCumulativeSum(getRandomIntArray(10),true);
fastCumulativeSum(getRandomIntArray(10000),false);
fastCumulativeSum(getRandomIntArray(20000),false);
fastCumulativeSum(getRandomIntArray(30000),false);
fastCumulativeSum(getRandomIntArray(40000),false);
fastCumulativeSum(getRandomIntArray(50000),false);
fastCumulativeSum(getRandomIntArray(100000),false);
fastCumulativeSum(getRandomIntArray(1000000),false);
}
/**
* Calculates the cumulative sum of a list of integer numbers using
* the slow method
*
* @param input_list A list of numbers
* @param print true if the input and output lists should be printed
to the console
*/
private static void slowCumulativeSum(int[] input_list, boolean
print) {
System.out.println("calculating cumulative sum for input list
length "+input_list.length+")...");
if (print) printList(input_list);
int output_list[] = new int[input_list.length];
long startTime = System.currentTimeMillis();
for (int i = 0; i < input_list.length; i++)
for (int j = 0; j <= i; j++)
output_list[i] += input_list[j];
long endTime = System.currentTimeMillis();
if (print) printList(output_list);
System.out.println("runtime: "+(endTime-startTime)+"ms.");
}
/**
* Calculates the cumulative sum of a list of integer numbers using
* the fast method
*
* @param input_list A list of numbers
* @param print true if the input and output lists should be printed
to the console
*/
private static void fastCumulativeSum(int[] input_list, boolean
print) {
System.out.println("calculating cumulative sum for input list
length "+input_list.length+")...");
if (print) printList(input_list);
int output_list[] = new int[input_list.length];
long startTime = System.currentTimeMillis();
for (int i = 1; i < input_list.length; i++)
output_list[i] = output_list[i-1] + input_list[i];
long endTime = System.currentTimeMillis();
if (print) printList(output_list);
System.out.println("runtime: "+(endTime-startTime)+"ms.");
}
/**
* Returns a random integer array with elements in [0-9]
*
* @param length The length of the array
*/
private static int[] getRandomIntArray(int length) {
int[] list = new int[length];
for (int i=0;i<length;i++) list[i] = getRandomInt();
return list;
}
/**
* Returns a random integer in [0-9]
*/
private static int getRandomInt() {
return (int) (Math.random()*10);
}
/**
* Prints a list of numbers to the console
*/
private static void printList(int[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i]+" ");
System.out.println();
}
}
--------------------------------------------------
The output of the program on my PC:
CUMULATIVE SUM WITH METHOD 1:
calculating cumulative sum for input list length 10000)...
runtime: 625ms.
calculating cumulative sum for input list length 20000)...
runtime: 1890ms.
calculating cumulative sum for input list length 30000)...
runtime: 3516ms.
calculating cumulative sum for input list length 40000)...
runtime: 6000ms.
calculating cumulative sum for input list length 50000)...
runtime: 9562ms.
CUMULATIVE SUM WITH METHOD 2:
calculating cumulative sum for input list length 10000)...
runtime: 0ms.
calculating cumulative sum for input list length 20000)...
runtime: 0ms.
calculating cumulative sum for input list length 30000)...
runtime: 0ms.
calculating cumulative sum for input list length 40000)...
runtime: 0ms.
calculating cumulative sum for input list length 50000)...
runtime: 0ms.
calculating cumulative sum for input list length 100000)...
runtime: 2ms.
calculating cumulative sum for input list length 1000000)...
runtime: 62ms.
Depending on the speed of your processor, the times might differ
significantly, however it should still remain obvious that the second
method is much faster than the first. Feel free to experiment with the
lengths.
Hope this helps!
Kind regards,
rhansenne-ga. |
