Java/Timing
From charlesreid1
If you want an extremely detailed picture of how much time you're spending in the various parts of your code, you can use a profiler: see Java/Profiling
Basic Timing in Java: Builtin Methods
If you just want to see how much time a piece of code takes to execute, you can use Java's built in time functionality:
long start = System.nanoTime();
doStuff();
long end = System.nanoTime();
long duration = end - start;
System.out.printf("Elapsed time: %03f s\n", duration/1E9);
Timing Snippets of Code
Can make a Stopwatch class that does the following:
- Constructor creates a new "start" variable - the stopwatch class measures time starting at its own creation
- Can call elapsed() method to get elapsed seconds
Via http://introcs.cs.princeton.edu/java/32class/Stopwatch.java.html
public class Stopwatch {
public Stopwatch() {
this.start = System.currentTimeMillis();
}
public double elapsed() {
this.end = System.currentTimeMillis();
return (end-start)/1000.0;
}
}
Comparing Hombrew Data Containers to Java Collections API
In the Java repository (link) in the lists/linked-lists folder (link), there is a timing script (link) that demonstrates a simple comparison of the built-in linked list type to a trimmed down generic TLinkedList type (link).
Code
The following code uses the TLinkedList class and the LinkedList class from the Java Collections API, so have those both ready and/or imported.
import java.util.LinkedList;
import java.util.Random;
/** Timing class: measure big-O complexity and runtime of data structures.
*
* Compare algorithms, test structures, and verify expected big-O behavior.
*
* This program is intended to be run on the command line like so:
*
* java Timing > output.txt
*
*/
public class Timing {
// Tests
public static void main(String[] args) {
linked_list_add_test();
linked_list_add_remove_test();
}
/** Compare the add and remove method - adding and removing from list.
*
* NOTE: If this is not constant, then add is not O(1) amortized,
* and there is something wrong with your implementation.
* */
public static void linked_list_add_remove_test() {
StringBuffer sb = new StringBuffer();
sb.append("N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k Mine (us) \n");
int ntrials = 1000;
Random r;
// Loop over values of N
for(int N = 1024; N <= 5e5; N*=2) {
sb.append( String.format("%d, ",N) );
// builtin linked list:
//
// b prefix is for built-in datatype
Tim btim = new Tim();
// Trials counter is always
// K for Kafka
r = new Random(100);
for(int k = 0; k<ntrials; k++) {
LinkedList<Integer> blist = new LinkedList<Integer>();
for(int i=0; i<N; i++) {
// 75% of the time, we add something. 25% of the time, we remove something.
boolean addSomething = r.nextBoolean();
if(addSomething) {
blist.add(0,r.nextInt(100));
} else {
if(!blist.isEmpty()) {
blist.remove(0);
}
}
}
}
double btime_total = btim.elapsedms();
// my little linked list:
//
// m prefix is for mine
Tim mtim = new Tim();
// Trials counter is k
r = new Random(100);
for(int k=0; k<ntrials; k++) {
TLinkedList<Integer> mylist = new TLinkedList<Integer>();
for(int i=0; i<N; i++) {
// 75% of the time, we add something. 25% of the time, we remove something.
boolean addSomething = r.nextBoolean();
if(addSomething) {
mylist.addFirst(r.nextInt(100));
} else {
if(!mylist.isEmpty()) {
mylist.removeFirst();
}
}
}
}
double mtime_total = mtim.elapsedms();
// print amortized cost per 1000 operations, times 1000 ms -> us
sb.append( String.format("%.3f, ", btime_total/N*1000) );
sb.append( String.format("%.3f ", mtime_total/N*1000) );
sb.append("\n");
}
System.out.println(sb.toString());
}
/** Compare the add method - appending to the rear of a list.
*
* Compares builtin LinkedList type with self-authored TLinkedList class.
*
* NOTE: If this is not constant, then add is not O(1) amortized,
* and there is something wrong with your implementation.
* */
public static void linked_list_add_test() {
StringBuffer sb = new StringBuffer();
sb.append("N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k Mine (us) \n");
int ntrials = 1000;
// Loop over some values of N,
// print the total cost,
// print the cost per add operation
for(int N = 1024; N < 5e5; N *= 2) {
sb.append( String.format("%d, ", N) );
// builtin linked list:
//
// b prefix is for built-in datatype
Tim btim = new Tim();
// Trials counter is always
// K for Kafka
for(int k = 0; k<ntrials; k++) {
LinkedList<Integer> blist = new LinkedList<Integer>();
for(int i=0; i<N; i++) {
blist.add(i*i);
}
}
double btime_total = btim.elapsedms();
// my little linked list:
//
// m prefix is for mine
Tim mtim = new Tim();
// Trials counter is k
for(int k=0; k<ntrials; k++) {
TLinkedList<Integer> mylist = new TLinkedList<Integer>();
for(int i=0; i<N; i++) {
mylist.addLast(i*i);
}
}
double mtime_total = mtim.elapsedms();
// print cost per 1000 add operations us, times 100 ms -> us
sb.append( String.format("%.3f, ", btime_total/N*1000) );
sb.append( String.format("%.3f", mtime_total/N*1000) );
sb.append("\n");
}
System.out.println(sb.toString());
}
}
Output
N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k Mine (us) 1024, 31.250, 18.555 2048, 15.137, 20.508 4096, 17.822, 8.301 8192, 17.944, 8.301 16384, 14.099, 12.085 32768, 10.742, 7.965 65536, 10.300, 7.248 131072, 10.597, 7.721 262144, 11.223, 9.842 N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k Mine (us) 1024, 53.711, 41.992 2048, 39.551, 19.043 4096, 23.438, 24.658 8192, 22.949, 18.677 16384, 22.949, 19.165 32768, 22.675, 20.172 65536, 23.087, 20.065 131072, 23.651, 19.623 262144, 23.518, 19.264