From: Alexis Reigel <mail@...>
Date: 2006-02-24T07:02:36+09:00
Subject: Huge performance gap

--------------040509020705090708050004
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Hi all

I've ported the following c++ code to ruby. It is a recursive
(backtracking) sudoku-solving algorithm. Well, I was rather surprised by
the execution time I got:

c++ code:   0.33 seconds
ruby code: 27.65 seconds

The implementation should do the same, at least they run through the
method/function "next_state"/"nextone" both 127989 times.

Now how can it be that the ruby code is so awfully slow?
Is that normal for ruby?
Or is my implementation so horribly bad?
I am aware that the non-native and object-oriented ruby code won't be as
fast as the c++ one, but I didn't expect such a gap.


Thanks for comments.

Alexis.


--------------040509020705090708050004
Content-Type: application/x-ruby;
 name="sudoku-solver.rb"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="sudoku-solver.rb"

PWJlZ2luCiAgcnVieSBzb2x2ZXIKPWVuZAoKJGNvdW50ID0gMAoKZGVmIHZhbGlkPyhzdGF0
ZSwgeCwgeSkKICAjIGNoZWNrIGluIGNvbCBhbmQgcm93CiAgMC51cHRvKDgpIGRvIHxpfAog
ICAgcmV0dXJuIGZhbHNlIGlmIGkgIT0geSBhbmQgc3RhdGVbeF1baV0gPT0gc3RhdGVbeF1b
eV0KICAgIHJldHVybiBmYWxzZSBpZiBpICE9IHggYW5kIHN0YXRlW2ldW3ldID09IHN0YXRl
W3hdW3ldCiAgZW5kCgogICMgY2hlY2sgaW4gYm94CiAgeF9mcm9tID0gKHggLyAzKSAqIDMK
ICB5X2Zyb20gPSAoeSAvIDMpICogMwogIHhfZnJvbS51cHRvKHhfZnJvbSArIDIpIGRvIHx4
eHwKICAgIHlfZnJvbS51cHRvKHlfZnJvbSArIDIpIGRvIHx5eXwKICAgICAgcmV0dXJuIGZh
bHNlIGlmICh4eCAhPSB4IG9yIHl5ICE9IHkpIGFuZCBzdGF0ZVt4eF1beXldID09IHN0YXRl
W3hdW3ldCiAgICBlbmQKICBlbmQKCiAgdHJ1ZQplbmQKCgoKZGVmIG5leHRfc3RhdGUoc3Rh
dGUsIHgsIHkpCiAgJGNvdW50ID0gJGNvdW50ICsgMQogIHkgPSAwIGFuZCB4ID0geCArIDEg
aWYgeSA9PSA5CiAgcmV0dXJuIHRydWUgaWYgeCA9PSA5CgogIHVubGVzcyBzdGF0ZVt4XVt5
XS56ZXJvPwogICAgcmV0dXJuIGZhbHNlIHVubGVzcyB2YWxpZD8oc3RhdGUsIHgsIHkpCiAg
ICByZXR1cm4gbmV4dF9zdGF0ZShzdGF0ZSwgeCwgeSArIDEpCiAgZWxzZQogICAgMS51cHRv
KDkpIGRvIHxpfCAgCiAgICBzdGF0ZVt4XVt5XSA9IGkKICAgICAgcmV0dXJuIHRydWUgaWYg
dmFsaWQ/KHN0YXRlLCB4LCB5KSBhbmQgbmV4dF9zdGF0ZShzdGF0ZSwgeCwgeSArIDEpCiAg
ICBlbmQKICBlbmQKICAKICBzdGF0ZVt4XVt5XSA9IDAKICBmYWxzZQplbmQKCgojIyBNQUlO
ICMjCgpzdGFydCA9ClsKICBbIDAsIDAsIDAsIDQsIDAsIDUsIDAsIDAsIDEgXSwKICBbIDAs
IDcsIDAsIDAsIDAsIDAsIDAsIDMsIDAgXSwKICBbIDAsIDAsIDQsIDAsIDAsIDAsIDksIDAs
IDAgXSwKICBbIDAsIDAsIDMsIDUsIDAsIDQsIDEsIDAsIDAgXSwKICBbIDAsIDAsIDcsIDAs
IDAsIDAsIDQsIDAsIDAgXSwKICBbIDAsIDAsIDgsIDksIDAsIDEsIDAsIDAsIDAgXSwKICBb
IDAsIDAsIDksIDAsIDAsIDAsIDYsIDAsIDAgXSwKICBbIDAsIDgsIDAsIDAsIDAsIDAsIDAs
IDIsIDAgXSwKICBbIDQsIDAsIDAsIDIsIDAsIDAsIDAsIDAsIDAgXQpdCgpzdGFydF90aW1l
ID0gVGltZS5uZXcKCmlmIG5leHRfc3RhdGUoc3RhcnQsIDAsIDApCiAgcHV0cyAidGltZSBl
bGFwc2VkOiAje1RpbWUubmV3IC0gc3RhcnRfdGltZX0gc2VjLiIKICBwdXRzICJjb3VudDog
I3skY291bnR9IgogIHN0YXJ0LmVhY2ggZG8gfHZhbHwKICAgIHB1dHMgdmFsLmpvaW4oIiAi
KQogIGVuZAplbHNlCiAgcHV0cyAiTm90IHNvbHZlYWJsZSEiCmVuZAoK
--------------040509020705090708050004
Content-Type: text/x-c++src;
 name="sudoku-solver.cpp"
Content-Transfer-Encoding: 8bit
Content-Disposition: inline;
 filename="sudoku-solver.cpp"

#include <iostream>
#include <time.h>

using namespace std;

int counter = 0;

int start[9][9] =
{
  { 0, 0, 0, 4, 0, 5, 0, 0, 1 },
  { 0, 7, 0, 0, 0, 0, 0, 3, 0 },
  { 0, 0, 4, 0, 0, 0, 9, 0, 0 },
  { 0, 0, 3, 5, 0, 4, 1, 0, 0 },
  { 0, 0, 7, 0, 0, 0, 4, 0, 0 },
  { 0, 0, 8, 9, 0, 1, 0, 0, 0 },
  { 0, 0, 9, 0, 0, 0, 6, 0, 0 },
  { 0, 8, 0, 0, 0, 0, 0, 2, 0 },
  { 4, 0, 0, 2, 0, 0, 0, 0, 0 }
};
    
bool isfine(int feld[9][9], int x, int y)
{
   // doppelte Zahl in Zeile oder Spalte?
   for (int yi = 0; yi < 9; yi++)
       if (yi != y && feld[x][yi] == feld[x][y])
           return false;
   for (int xi = 0; xi < 9; xi++)
       if (xi != x && feld[xi][y] == feld[x][y])
           return false;
   
   // Neuner-K辰stchen-Test
   int x1 = (x / 3) * 3;
   int y1 = (y / 3) * 3;
   for (int xk = x1; xk < x1 + 3; xk++)
       for (int yk = y1; yk < y1 + 3; yk++)
           if ((xk != x || yk != y) && feld[xk][yk] == feld[x][y])
               return false;
   
   return true;
}
    
bool nextone(int feld[9][9], int x, int y)
{
	++counter;
   if (y == 9) { y = 0; x++; };
   if (x == 9) return true;
   
   if (feld[x][y] > 0)
   {
       return nextone(feld, x, y + 1);
   }
   else for (feld[x][y] = 1; feld[x][y] <= 9; feld[x][y]++)
   {
       if (!isfine(feld, x, y)) continue;
       if (nextone(feld, x, y + 1)) return true;
   }
   feld[x][y] = 0;
   return false;
};
    
int main(int argc, char **argv)
{
  clock_t start_time = clock();
  if (nextone(start, 0, 0)){
    printf("time elapsed: %f\n sec.", ((double)clock() - start_time) / CLOCKS_PER_SEC);
    //cout << "time elapsed: " << ((double)clock() - start_time) / CLOCKS_PER_SEC) << " sec.\n";
    cout << "count: " << counter << endl;
    for (int x = 0; x < 9; x++)
    {
      for (int y = 0; y < 9; y++)
        cout << " " << start[x][y];
      cout << endl;
    }
   }  
   else cout << "Not solveable" << endl;
   return 0;
}

--------------040509020705090708050004--