gyakoo blog

Complexity Order I mean. Algorithmic is an useful tool which every programmer needs to know. As you already know, you could find/do a very very fast routine to compare two strings, by using new SIMD instructions built in the SS4, as the PCMPEQQ for example, and reordering instructions to minimize cache fails and take advantage of out of order micro execution. But if you're applying a direct algorithm to traverse words or a direct structure to store them, there is nothing you can do when you get an asynthotic input. It is the beauty about algorithmic, an university's subject that all the software engineers should know, and apply it in their daily technology decisions (whenever they can), because the system's behavior with large input matters and can makes the difference.

I remember, when I was studying at UCA, we did practices about algorithmic and complexity order theory by measuring different algorithms times to the same problem. We sampled the time that an algorithm takes for different input sizes, so you're sampling the complexity order curve/function and then by comparing all the algorithms-times, you can see how they behave asynthotically, in a graphic manner.

I've been using this technique since then, when I need to test different approaches to same problem, or when I need to empirically demonstrate a data structure, for example. In another post in this blog I talked about a special radix tree to store IP numbers, demonstrating you'll get a constant complexity order O(k) when search for an IP, independently you store all internet IPs (another thing is the complexity order in space). This means that you'll perform same number of instructions to search any number.

So you have, O(1) < O(logn) < O(n) < O(n·logn) < O(n^2) < O(n^a) < O(a^n) < O(n!), being O(1) the best you can get in time and space. Related with this you have the NP complete problems.

Sometimes when trying to get a best time complexity, probably you'll get worse the spatial one, and vice versa. Another important note about measuring times is the time precision. Although you use a high performance counter, you cannot measure how much time takes two std vector's inserts, because current microprocessors are very fast. You should use a big N input, repeated M times, because memory never is enough (you can't insert 1·10^12 words in a vector, at least you shouldn't), and then divide the time to compute the average time. Selection of N and M is important. Also, you need to know that another daemons or processes are continuously interrupting the algorithm, maybe the compiler can generate an optimize version of your algorithm (only improving the multiplicative constant). All these variables can corrupt the times you get, so the conclusion is do not use the times as it, but the graphical comparisons between algorithms' times, or in other words, you need to extract all the multiplicative constants and think only in terms of sampled curves' behavior.

In the code below you see a snippet to measure a std list insert varying N.

unsigned long step = (MAX-MIN)/N_POINTS;
// Varying our input N
for ( unsigned long N = MIN; N < MAX; N+=step )
{   
double time = 0.0;
// Repeating M times
for ( unsigned long m = 0; m < M; ++m )
{
  Clock cl;
  cl.Start();
  // Algorithm test comes here.
  // Trying to insert N numbers in a stl list
  std::list<int> lis;
    for ( unsigned long i = 0; i < N; ++i )
    {
        lis.push_back( i );
    }
  time += cl.Stop();
}

printf ( "%lu\t%0.10lf\n", N, time/(N*M) );
}

This code will print an output like follow:

99999 0.0000001016 
6759999 0.0000001023 
13419999 0.0000001042 
20079999 0.0000001021 
26739999 0.0000001028 
33399999 0.0000001037 
40059999 0.0000001016 
46719999 0.0000001051 
53379999 0.0000001017 
60039999 0.0000001020 
66699999 0.0000001012 
73359999 0.0000001021 
80019999 0.0000001005 
86679999 0.0000001011 
93339999 0.000000101

This data can be obtained for several algorithms. All those data then can be graphically represented using a plot program, like gnuplot for example.

Follow are curves for insert algorithms in <vector>, <list> and <map> Before you look through the image below, it would be interesting you know what are the complexity order for insertions in these containers. In this page you can see all O for stl containers. O(1) for vector and list. And * for map. Well, the time complexity requirements imposed by the standard for each map operation suggest a balanced binary search tree mostly. Let's see the results:



Wow!, it is interesting that the vector (red line) and the list (blue line) are constant ( O(1) ). In other words, doesn't matter how N increase, always you'll get a constant time. And the map (green line) follows a logarithmic curve ( O(logn) ). Obviously a linear interpolation between measuring points are used.

As you can view, vector has O(1) in push_back operations. Wait a minute! When a vector increases beyond its capacity, a memory resize is needed, and a copy for all elements is performed. So, why is it O(1)? It's a O(n) just because asynthotically you'll need to make N copies... Well, there exists a thing called amortized analysis to deal with it. In fact, in the wikipage about amortized analysis, the example used to describe it, is the array push back operation.

Also you can get from graphic that vector is faster than list when inserting elements, due to multiplicative constant, being smaller in vector structure. But remember, with this implementation and in the CPU I used. This is can be because in list you need to make pointers operations when a new node is added, in vector you only need access to last available memory slot to put the element. Also in list you need to create every new node (memory alloc operation).

Another comparison graphic below, measuring find operations in the three same containers.


But, what happened to green line (map's find operation)? This is a common issue you'll get when comparing very different measuring scales. Map's searches are so fast, comparing with the vector or list ones. So, you cannot see the green line because is very near to X axis, in other words, with low times. You need to change scale, but anyway you can see here that vector and list find operations are linear ( O(n) ), with different constants (again vector has lower constant). To view if map searching operation behaves like a logarithmic one, we represent independently the third curve.


And finally, it behaves like a logarithmic curve!.