Что, господа суровые С++ программисты, поспорим быстродействием с отстойной Джавой? ;)

 
1 2 3 4 5 6 7 29
+
-
edit
 

Balancer

администратор
★★★★☆
pokos> Чо ж тут непонятного? Для простого примера берём обычный рекурсивный фильтр. При сбое в одной операции его легко может понести вразнос. Если разрядность ограничена, то эта херня длится всего несколько циклов, потом всё упирается в разрядность и происходит устаканивание. А если разрядность неограничена, то фильтр засрёт всю память до упора, и программа умрёт ВСЯ. "Очередной КА убит софтом".

Тебя куда-то очень сильно уносит :D Начиная с того, что Питон не будут ставить на КА в обозримом будущем, у него иной профиль, кончая тем, что если у тебя в процессоре существует осуществимая вероятность сбоя при сдвиге, то комп будет постоянно сыпаться хоть в Питоне, хоть в машкодах :)

...

И ты главного не понял. Пока разрядности хватает или по прямому указанию программиста, Питон будет оперировать Int'ом, а не Long'ом. А Int у него обычный, машинный.
 
US Сергей-4030 #03.06.2008 21:10  @pokos#02.06.2008 10:09
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Balancer>> Разъясни, чем целый (машинный) тип Питона хуже целого типа Си,...
pokos> Чо ж тут непонятного? Для простого примера берём обычный рекурсивный фильтр. При сбое в одной операции его легко может понести вразнос. Если разрядность ограничена, то эта херня длится всего несколько циклов, потом всё упирается в разрядность и происходит устаканивание. А если разрядность неограничена, то фильтр засрёт всю память до упора, и программа умрёт ВСЯ. "Очередной КА убит софтом".

Странный подход. А если не хватит одной единички и переполнение убъет КА? Тогда все хорошо и нормально?
 
+
-
edit
 

pokos

аксакал

Balancer> ... если у тебя в процессоре существует осуществимая вероятность сбоя при сдвиге, то комп будет постоянно сыпаться хоть в Питоне, хоть в машкодах :)
Рома, вообще-то это тема для целого диссера. А ты тут так ловко икс-як, и все дела...
Balancer> И ты главного не понял. Пока разрядности хватает...
Это ты главного не понял. Я писал о случае, когда разрядности не хватило.

Вот потому и
Balancer>...Питон не будут ставить на КА в обозримом будущем, у него иной профиль..

У него не только профиль, но и фас другой.
 
CA pokos #05.06.2008 10:37  @Сергей-4030#03.06.2008 21:10
+
-
edit
 

pokos

аксакал

Сергей-4030> Странный подход. А если не хватит одной единички и переполнение убъет КА? Тогда все хорошо и нормально?
Переполнение не убивает КА, потому что оно не убивает программу. Переполнение леко и примитивно обнаруживается и обрабатывается как надо.
А вот засёр всей памяти парой переменных уже никак не обработаешь. Токо рестарт.
 
+
-
edit
 

Balancer

администратор
★★★★☆
pokos> Это ты главного не понял. Я писал о случае, когда разрядности не хватило.

Тогда я не понял и почему при нехватке разрядности GMP в Питоне способна на большую ошибку, чем GMP в Си :)

pokos> У него не только профиль, но и фас другой.

Ну так а какого тогда ты тёплое с мягким сравнивать рвёшься?
 
+
-
edit
 

Balancer

администратор
★★★★☆
pokos> Переполнение не убивает КА, потому что оно не убивает программу.

Скажи это приснопамятному Ариану :D
 
+
-
edit
 

pokos

аксакал

Balancer> Тогда я не понял и почему при нехватке разрядности GMP в Питоне способна на большую ошибку, чем GMP в Си :)
Да я, вроде, пояснил уже. На примере.

Balancer> Ну так а какого тогда ты тёплое с мягким сравнивать рвёшься?
Дык, это не я рвался сравнивать, а совсем-таки ты!

Balancer> Там используются многоразрядные сдвиги. Это решение одно из первых в голову приходящее. В Питоне они есть на уровне языка. В Java и Си - нет.

Balancer>Скажи это приснопамятному Ариану
Чтоп он был здоров! А программисту, забившему на нормальную обработку исключения, забить метра два осины в анус.
 
+
-
edit
 

Balancer

администратор
★★★★☆
pokos> Да я, вроде, пояснил уже. На примере.

Я не видел примера, чем использование GMP в Си лучше использования GMP в Питоне. Нет, даже не так. Я не видел примера, почему написанная на Си GMP при работе внутри себя в случае вызова из Си будет работать лучше, чем при вызове из Питона.

pokos> Чтоп он был здоров! А программисту, забившему на нормальную обработку исключения, забить метра два осины в анус.

Ну вот, и тут пошли какие-то уточнения, которых не было в исходных условиях. Опять же, исключения и на Питоне легко перехватываются и обрабатываются.

В общем, банальный троллинг. Всего хорошего.
 
+
-
edit
 

pokos

аксакал

Balancer> ...Опять же, исключения и на Питоне легко перехватываются и обрабатываются.
Да-да, с громким ура. Если не видишь разницу между исключением по переполнению типа и исключением по переполнению ОЗу, то да, досвиданья.
 
+
-
edit
 

Balancer

администратор
★★★★☆


...
exception OverflowError
Raised when the result of an arithmetic operation is too large to be represented. This cannot occur for long integers (which would rather raise MemoryError than give up). Because of the lack of standardization of floating point exception handling in C, most floating point operations also aren't checked. For plain integers, all operations that can overflow are checked except left shift, where typical applications prefer to drop bits than raise an exception.
...
exception MemoryError
Raised when an operation runs out of memory but the situation may still be rescued (by deleting some objects). The associated value is a string indicating what kind of (internal) operation ran out of memory. Note that because of the underlying memory management architecture (C's malloc() function), the interpreter may not always be able to completely recover from this situation; it nevertheless raises an exception so that a stack traceback can be printed, in case a run-away program was the cause.

По-моему, разница очевидна.

Но ты так и не ответил на вопрос про разницу GMP в Си и в Питоне. Типа, продолжается троллинг?
 
+
-
edit
 

pokos

аксакал

Balancer> ...Я не видел примера, почему написанная на Си GMP при работе внутри себя в случае вызова из Си будет работать лучше, чем при вызове из Питона.
У тебя хорошее зрение. Да, я приводил несколько другую ситуацию.

Balancer> По-моему, разница очевидна.
"Хорошо, что хоть это-то понял." к/ф "Копейка".
Теперь потренируйся писать обработчики этих исключений в реальном времени. Тогда, Бог даст, поймёшь, что разница ещё больше.

Да, можешь записать это в троллинг, как ты любишь. Покедова.
 
US Сергей-4030 #05.06.2008 17:30  @pokos#05.06.2008 16:29
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
pokos> "Хорошо, что хоть это-то понял." к/ф "Копейка".
pokos> Теперь потренируйся писать обработчики этих исключений в реальном времени. Тогда, Бог даст, поймёшь, что разница ещё больше.

А у тебя что за основания вещать в таком менторском тоне - "попробуй", "поймешь"? Ты со школьниками, думаешь, дискутируешь? Ты уж тогда сначала покажи предметно, что у тебя опыт программирования - ого-го какой, мы все сынки перед тобой. А то понтов много, а информации - ноль.

pokos> Да, можешь записать это в троллинг, как ты любишь. Покедова.

В данном случае с Романом нельзя не согласиться.
 
UA passer by #06.07.2008 23:01
+
-
edit
 

passer by

новичок
Дорого времени суток.

На моем железе ваш вариант работает так

code text
  1. 16 queens.
  2. Started at:Sun Jul 06 20:56:10 EEST 2008
  3. SIZE=16
  4. BITS_PER_CELL=4
  5. FILL_MASK=15
  6. Finished at:Sun Jul 06 20:59:15 EEST 2008, after 185109 ms.
  7. 1846955 solutions found.


После небольшой оптимизации работает так

code text
  1. 16 queens.
  2. Started at:Sun Jul 06 21:10:48 EEST 2008
  3. SIZE=16
  4. BITS_PER_CELL=4
  5. FILL_MASK=15
  6. Finished at:Sun Jul 06 21:13:39 EEST 2008, after 170610 ms.
  7. 1846955 solutions found.


Ускорение около 8%. Интересно насколько ускорится, если избавиться от постоянного распределение памяти при входе в процедуры ? Здесь это сделать возможно, потому как глубина вызовов равна размеру доски. Только все это пробовать в яве не стоит.
 
UA passer by #06.07.2008 23:03
+
-
edit
 

passer by

новичок
Изменения в коде

code text
  1. package com.ssv.test.samples.queens2;
  2.  
  3. import java.util.Set;
  4. import java.util.HashSet;
  5.  
  6. class Solution {
  7.  
  8.     static private class SolutionThread extends Thread {
  9.         public SolutionThread(int partial) {
  10.             pos = partial;
  11.             solution = new Solution(partial);
  12.             setName("T" + pos);
  13.         }
  14.  
  15.         public void run() {
  16.             solution.arrange();
  17.         }
  18.  
  19.         final Solution solution;
  20.         final int pos;
  21.     }
  22.  
  23.     public static Set<Long> solve(final int size, boolean checkTransitions) {
  24.  
  25.         setLimits(size, false, checkTransitions);
  26.  
  27.         Thread solutionThreads[] = new Thread[size];
  28.         for (int i = 0; i < size; i++) {
  29.             solutionThreads[i] = new SolutionThread(i);
  30.             solutionThreads[i].start();
  31.         }
  32.  
  33.         try {
  34.             for (int i = 0; i < size; i++) {
  35.                 solutionThreads[i].join();
  36.             }
  37.  
  38.         } catch (InterruptedException e) {
  39.         }
  40.  
  41.         return solutions;
  42.     }
  43.  
  44.     public static Set<Long> solveSingle(final int size, boolean first, boolean checkTransitions) {
  45.         setLimits(size, first, checkTransitions);
  46.         (new Solution()).arrange();
  47.         return solutions;
  48.  
  49.     }
  50.  
  51.     static private void setLimits(int size, boolean first, boolean check) {
  52.         SIZE = size - 1;
  53.         BITS_PER_CELL = 0;
  54.         while(SIZE != 0) {BITS_PER_CELL++;  SIZE = (SIZE >> 1);}
  55.         SIZE = size;
  56.         FILL_MASK = (((long)1) << BITS_PER_CELL) - 1;
  57.  
  58.         EightQueens.log("SIZE=" + SIZE);
  59.         EightQueens.log("BITS_PER_CELL=" + BITS_PER_CELL);
  60.         EightQueens.log("FILL_MASK=" + FILL_MASK);
  61.  
  62.         FIRST_ONLY = first;
  63.         CHECK_TRANSITIONS = check;
  64.     }
  65.  
  66.     public Solution() {
  67.         desk = 0;
  68.     }
  69.  
  70.     public Solution(int partialSolution) {
  71.         this();
  72.         addQueen(partialSolution);
  73.     }
  74.  
  75.     long stack[] = new long[SIZE];
  76.     int sp = 0;
  77.  
  78.     private boolean addQueen(int pos) {
  79.         if (verts[pos]
  80.             || diags1[currentLine - pos + (SIZE - 1)]
  81.             || diags2[currentLine + pos])
  82.             return false;
  83.  
  84.         stack[sp++] = desk;
  85.         desk = Desk.setPos(desk, pos, currentLine);
  86.  
  87.         verts[pos] = diags1[currentLine - pos + (SIZE - 1)] = diags2[currentLine + pos] = true;
  88.  
  89.         currentLine++;
  90.         return true;
  91.     }
  92.  
  93.     private void removeLastQueen(int pos) {
  94.         currentLine--;
  95.         desk = stack[--sp];
  96.         verts[pos] = diags1[currentLine - pos + (SIZE - 1)] = diags2[currentLine + pos] = false;
  97.     }
  98.  
  99.     private void arrange() {
  100.         if (currentLine == SIZE) {
  101.             addKnownPosition(desk);
  102.         } else {
  103.             for (int x = 0; x < SIZE; x++) {
  104.                 if (addQueen(x)) {
  105.                     arrange();
  106.                     removeLastQueen(x);
  107.                 }
  108.             }
  109.         }
  110.     }
  111.  
  112.     private static void addKnownPosition(long desk) {
  113.         long fliphor0  = Desk.cloneFlipHor(desk);
  114.         long flipvert0 = Desk.cloneFlipVert(desk);
  115.  
  116.         long clone1    = Desk.cloneRotate(desk);
  117.         long fliphor1  = Desk.cloneFlipHor(clone1);
  118.         long flipvert1 = Desk.cloneFlipVert(clone1);
  119.  
  120.         long clone2    = Desk.cloneRotate(clone1);
  121.         long fliphor2  = Desk.cloneFlipHor(clone2);
  122.         long flipvert2 = Desk.cloneFlipVert(clone2);
  123.  
  124.         long clone3    = Desk.cloneRotate(clone2);
  125.         long fliphor3  = Desk.cloneFlipHor(clone3);
  126.         long flipvert3 = Desk.cloneFlipVert(clone3);
  127.  
  128.         long min_desk  = desk;
  129.         if(fliphor0  < min_desk) min_desk = fliphor0;
  130.         if(flipvert0 < min_desk) min_desk = flipvert0;
  131.         if(clone1    < min_desk) min_desk = clone1;
  132.         if(fliphor1  < min_desk) min_desk = fliphor1;
  133.         if(flipvert1 < min_desk) min_desk = flipvert1;
  134.         if(clone2    < min_desk) min_desk = clone2;
  135.         if(fliphor2  < min_desk) min_desk = fliphor2;
  136.         if(flipvert2 < min_desk) min_desk = flipvert2;
  137.         if(clone3    < min_desk) min_desk = clone3;
  138.         if(fliphor3  < min_desk) min_desk = fliphor3;
  139.         if(flipvert3 < min_desk) min_desk = flipvert3;
  140.  
  141.         synchronized (solutions) {
  142.             if ( !CHECK_TRANSITIONS || !solutions.contains(min_desk)) {
  143.                 solutions.add(min_desk);
  144.             }
  145.         }
  146.     }
  147.  
  148.     static int SIZE;
  149.     static int BITS_PER_CELL;
  150.     static long FILL_MASK;
  151.     static boolean FIRST_ONLY = false;
  152.     static boolean CHECK_TRANSITIONS = true;
  153.  
  154.     static final Set<Long> solutions = new HashSet<Long>(2000000);
  155.  
  156.     boolean verts[] = new boolean[SIZE];
  157.     boolean diags1[] = new boolean[2 * SIZE];
  158.     boolean diags2[] = new boolean[2 * SIZE];
  159.     int currentLine = 0;
  160.     long desk = 0;
  161.  
  162. }


code text
  1. package com.ssv.test.samples.queens2;
  2.  
  3. import java.io.IOException;
  4. import java.util.Date;
  5. import java.util.Set;
  6. import java.util.Iterator;
  7.  
  8. public class EightQueens {
  9.             static void log(String s) {
  10.                         if (log)
  11.                                     System.out.println(s);
  12.             }
  13.  
  14.             static boolean threaded = false;
  15.             static boolean first = false;
  16.             static boolean log = false;
  17.             static boolean print = false;
  18.             static boolean wait = false;
  19.             static boolean nocheck = false;
  20.             static int size = 12;
  21.  
  22.             private static void parseParameters(String args[]) {
  23.                         for (int i = 0; i < args.length; i++) {
  24.                                     if (args[i].equalsIgnoreCase("threaded"))
  25.                                                 threaded = true;
  26.                                     else if (args[i].equalsIgnoreCase("first"))
  27.                                                 first = true;
  28.                                     else if (args[i].equalsIgnoreCase("log"))
  29.                                                 log = true;
  30.                                     else if (args[i].equalsIgnoreCase("print"))
  31.                                                 print = true;
  32.                                     else if (args[i].equalsIgnoreCase("wait"))
  33.                                                 wait = true;
  34.                                     else if (args[i].equalsIgnoreCase("nocheck"))
  35.                                                 nocheck = true;
  36.                                     else {
  37.                                                 try {
  38.                                                             size = Integer.parseInt(args[i]);
  39.                                                 } catch (NumberFormatException e) {
  40.                                                             System.out.println("Invalid argument:" + args[i]);
  41.                                                 }
  42.                                     }
  43.  
  44.                                     if (first) {
  45.                                                 threaded = false;
  46.                                                 print = true;
  47.                                     }
  48.                         }
  49.             }
  50.  
  51.             public static void main(String args[]) {
  52.                         Date begin = new Date();
  53.                         parseParameters(args);
  54.                         System.out.println("" + size + " queens.");
  55.                         System.out.println("Started at:" + begin);
  56.                         Set<Long> solutions = (!threaded) ? Solution.solveSingle(size, first, ! nocheck)
  57.                                                 : Solution.solve(size, ! nocheck);
  58.                         Date finish = new Date();
  59.                         System.out.println("Finished at:" + finish + ", after "
  60.                                                 + (finish.getTime() - begin.getTime()) + " ms.");
  61.                         System.out.println("" + solutions.size() + " solutions found.");
  62.                         if (print) {
  63.                             Iterator<Long> iterator =  solutions.iterator();
  64.                             while(iterator.hasNext())
  65.                                 System.out.println(Desk.toString(iterator.next()));
  66.                         }
  67.                         if (wait)
  68.                                     try {
  69.                                                 System.in.read();
  70.  
  71.                                     } catch (IOException e) {
  72.                                                 e.printStackTrace();
  73.                                     }
  74.             }
  75. }
 
US Сергей-4030 #07.07.2008 04:46  @passer by#06.07.2008 23:01
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
p.b.> Дорого времени суток.
p.b.> На моем железе ваш вариант работает так
p.b.> Ускорение около 8%. Интересно насколько ускорится, если избавиться от постоянного распределение памяти при входе в процедуры ? Здесь это сделать возможно, потому как глубина вызовов равна размеру доски. Только все это пробовать в яве не стоит.

Вы бы привели changelog, а то неудобно. Насколько я понял, вы развернули цикл в addKnownPosition и убрали проверки в arrange(). По-моему, развертка циклов дала копейки, а проверки в arrange() - они ж не просто так, они для повышения гибкости.

ЗЫ Изменения в addQueen вряд ли вообще повлияли на байт-код. Сорри.
 
US Сергей-4030 #07.07.2008 04:51  @passer by#06.07.2008 23:01
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
p.b.> Ускорение около 8%. Интересно насколько ускорится, если избавиться от постоянного распределение памяти при входе в процедуры ? Здесь это сделать возможно, потому как глубина вызовов равна размеру доски. Только все это пробовать в яве не стоит.

Вряд ли вообще ускорится. Положить ссылку на объект на стек никакой проблемы не представляет.
 
US Сергей-4030 #07.07.2008 05:03
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Вообще, addKnownPosition вряд ли имеет смысл особо править - редко вызывается, не имеет смысла. arrange, addQueen, removeQueen - вот куда следует смотреть. М.б. стоит переопределить хэш-функцию и написать свою реализацию хэш-массива. Наверняка развертка рекурсии в код даст хороший выигрыш.
 
US Сергей-4030 #07.07.2008 05:11
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
И еще, конечно, синхронизация. У меня мультипотоковость сделана достаточно наивно - времени тратить не хотелось. Поэтому до 40% времени проводим в wait(). Вот тут точно поле для улучшения непаханое. Я бы сказал, при правильной организации потоков те самые 40% в скорости и отыграются.
 
RU anonymous_lor #07.07.2008 09:52
+
-
edit
 

anonymous_lor

новичок

короче ... ЛОР-овские анонимусы подтверждают свой высокий статус и что они круче гор :) ... написал я реализацию на C ... честно признаюсь, тупо переписывал код с явы, в качестве реализации hash таблицы использовалась реализация найденая в гугле 404 Not Found

собственно полностью файлы для сборки и с exe-шкой лежат тут, кому интересно http://slil.ru/25962907

код программы

code text
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4. #include "hashtable.h"
  5.  
  6. typedef __int64 desk_t;
  7.  
  8. int         desk_size = 8;
  9. char        verts[16]  = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  10. char        diags1[32] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  11. char        diags2[32] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  12. unsigned    solution_count = 0;  
  13. desk_t      desk_cache[23000000];
  14. int         desk_cache_count = 0;
  15. struct hsahtable*  desk_hash = NULL;
  16.  
  17. desk_t desk_set_pos(desk_t desk, int c, int r)
  18. {
  19.         return desk | ((__int64)c << (r * 4));
  20. }
  21.  
  22. unsigned int desk_hash_from_key( void *k )
  23. {
  24.         return *(unsigned int*)k;
  25. }
  26.  
  27. int          desk_keys_equal ( void *key1, void *key2 )
  28. {
  29.         return *(desk_t*)key1 == *(desk_t*)key2;
  30. }
  31.  
  32. void desk_save_cache(desk_t desk)
  33. {
  34.         if (desk_cache_count >= 23000000)
  35.         {
  36.                 printf("\nalarm, desk_cache_count >= 23000000!!!\n");
  37.                 exit(1);
  38.         }
  39.         desk_cache[desk_cache_count] = desk;
  40.         hashtable_insert(desk_hash, &desk_cache[desk_cache_count], (void*)1);
  41.         desk_cache_count++;
  42. }      
  43.  
  44. char desk_in_cache(desk_t desk)
  45. {
  46.         return hashtable_search(desk_hash, &desk) != NULL;
  47. }      
  48.  
  49. void desk_clone(desk_t desk, desk_t* rotate, desk_t* fliphor, desk_t* flipvert)
  50. {
  51.         int    col = 0;
  52.         int    row;
  53.         *rotate = *fliphor = *flipvert = 0;
  54.         for (row = 0; row < desk_size; row++)
  55.         {
  56.                 col = (desk >> (row * 4)) & 0xf;
  57.                 *rotate   = desk_set_pos(*rotate, row, desk_size - col - 1);
  58.                 *fliphor  = desk_set_pos(*fliphor, desk_size - col - 1, row);
  59.                 *flipvert = desk_set_pos(*flipvert, col, desk_size - row - 1);
  60.         }
  61. }
  62.  
  63. void desk_print(desk_t desk)
  64. {
  65.         int row;
  66.         for (row = 0; row < desk_size; row++)
  67.         {
  68.                 int col = (int)((desk >> (row * 4)) & 0xf);
  69.                 int i = 0;
  70.                 for (i = 0; i < col; i++)
  71.                         printf(".");
  72.                 printf(";");
  73.                 i++;
  74.                 for (;i < desk_size; i++)
  75.                         printf(".");
  76.                 printf("\n");
  77.         }
  78. }
  79.  
  80. void solve(desk_t desk, int row)
  81. {
  82.         int    col;
  83.         desk_t clone;
  84.         desk_t _clone;
  85.         desk_t fliphor;
  86.         desk_t flipvert;
  87.         int    i;
  88.  
  89.         if (row == desk_size)
  90.         {
  91.                 if (!desk_in_cache(desk))
  92.                 {
  93.                         solution_count++;
  94.                         if (!(solution_count % 1000))
  95.                                 printf("\r%d", solution_count);
  96.                         desk_clone(desk, &clone, &fliphor, &flipvert);
  97.                         clone = desk;
  98.  
  99.                         for(i=0;i<3;i++) {
  100.                                 desk_save_cache(clone);
  101.                                 desk_save_cache(fliphor);
  102.                                 desk_save_cache(flipvert);
  103.            
  104.                                 _clone = clone;
  105.                                 desk_clone(_clone, &clone, &fliphor, &flipvert);
  106.                         }
  107.  
  108.                         desk_save_cache(clone);
  109.                         desk_save_cache(fliphor);
  110.                         desk_save_cache(flipvert);
  111.                 }
  112.         } else
  113.         {
  114.                 for (col = 0; col < desk_size; col++)
  115.                 {
  116.                         if (!verts[col] && !diags1[row - col + (desk_size - 1)] && !diags2[row + col])
  117.                         {
  118.                         verts[col] = diags1[row - col + (desk_size - 1)] = diags2[row + col] = 1;
  119.                                 solve(desk_set_pos(desk, col, row), row + 1);
  120.                         verts[col] = diags1[row - col + (desk_size - 1)] = diags2[row + col] = 0;
  121.                         }
  122.                 }
  123.         }
  124. }
  125.  
  126. int main(int argc, char* argv[])
  127. {
  128.         __time64_t start_time;
  129.  
  130.         if (argc != 2)
  131.         {
  132.                 printf("Usage: aqueens <desk size>\n");
  133.                 return 1;
  134.         }
  135.         desk_size = atoi(argv[1]);
  136.         if (desk_size <= 0 || desk_size > 16)
  137.         {
  138.                 printf("invalid desk size\n");
  139.                 return 1;
  140.         }
  141. //      desk_hash = create_hashtable(2000000, desk_hash_from_key, desk_keys_equal);
  142.         desk_hash = create_hashtable(2850000, desk_hash_from_key, desk_keys_equal);
  143.         start_time = _time64(NULL);
  144.         solve(0, 0);
  145.         printf("\ntotal solutions %d in %d seconds.\n", solution_count, _time64(NULL) - start_time);
  146. //      printf("desk_cache_count = %d \n", desk_cache_count);
  147.         return 0;
  148. }


результат запуска на компьютере с процессором Intel Core 2 Duo 2,6 Ггц, 4 Гбайт памяти, ОС Виста, транслировалось Microsoft Vidual studio 2005 SP1
code text
  1. c:\TEMP\1>aqueens 16
  2. 1846000
  3. total solutions 1846955 in 110 seconds.


программа использует 900 МБайт памяти
итого монжо заключить что однопоточная сишная реализация работает быстрее чем многопоточная реализация на яве, использует меньше памяти, а также имеет более короткий исходный текст ... собственно многопоточную реализацию мобыть ещё осилю ... ну и оптимизации различные конечно можно проводить, собственно пока код без оптимизаций, тупо переписывание ...
 
RU anonymous_lor #07.07.2008 11:07
+
-
edit
 

anonymous_lor

новичок

попробовал у себя же на машине Java-реализацию, вот что получилось
code text
  1. E:\aqueens_java>java -version
  2. java version "1.6.0"
  3. Java(TM) SE Runtime Environment (build 1.6.0-b105)
  4. Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode, sharing)
  5.  
  6. E:\aqueens_java>java -Xmx1500m com.ssv.test.samples.queens.EightQueens 16
  7. 16 queens.
  8. Started at:Mon Jul 07 12:59:18 YEKST 2008
  9. Finished at:Mon Jul 07 13:03:33 YEKST 2008, after 255308 ms.
  10. 1846955 solutions found.
  11.  
  12. E:\aqueens_java>java -Xmx1500m com.ssv.test.samples.queens.EightQueens 16 thread
  13. ed
  14. 16 queens.
  15. Started at:Mon Jul 07 13:03:48 YEKST 2008
  16. Finished at:Mon Jul 07 13:06:11 YEKST 2008, after 142841 ms.
  17. 1846955 solutions found.
 

vsb

новичок
Ещё одна реализация на С++: http://vsb.name/files/queen.tar.bz2

В архиве исходник и скомпилированный под i386 бинарник. Компилировать с -DNDEBUG -lboost_thread (и иметь на машине буст 1.34.1). Я собирал gcc 4.2, использовал некоторые нестандартные заголовки из будущего стандарта, поэтому под другие компиляторы может не собраться. Использует многопоточность.
 
RU anonymous_lor #07.07.2008 14:59
+
-
edit
 

anonymous_lor

новичок

что за уродский форум, нафига мне аватарку прилепляют все время, я не хочу аватарку ...
 
RU anonymous_lor #07.07.2008 14:59
+
-
edit
 

anonymous_lor

новичок

vsb, на винде так и не скомпилилось :(, ты хоть результаты работы выложи ...
 
KZ vsb #07.07.2008 15:03  @anonymous_lor#07.07.2008 14:59
+
-
edit
 

vsb

новичок
anonymous_lor> vsb, на винде так и не скомпилилось :(, ты хоть результаты работы выложи ...

На моей машине в 3-4 раза быстрее джавы в среднем. ОК, поставлю VS 2008 Express, портирую :)
 
RU anonymous_lor #07.07.2008 15:04
+
-
edit
 

anonymous_lor

новичок

в 3-4 ... фигасе ... у меня C-шная реализация всего в 2,5 раза быстрее ... чтоже, у тебя ещё быстрей получилось ? ...
 
1 2 3 4 5 6 7 29

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru