From: Jon Harrop <jon@...>
Date: 2006-08-04T11:35:04+09:00
Subject: Re: For performance, don't write it in C++

Jon Harrop wrote:
> Here are my 32-bit timings (language versions are the same):
> 
>         Compile  Run
> C       0.126s    0.386s  gcc -O3 -Wall
> OCaml2  0.089s    0.391s  ocamlopt
> OCaml2  0.010s   10.111s  ocamlc
> Java    1.615s   12.745s  javac

Here's a C++ implementation:

C++     0.652s    0.608s  g++ -O3 -Wall

(95% of time is spent in addRow())

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int fact(int n) { return n == 0 ? 1 : n*fact(n-1); }

int size=5;
vector<int> list(size);
int n = fact(size);
vector< vector<int> > perms(n);
vector< vector<bool> > compat(n);
vector<int> board(size);
string out(size*(size+1), ':');

void print() {
  for (int i=0; i<size; ++i)
    for (int j=0; j<size; ++j)
      out[i*(size+1) + j] = '1' + perms[board[i]][j];
  cout << out;
}

int next(vector<bool> &compat, int row) {
  int prev_row = 0;
  while (prev_row < row && compat[board[prev_row]])
    ++prev_row;
  return prev_row;
}

void addRow(int row) {
  if (row == size) print(); else
    for (int latest=0; latest<n; ++latest) {
      if (next(compat[latest], row) == row) {
        board[row] = latest;
        addRow(row+1);
      }
    }
}

int main() {
  for (int i=0; i<size; ++i) list[i] = i;

  for (int i=0; i<n; ++i) {
    perms[i] = vector<int>(list.begin(), list.end());
    next_permutation(list.begin(), list.end());
  }

  for (int i=0; i<n; ++i) {
    compat[i] = vector<bool>(n);
    for (int j=0; j<n; ++j) {
      compat[i][j] = true;
      for (int k=0; k<size; ++k)
        if (perms[i][k] == perms[j][k]) {
          compat[i][j] = false;
          break;
        }
    }
  }

  out[size*(size+1)-1] = '\n';

  addRow(0);
}

-- 
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists