|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeny Sharandin 2:5020/755.12 23 Oct 2001 14:39:00
To : Rustam Gadeyev
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
Привет Rustam!
19 октября 2001 года (а было тогда 17:12)
Rustam Gadeyev в своем письме к Evgeny Sharandin писал:
RG> Рекурсия всегда короче, но не быстрее.
Точнее - не всегда быстрее ;). Здесь же была идея сделать две процедуры для
учета повторяющихся комбинаций, но она не сработала ;(.
RG> Поэтому я внес непринципиальные изменения в свою программку, ведь BP7
RG> не оптимизирует использование переменных. И размер 14 мой вариант
RG> вычисляет на 30% быстрее, чем твой рекурсивный вариант. Переписанный
RG> алгоритм один в один на BC3.1 считает еще быстрее, а вот WC10.0
RG> почему-то медленнее
Hу кто же так делает? Сразу видно завзятого паскалиста ;). Замени
арифметическое and на логическое (вместо & поставь &&) и все встанет на свои
места. То, что ВС сработал в этом случае по короткой схеме характеризует его не
лучшим образом.
RG> (/5 /oilr /s).
О! Оптимизатор ваткома всегда отличался причудливостью, а уж его разворачивание
циклов... Вполне достаточно было бы /r.
RG> Видимо оптимизировать уже нечего.
Да там и изночально оптимизировать особо нечего было. Все время съедает первый
if и только на него стоит обращать внимание.
RG> Процессор P3-450. В прошлый раз я ошибся, у меня был Cel-550.
RG> old BP7 14 27.73, 13 4.63
RG> ES BP7 14 23.43, 13 3.89
RG> RG BP7 14 18.51, 13 3.24
RG> RG BC3.1 14 11.75, 13 1.92
RG> RG WC10 14 12.58, 13 2.08
RG> Так что теперь я думаю сильно быстрее сделать уже нельзя.
Hу почему же? Можно чуток еще подбросить упрощением оператора сравнения. Hу а
если учесть симметрию, можно и сильно ускорить. Для перебора только половины
первого столбца, даже с учетом четности/нечетности размера доски, усложнения
особо не потребуется, а время сокраится практически вдвое.
Следующий вариант, в котором рекурсия преобразована в цикл. Тупо, но надежно ;)
=== File / Q2.PAS / ===
program queens;
uses timer;
Const N=14;
var
v : array [0..N] of byte;
h : array [0..N] of boolean;
d1 : array [0..2*N] of boolean;
d2 : array [-N..N] of boolean;
Num: longint;
procedure Find;
Label M1;
var
x, y : integer;
begin
Num:=0;
for x:=1 to N do h[x]:=true;
for x:=2 to 2*N do D1[x]:=true;
for x:=-N+1 to N-1 do D2[x]:=true;
x:=1;
M1:
y:=N;
repeat
while y > 0 do begin
if h[y] and d1[x+y] and d2[x-y] then begin
v[x]:=y; {Hаступаем сюда}
if x=N then begin
{сюда печать вставить}
inc(Num)
end else begin
h[y]:=false; {Запрещаем диагонали и горизонталь}
d1[x+y]:=false; d2[x-y]:=false;
inc(x);
GoTo M1;
end;
end;
dec(y);
end;
dec(x);
if x=0 then break;
y:=v[x];
h[y]:=true; {Откат}
d1[x+y]:=true; d2[x-y]:=true;
dec(y);
until false;
end;
begin
time1;
Find;
writeln(Num,' вариантов', time2*1e-3:7:2,' Sec');
end.
=== End / Q2.PAS / ===
Вот результаты, для сопоставимости приведены и твои. iP-233mmx
BP7 Delphi 5.0 GPC SBP
Rustam N1 67.9 44.3 46.0
Shar N1 40.8 21.2 24.9
Rustam N2 31.7 29.6 22.7
Shar N2 29.6 16.3 14.8 20.4
Ключи GPC (2.1 навешанный на gcc 3.0, djgpp-шный порт): "-O3 -s". Подбором
ключей можно было бы пару процентов выудить за счет некоторой дооптимизации
внутренностей цикла.
Обрати внимание - после оптимизирующего компилятора время поиска на первопне
только чуть больше сишного варианта на вдое более высокочастотном пне2. Если ты
в своем варианте сместишь массивы для исключения лишнего сложения и вычитания,
то должно получиться что-то около того.
Обычно на х86 в регистры компиляторы засовывают до трех целочисленных
переменных. Поэтому смело можно добавить еще одну переменную, в которой хранить
x+y и менять ее синхронно с изменением x и у. Hа этом, думаю, еще 1-2 сек.
получится отыграть (на ВР, наверное, будет наоборот). Hу а далее - только
симметрию учитывать, скорее всего.
Итого имеем уже 67.9/14.8 ~ 4.5. До обещанного порядка совсем чуть-чуть
осталось ;)
С уважением, Evgeny 23 октября 2001 года
---
* Origin: LID (2:5020/755.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
