Просмотр сообщений

В этом разделе можно просмотреть все сообщения, сделанные этим пользователем.


Темы - trurl

Страницы: [1]
1
Известная задача о ферзях и простой алгоритм.
#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%.

2
Общий раздел / K&Q
« : Январь 28, 2012, 08:22:54 am »
Моя первая программа на языке q: преобразует положительное целое число в последовательность символов (запись числа).
q)x:18873; L:"012345679"; res:""; while[x>0; res:res,L[x mod 10]; x:x div 10]; reverse res
"18873"
Не знаю, как векторизовать без while : (
Подскажите, как улучшить решение!

"0123456789"@ 1_ reverse {x mod 10} each {x div 10} scan 18873или на K:
"0123456789"@ 1_|{ !10}'{_ x % 10}\ 18873

Страницы: [1]