1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Кто может сделать быстрее? "Задача о восьми Ферзях"

Тема в разделе "WASM.A&O", создана пользователем locki, 16 июл 2006.

  1. Yuric74

    Yuric74 New Member

    Публикаций:
    0
    Регистрация:
    24 июл 2006
    Сообщения:
    1
    Моя прога выдает первый вариант для N=32 за 1187 мс. :)
    Комп Cel 2.0@3.0
     
  2. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    locki
    То есть, если я правильно читаю результаты, одно решение для 32 ферзей искали более 20ти секунд? Здесь приводится программа на ПРОЛОГе, которая (если верить описанию) находит решение для 100 ферзей за меньше чем 0.1 секунды. Надо бы проверить :)
     
  3. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Взял за исходную точку код отсюда, приделал упоминавшиеся выше оптимизации и развернул рекурсию. Получилось следующее:

    Код (Text):
    1. #include <stdio.h>
    2. #include <windows.h>
    3.  
    4. int count = 0;
    5.  
    6. void queens(int N) {
    7.     int arow[32], aleft[32], aright[32], aposs[32];
    8.     int poss, place, val = (1<<N)-1, pos=1;
    9.  
    10.     arow[1]=aleft[1]=aright[1]=0;
    11.     poss=aposs[1]=val>>(N/2);
    12.  
    13.     while(pos){
    14.         if(poss){
    15.             place = poss & -poss;
    16.             poss &= ~place;
    17.             if(pos==1 && !poss && (N & 1))count<<=1;
    18.             if(pos!=N){
    19.                 aposs[pos]=poss;
    20.                 poss=arow[pos+1]=arow[pos]|place;
    21.                 poss|=aleft[pos+1]=(aleft[pos]|place)<<1;
    22.                 poss|=aright[pos+1]=(aright[pos]|place)>>1;
    23.                 aposs[++pos]=poss=~(poss) & val;
    24.             } else{
    25.                 ++count;
    26.             }
    27.         }else{
    28.             poss=aposs[--pos];
    29.         }
    30.     }
    31. }
    32.  
    33. void main() {
    34.         int N=0;
    35.     printf("Enter number of queens (1..32):");
    36.     scanf("%d", &N);
    37.     printf("Placing %d queens...\n", N);
    38.     DWORD tick=GetTickCount();
    39.     queens(N);
    40.     if(!(N & 1))count<<=1;
    41.     printf("%d ms.\n", GetTickCount()-tick);
    42.     printf("There are %d solutions.\n", count);
    43.     char c;
    44.     scanf("%c",&c);
    45. }
    Результат:
    16 - 11186 мс
    17 - 83360 мс

    Версия 1.3 (Black_mirror)
    16 - 9404 мс
    17 - 64343 мс

    Для чистого С++ очень даже неплохо :) около 25% разницы (Pentium M, 2 GHz). Не знаю, имеет ли смысл оптимировать дальше С-шный код, так как уже начинается бред компилятора. Например если убрать строчку

    if(pos==1 && !poss && (N & 1))count<<=1;

    то скорость вместо увеличения падает в полтора раза. Компилятор - Microsoft C++ 12.00.
     
  4. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Хватит время мерять! Сделайте уже вклад в науку!

    Вычислите число расстановок N мирных ферзей для N>25.
    Или число уникальных (с точностью до отражений и поворотов) расстановок N мирных ферзей для N>23.
    Или число (всех и уникальных) расстановок N мирных суперферзей для N>20. Суперферзь - это смесь ферзя и коня.

    Текущее положение дел в этих вопросах обрисовано тут: http://www.durangobill.com/N_Queens.html
     
  5. locki

    locki New Member

    Публикаций:
    0
    Регистрация:
    16 июл 2005
    Сообщения:
    83
    Адрес:
    Russia
    RElf
    Ну ты даешь! Тут для 25 ферзей считали на 260 компьютерах полгода (цитата:{6 months, about 260 machines [PII and PIV from 450 MHz to 3.4 GHz]}, а ты... Читай внимательней то, о чем говоришь...
     
  6. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    Есть число всех расстановок сверхферзей для N=21!

    F(10)=4 time=1 ms speed=4000 v/s
    F(11)=44 time=1 ms speed=44000 v/s
    F(12)=156 time=1 ms speed=156000 v/s
    F(13)=1876 time=2 ms speed=938000 v/s
    F(14)=5180 time=10 ms speed=518000 v/s
    F(15)=32516 time=58 ms speed=560620 v/s
    F(16)=202900 time=380 ms speed=533947 v/s
    F(17)=1330622 time=2584 ms speed=514946 v/s
    F(18)=8924976 time=18519 ms speed=481936 v/s
    F(19)=64492432 time=139s speed=463101 v/s
    F(20)=495864256 time=1086s speed=456403 v/s

    F(21)=3977841852 time=8883 s speed=447799 v/s

    Версия в архиве чуть по медленее, но зато считает и число уникальных расстановок.
     
  7. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    RElf
    Число всех расстановок до N=23 приведено здесь. Правда непонятен источник.
     
  8. bogrus

    bogrus New Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    У меня другое число всех расстановок получилось, это нормально?

    AXv1.0:
    end A(21)=3984578290 (497236090) time=6576782 ms speed=605855 v/s
     
  9. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    A(14)=5180 (653) time=16 ms speed=323750 v/s
    A(15)=32516 (4089) time=62 ms speed=524451 v/s
    A(16)=202900 (25411) time=359 ms speed=565181 v/s
    A(17)=1330622 (166463) time=2438 ms speed=545784 v/s

    A(18)=8924976 (1115871) time=17766 ms speed=502362 v/s [2 threads]
    A(18)=8924976 (1115871) time=17750 ms speed=502815 v/s [4 threads]
    A(18)=8924976 (1115871) time=17781 ms speed=501938 v/s [8 threads]

    На малых значения скорость куда-то исчезает. Считал в основном с помощью 4 потоков - получается незначительно шустрее (чудеса HT?)

    Интересно - сложно ли сделать программу распределенной...
     
  10. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    bogrus
    Это на многопроцессорной машине получилось? Если так, то возможно всё дело в том, что я в потоках делающих перебор не поставил LOCK, перед командой увеличивающей 32х-разрядный счётчик найденных решений (для каждого потока свой). Эти счётчики основной поток периодически забирает делая xchg с регистром содержащим ноль, и добавляет к 64х-разрядному счётчику. Видимо этот xchg вклинивается когда поток на другом процессоре прочитал счётчик, чтобы сделать инкремент, но еще не успел его записать. Я добавил префиксы к этой программе, а также к FX1.3. Проверь пожалуйста старую и новую версии на меньших значениях, на них баг тоже вылезает?

    alpet
    Скорость уходит на создание потоков. А может просто не получилось поделить на нулевой интервал времени.

    Ну сам алгоритм параллелится на ура. Ну самое сложное в распределённой программе это
    защита это сбоев и от фальсификации результатов со стороны злоумышленника.
     
  11. bogrus

    bogrus New Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    да на двух ядрах, сейчас стало все нормально, ещё CRLF перевернуть забыл (крякозябл получается)
    Код (Text):
    1.         mov dword [buf],'AXv1'
    2.         mov dword [buf+4],'.01:'
    3.         mov dword [buf+8],$D0A
     
  12. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Black_mirror
    Ну и какие получились значения? Результатами для N>20 можешь пополнить последовательность A051224 и увековечить там свое имя ;)
     
  13. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    Вот что у меня получилось для 21:
    end A(21)=3977841852 (497236090) time=8621266 ms speed=461398 v/s
     
  14. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Возвращаясь к обычным ферзям: можно ускорить алгоритм еще почти в полтора раза если использовать две оси симметрии вместо одной. В аттаче соответствующая модификация С-шного кода для четных N

    Результаты (Pentium M, 2 GHz):
    16 - 6319 мс
    18 - 321 с

    Версия 1.3 (Black_mirror):
    16 - 9404 ms
    18 - 463 s

    То есть бьет версию 1.3 больше чем на 40%. Для нечетных N принцип тот же самый, но я замучился с компилятором воевать.

    Black_mirror, приделай у себя вторую ось симметрии, тогда точно никто не догонит :) Суть в том, что начинать нужно не с первой строки доски, а в середине. Тогда в большинстве случаев достаточно перебрать только четверть вариантов.
     
  15. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    Black_mirror
    Замечательно, может тогда сделать его версию для видеокарт, по методике GPGPU? Или возможностей шейдеров для этого не хватит?
     
  16. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    Stiver
    Не знаю сколько там осей симметрии, я решил перебирать только уникальные варианты. В архиве очень жуткий код (для понимания), написан на Си, но он имеет шансы стать новым чемпионом (после перевода на асм).

    alpet
    Я не знаю как организованны шейдеры, и можно ли там делать сложные циклы или рекурсию, но когда появится десятая версия, решить на них эту задачу точно можно будет ;)
     
  17. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Black_mirror
    Файл AX11.zip у меня не открывается, говорит поврежденный архив.

    Вот еще интересная ссылка, где упоминается симметрия: Non-attacking Queens Problem Page
     
  18. locki

    locki New Member

    Публикаций:
    0
    Регистрация:
    16 июл 2005
    Сообщения:
    83
    Адрес:
    Russia
    Black_mirror
    Привет. Тут у людей назрел вопрос почему новый навороченный "КОНРОЙ" (делающий аж 4! команды за такт) проигрывает Athlon'у 64, да еще и при большей тактовой частоте:
    4.__dream_____AMD_X2-3800+_3020MHz_______403Mhz-1.5-3-2-5__12266ms
    5.__colfin22____E6600_Core_2_Duo_@3.25Ghz___820Mhz-5-5-5-15___12562ms
    тогда как во всех остальных тестах при равных частотах наблюдается 8-20% преимущество "Конроя"... ???
     
  19. locki

    locki New Member

    Публикаций:
    0
    Регистрация:
    16 июл 2005
    Сообщения:
    83
    Адрес:
    Russia
    P.S. Кстати, я тут сделал вот это: http://benchqueens.narod.ru/
    Надеюсь ты не против...
     
  20. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    locki
    Может троттлинг?