General Category > Общий раздел

Еще один тест на производительность.

(1/3) > >>

trurl:
Известная задача о ферзях и простой алгоритм.

--- Код: ---#include <stdio.h>
#include <time.h>
 
int board[32], count;

int can_place(int row,int col) {
  int i = 1;
  while((i < row) && (board[i] != col) && (abs(board[i]-col) != abs(i-row))) ++i;
  return (i == row);
}

void queen(int row,int n) {
  int col;
  for(col=1; col<=n; ++col)  {
    if(can_place(row,col)) {
       board[row] = col;
       if(row==n) ++count; else queen(row+1, n);
    }
  }
}

void solve(int n) {
  count = 0;
  queen(1,n);
}

int main(int argc, char **argv) {
  int N;
  clock_t starttime, endtime; float runtime;
  N = 13;
  if (argc == 2) N = atoi(argv[1]);
 
  printf("Solving %d Queens Problem ... \n", N );
  starttime = clock();
  solve(N);
  endtime  = clock();
  runtime  =  (endtime-starttime)/1000.0;
  printf(" %d solutions found, t = %f \n", count, runtime );
  return 0;
}

--- Конец кода ---
Запускал на разных компьютерах и усреднял относительное время среднепотолочно. За попугая принято время выполнения на BlackBox.
Разные компиляторы от ETH дали сравнимые результаты: 80-90%.
Oberon-07 от akron1 - 40%.
Oxford oberon - 40%, а с выключенным JIT всего 6%.
XDS - 100%, с оптимизацией и отключением проверок - 170%.

Компиляторы С без оптимизации 50-90%, но это неинтересно.
Лучший результат у clang - 220%.
Потом идет PellesC - 200%.
GCC и старенький Watcom - по 160%.
lcc немного не дотянул - 90%.
TinyC -  50%. 

JavaScript от гугла (V8): 100%,от мозиллы: 70%, и просто для интереса, JavaScript без JIT: от 5 до 20%.
LuaJit: 75%, просто Lua 4%.

Geniepro:
Погодите-ка, тут проценты надо считать не по времени, а по скорости расчётов, что ли? Потому-то непонятно, почему 220% времени лучше, чем 50%, ведь это в 4.4 раза медленнее должно быть...

trurl:
Ну да, по скорости. 200% - это вдвое быстрее BB, а 50% - вдвое медленнее.

kkkk:
Где версия для Оберона?

trurl:

--- Код: ---MODULE Queens;
IMPORT Out:=StdLog, Kernel;

VAR count:INTEGER;
    board: ARRAY 32 OF INTEGER;

PROCEDURE canplace(row,col:INTEGER):BOOLEAN;
  VAR i:INTEGER;
BEGIN
  i:=1; 
  WHILE  (i < row) & (board[i] # col) & (ABS(board[i]-col) # ABS(i-row)) DO
    INC(i)
  END;
  RETURN i = row
END canplace;

PROCEDURE queen(row, n:INTEGER);
  VAR col:INTEGER;
BEGIN
  FOR col := 1 TO n DO
    IF canplace(row,col)  THEN
      board[row] := col;
      IF row = n THEN count := count + 1 ELSE queen(row+1, n)  END
    END
  END
END queen;

PROCEDURE solve(n:INTEGER);
BEGIN
  count := 0;
  queen(1,n);
END solve;

PROCEDURE Do*(N:INTEGER);
VAR  starttime, endtime:LONGINT;
BEGIN
  Out.String("Solving "); Out.Int(N); Out.String(" Queens Problem") ;Out.Ln;
  starttime := Kernel.Time();
  solve(N);
  endtime  := Kernel.Time();
  Out.Int(count); Out.String(" solutions found t ="); Out.Real((endtime-starttime)/1000); Out.Ln;
END Do;

END Queens.
--- Конец кода ---
Вот для BB. Для других приходится переделывать немного.

Навигация

[0] Главная страница сообщений

[#] Следующая страница