Android: benchmarking two algorithms

Question

I have implemented two algorithm for the same problem and want to find out, which is the best in a professional way.

The basis idea was:

final static int LOOP_COUNT = 500;
long totaTime = 0;

worm-up();
for(int i =0, i<LOOP_COUNT, i++)
{
    long startTime = System.currentTimeMillis();
    myMethod();
    long endTime= System.currentTimeMillis();
    totalTime += endTime - startTime;
 }

 return totalTime / LOOP_COUNT;

And do that for both Algorithm.

But:

how can I achieve, that the android System does not do any system calculations in the background and skew up the data
ist there a way i can also compare the used memory, both methods need?

score 1 · Answer 1 · answered Oct 30 '12 at 18:16

If you want professional statistical and relevant results and you want to minimize the influence of Android background processes, you will need to run your algorithm a number of times and compare the averages. In that way, due the the law of large numbers, your results will be correct.

How much times depends on the standard deviation of the execution time and how certain you want to be. If you're familiar with some basic statistic knowledge, you can determine your sample size with some basic formulas and you can for example run a t-test if your sample distribution is normally distributed to compare the averages of both algorithms. This automatically incorporates the fact that you want to minimize the influence of background processes. They will appear randomly so after a number of iterations, the influence of Android will be cancelled out.

Also take a look at the garbage collector, if you have a lot of object creation during the execution of your algorithm, it will affect your results but it should, as it will also affect the real world usage of the algorithm.

score 0 · Answer 2 · answered Oct 30 '12 at 18:19

0

You could try to analyze your code and find the time complexity. If you have a nested loop:

for(int i = 0; i< max; i++){
  for(int j = 0; j< max; j++){
      c = i + j;
   }
 }

This would have the time complexity O(n^2). The space complexity is O(1)

Another example is this:

for(int i = 0; i< max; i++){
   list[i] = "hello";
}

for(int j = 0; j< max; j++){
   list2[j] = "hello";
}

This would have the time complexity of O(2n) which is the same as O(n), and space complexity of O(2n) which is O(n).

The latter have a better runtime but uses more memory.

answered Oct 30 '12 at 18:19

rtc11

747
8
23

I have allready analysied the time complexity and now I want to test it on a real device to confirm my own choice. – user1786426 Oct 30 '12 at 18:31
Take a look at this: http://stackoverflow.com/questions/1957135/how-to-test-the-performance-of-an-android-application – rtc11 Oct 30 '12 at 18:40
I think the tool ist rather for finding bottlenecks than for benchmarking – user1786426 Oct 30 '12 at 22:18

score 0 · Answer 3 · answered Dec 13 '22 at 10:42

0

The recommended approach to measure specific inner loop performance is the Jetpack Microbenchmark library. You can find code samples on GitHub.

answered Dec 13 '22 at 10:42

Ben Weiss

17,182
6
67
87

Android: benchmarking two algorithms

3 Answers3