Critticall: Example

Example

Here we have the so called next permutation algorithm,implemented in the Critticall's C language:

Reference: E.W.Dijkstra, A Discipline of Programming, Prentice-Hall, 1976



$DECLAREINT i i1 one element1 size j ii element2 i2

$DIMENSION small[6] test[6] 

$MINIMIZE LINES 40 
$WEIGHTS COMMANDS=0 LINES=1  
// A message to Critticall, that only lines count. 
// That this source should be minimized for lines.

$RETVAR small[]
// Must include this file here before any optimization can take place!!! 



one=1;
i=size-one;
ii=i-one;
element1=small[ii];
element2=small[i];
while (element1 >= element2) { 
      i--;
      ii=i-one;
      element1=small[ii];
      element2=small[i];
}
j=size;
ii=j-one;
element1=small[ii];
ii=i-one;
element2=small[ii];
while (element1 <= element2) { 
      j--;
      ii=j-one;
      element1=small[ii];
      ii=i-one;
      element2=small[ii];
}
i1=i-one;
element1=small[i1];
i2=j-one;
element2=small[i2];
small[i1] = element2;
small[i2] = element1;
i++;
j=size;
while (i < j) {
      i1=i-one;
      element1=small[i1];
      i2=j-one;
      element2=small[i2];
      small[i1] = element2;
      small[i2] = element1;
      i++;
      j--;
}

From 41 lines at the beginning, we have something less then 2/3 of that number bellow. And it's already faster. Now we are going to subject the result to the default Critticall's optimization. Regardless of how many lines, but as less instructions as possible.



// The algorithm has been enhanced for 36.5854%


$DECLAREINT one i size element1 j i2 critticall3 


$DIMENSION small[6] test[6]

$MINIMIZE LINES 41
$RETVAR small[] 
// Must include this file here before any optimization can take place!!! 


$BES
i=size;
while (element1>=critticall3) {
    i+=-1;
    one=1;
    critticall3=small[i];
    i2=i-one;
    element1=small[i2];
    j=size;
}
while (i<j) {
    while (element1<=critticall3) {
        critticall3=small[i2];
        size+=-1;
        element1=small[size];
    }
    small[i2]=element1;
    small[size]=critticall3;
    size=i;
    i2=j-one;
    critticall3=small[i2];
    j+=-1;
    element1=small[size];
    i+=1;
}
small[size]=critticall3;
small[i2]=element1;
$EES

And we have got this. An algorithm which doesn't swap like the original one does. Yet it works perfectly, has less lines and it is on average 1/3 faster, than the original one.



// The algorithm has been enhanced for 35.7447%


$DECLAREINT size critticall3 i2 j critticall1 critticall4 


$DIMENSION small[6] test[6]

$MINIMIZE LINES 41
$RETVAR small[] 
// Must include this file here before any optimization can take place!!! 


// int small[6]; int size=0;int critticall3=0;int i2=0;int j=0;
// int critticall1=0;int critticall4=0;


$BES

size+=-1;
critticall3=small[size];
i2=size;
i2+=-1;


critticall4=size;
critticall1=small[i2];
while (critticall1>critticall3) {
    critticall3=critticall1;
    j=size;
    i2+=-1;
    critticall1=small[i2];
    critticall4+=-1;
}
critticall3=critticall1;
critticall1=small[size];
while (critticall4<j) {
    while (critticall1<critticall3) {
        size+=-1;
        critticall1=small[size];
    }
    if (size<j) {
        small[size]=critticall3;
        critticall3=small[j];
    }
    size=critticall4;
    small[i2]=critticall1;
    critticall1=small[size];
    i2=j;
    critticall4+=1;
    j+=-1;
}
small[size]=critticall3;
small[i2]=critticall1;
$EES

We could go directly from the first example, without minimizing the number lines first, but we could go through more stages also. One should always remember, that birds feathers first evolved as a protection against cold, later were used as a flying codevice. It often pays, to go through seemingly unrelated stages.

Now we may wonder, what Dr. Dijkstra would say!

            Dijkstra 1976:               Critticall 2004:

            0 5 4 3 2 1                  0 5 4 3 2 1
            1 5 4 3 2 1                  1 5 4 3 2 1
            1 5 4 3 2 0
            1 0 4 3 2 0                  1 0 4 3 2 1
            1 0 4 3 2 5                  1 0 4 3 2 5
            1 0 2 3 2 5                  1 0 4 3 4 5
            1 0 2 3 4 5                  1 0 2 3 4 5