Форумы » Наука и техника » Компьютерный » Программирование » Что, господа суровые С++ программисты, поспорим…
[image]

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

Теги:Java, задачи, компьютеры, программирование
 
Новый опрос Новый фотосет Новая тема Написать сообщение в тему
1 2 3 4 5 6 7 … 29
DE Eretik #13.05.2008 18:46  @Сергей-4030#13.05.2008 18:34
+
-
edit
 

Eretik

втянувшийся
☆
Eretik>> От этого работающий на конвейере буратино гуру не становится. А вот в кустарной кузнице может и стать.
Сергей-4030> Ну да. Великий гуру в производстве гвоздей для подков. И самих подков.
Всяк лучше, чем рабочий на конвейере. Да еще и сам себе хозяин. Опуститься до уровня рабочего на конвейере всегда успеется.
   
US Сергей-4030 #13.05.2008 18:49  @Сергей-4030#13.05.2008 18:31
+
-
edit
 

Сергей-4030

исключающий третье
★★
Balancer>> Решение на Питоне: Tiobe: Си++ уступил PHP! :D [Balancer#13.05.08 18:09]
Balancer>> Не ради скоростных параметров, а для практики, надо понемногу и на нём учиться писать :D
Сергей-4030> А время в чем там? В миллисекундах? Тогда Питон побивает Джаву влет, у Джавы на 12 ферзях на моем компьютере 280 ms.

Не, только что посмотрел, time() возвращает время в секундах. Тогда что-то очень долго, где-то провал.

PS Зря текст дал, теперь Еретик перепишет на C++ и будет говорить, что сам написал. ;) Впрочем, если уже один фиг опубликован результат, я свой тоже опубликую.
   
DE Eretik #13.05.2008 18:53  @Сергей-4030#13.05.2008 18:49
+
-
edit
 

Eretik

втянувшийся
☆
Сергей-4030> PS Зря текст дал, теперь Еретик перепишет на C++ и будет говорить, что сам написал. ;)
Ни за что в жизни я вам ничего не напишу! ;)

Сергей-4030> Впрочем, если уже один фиг опубликован результат, я свой тоже опубликую.
Ни в коем разе! Я может передумаю! Ааааааа!
   
US Сергей-4030 #13.05.2008 18:56
+
-
edit
 

Сергей-4030

исключающий третье
★★
Главный модуль.

code java
  1. package com.ssv.test.samples.queens;
  2.  
  3. import java.io.IOException;
  4. import java.util.Date;
  5.  
  6. public class EightQueens {
  7.             static void log(String s) {
  8.                         if (log)
  9.                                     System.out.println(s);
  10.             }
  11.  
  12.             static int log2(int i) {
  13.                         int count = 0;
  14.                         i--;
  15.                         do {
  16.                                     i = i / 2;
  17.                                     count++;
  18.                         } while (i > 0);
  19.                         return count;
  20.             }
  21.  
  22.             static int power2(int x) {
  23.                         int count = 1;
  24.                         for (int i = 0; i < x; i++)
  25.                                     count *= 2;
  26.                         return count;
  27.             }
  28.  
  29.             static boolean threaded = false;
  30.             static boolean first = false;
  31.             static boolean log = false;
  32.             static boolean print = false;
  33.             static boolean wait = false;
  34.             static boolean nocheck = false;
  35.             static int size = 12;
  36.  
  37.             private static void parseParameters(String args[]) {
  38.                         for (int i = 0; i < args.length; i++) {
  39.                                     if (args[i].equalsIgnoreCase("threaded"))
  40.                                                 threaded = true;
  41.                                     else if (args[i].equalsIgnoreCase("first"))
  42.                                                 first = true;
  43.                                     else if (args[i].equalsIgnoreCase("log"))
  44.                                                 log = true;
  45.                                     else if (args[i].equalsIgnoreCase("print"))
  46.                                                 print = true;
  47.                                     else if (args[i].equalsIgnoreCase("wait"))
  48.                                                 wait = true;
  49.                                     else if (args[i].equalsIgnoreCase("nocheck"))
  50.                                                 nocheck = true;
  51.                                     else {
  52.                                                 try {
  53.                                                             size = Integer.parseInt(args[i]);
  54.                                                 } catch (NumberFormatException e) {
  55.                                                             System.out.println("Invalid argument:" + args[i]);
  56.                                                 }
  57.                                     }
  58.  
  59.                                     if (first) {
  60.                                                 threaded = false;
  61.                                                 print = true;
  62.                                     }
  63.                         }
  64.             }
  65.  
  66.             public static void main(String args[]) {
  67.                         Date begin = new Date();
  68.                         parseParameters(args);
  69.                         System.out.println("" + size + " queens.");
  70.                         System.out.println("Started at:" + begin);
  71.                         int solution_size = (!threaded) ? Solution.solveSingle(size, first, ! nocheck)
  72.                                                 : Solution.solve(size, ! nocheck);
  73.                         Date finish = new Date();
  74.                         System.out.println("Finished at:" + finish + ", after "
  75.                                                 + (finish.getTime() - begin.getTime()) + " ms.");
  76.                         System.out.println("" + solution_size + " solutions found.");
  77.                         if (print)
  78.                                     for (int i=0;i<solution_size;i++) {
  79.                                                 System.out.println(Desk.toString(Solution.solutions[i]));
  80.                                     }
  81.                         if (wait)
  82.                                     try {
  83.                                                 System.in.read();
  84.  
  85.                                     } catch (IOException e) {
  86.                                                 e.printStackTrace();
  87.                                     }
  88.             }
  89. }


Модуль Desk

code java
  1. package com.ssv.test.samples.queens;
  2.  
  3. import java.text.DecimalFormat;
  4. import java.text.Format;
  5.  
  6. class Desk {
  7.             static int pos(long body, int y) {
  8.                         return (int)
  9.                            ((body >> (y*Solution.BITS_PER_CELL)) & Solution.FILL_MASK);
  10.             }
  11.  
  12.             static long setPos(long body, int x, int y) {
  13.                         return body | (((long)x) << (y*Solution.BITS_PER_CELL));
  14.             }                      
  15.  
  16.             public static long cloneRotate(long body) {
  17.                         long nb=0;
  18.                         for(int y=0;y<Solution.SIZE;y++) {
  19.                                     int x=pos(body, y);
  20.                                     nb=setPos(nb, y, Solution.SIZE-x-1);                            
  21.                         }
  22.                         return nb;
  23.             }
  24.  
  25.             public static long cloneFlipHor(long body){
  26.                         long nb=0;
  27.                         for(int y=0;y<Solution.SIZE;y++) {
  28.                                     int x=pos(body, y);
  29.                                     nb=setPos(nb, Solution.SIZE-x-1, y);
  30.                         }
  31.                         return nb;
  32.             }
  33.  
  34.             public static long cloneFlipVert(long body){
  35.                         long nb=0;
  36.                         for(int y=0;y<Solution.SIZE;y++) {
  37.                                     int x=pos(body, y);
  38.                                     nb=setPos(nb, x,Solution.SIZE-y-1);
  39.                         }
  40.                         return nb;
  41.             }
  42.  
  43.     static String line(int numspaces) {
  44.             StringBuffer sb=new StringBuffer();
  45.         for (int i = 0; i < numspaces; i++)
  46.             sb.append("  ");
  47.         sb.append("FF\n");
  48.         return sb.toString();
  49.     }                      
  50.  
  51.     public static String toString(long body) {
  52.             StringBuffer sb=new StringBuffer();
  53.             sb.append("  ");
  54.         for (int i = 0; i < Solution.SIZE; i++)
  55.             sb.append("--");
  56.         sb.append("\n");
  57.         Format f = new DecimalFormat("00");
  58.         for (int y = 0; y < Solution.SIZE; y++) {
  59.             sb.append("" + f.format(Solution.SIZE - y) + " ");
  60.             sb.append(line(pos(body,y)));
  61.         }
  62.  
  63.         sb.append("  ");
  64.         int ch='A';
  65.         for(int i=0;i<Solution.SIZE;i++) {
  66.             sb.append(" ");
  67.             sb.append((char)(ch+i));
  68.         }
  69.  
  70.         sb.append("\n");
  71.         sb.append("  ");
  72.         for (int i = 0; i < Solution.SIZE; i++)
  73.             sb.append("--");
  74.         sb.append("\n");
  75.         return sb.toString();
  76.     }
  77. }


Модуль Solution

code java
  1. package com.ssv.test.samples.queens;
  2.  
  3. import java.util.HashSet;
  4. import java.util.Set;
  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 int solve(final int size, boolean checkTransitions) {
  24.  
  25.                 setLimits(size, false, checkTransitions);
  26.                 known_positions.clear();
  27.                 solution_pointer = 0;
  28.  
  29.                 Thread solutionThreads[] = new Thread[size];
  30.                 for (int i = 0; i < size; i++) {
  31.                         solutionThreads[i] = new SolutionThread(i);
  32.                         solutionThreads[i].start();
  33.                 }
  34.  
  35.                 try {
  36.                         for (int i = 0; i < size; i++) {
  37.                                 solutionThreads[i].join();
  38.                         }
  39.  
  40.                 } catch (InterruptedException e) {
  41.                 }
  42.  
  43.                 return solution_pointer;
  44.         }
  45.  
  46.         public static int solveSingle(final int size, boolean first,
  47.                         boolean checkTransitions) {
  48.                 setLimits(size, first, checkTransitions);
  49.                 known_positions.clear();
  50.                 solution_pointer = 0;
  51.                 (new Solution()).arrange();
  52.                 return solution_pointer;
  53.  
  54.         }
  55.  
  56.         static private void setLimits(int size, boolean first, boolean check) {
  57.                 SIZE = size;
  58.                 BITS_PER_CELL = EightQueens.log2(SIZE);
  59.                 FILL_MASK = EightQueens.power2(BITS_PER_CELL) - 1;
  60.  
  61.                 EightQueens.log("SIZE=" + SIZE);
  62.                 EightQueens.log("BITS_PER_CELL=" + BITS_PER_CELL);
  63.                 EightQueens.log("FILL_MASK=" + FILL_MASK);
  64.  
  65.                 FIRST_ONLY = first;
  66.                 CHECK_TRANSITIONS = check;
  67.         }
  68.  
  69.         public Solution() {
  70.                 desk = 0;
  71.         }
  72.  
  73.         public Solution(int partialSolution) {
  74.                 this();
  75.                 addQueen(partialSolution);
  76.         }
  77.  
  78.         long stack[] = new long[SIZE];
  79.         int sp = 0;
  80.  
  81.         private boolean addQueen(int pos) {
  82.                 if (verts[pos])
  83.                         return false;
  84.  
  85.                 if (diags1[currentLine - pos + (SIZE - 1)])
  86.                         return false;
  87.  
  88.                 if (diags2[currentLine + pos])
  89.                         return false;
  90.  
  91.                 stack[sp++] = desk;
  92.                 desk = Desk.setPos(desk, pos, currentLine);
  93.  
  94.                 verts[pos] = diags1[currentLine - pos + (SIZE - 1)] = diags2[curr
   
US Сергей-4030 #13.05.2008 18:59  @Eretik#13.05.2008 18:53
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>> PS Зря текст дал, теперь Еретик перепишет на C++ и будет говорить, что сам написал. ;)
Eretik> Ни за что в жизни я вам ничего не напишу! ;)
Сергей-4030>> Впрочем, если уже один фиг опубликован результат, я свой тоже опубликую.
Eretik> Ни в коем разе! Я может передумаю! Ааааааа!

Да с вами, собственно, уже все ясно.
   
US Сергей-4030 #13.05.2008 19:01
+
-
edit
 

Сергей-4030

исключающий третье
★★
Кстати, только заметил - забыл лишнюю синхронизацию убрать в arrange, которая по solutions. Ну да ладно.
   
RU Balancer #13.05.2008 19:04  @Сергей-4030#13.05.2008 18:31
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> А время в чем там? В миллисекундах?

Нет, в секундах :D А проигрышь Яве при прочих равных в этих условиях должен быть раз в 5..10, наверное.
   
RU Balancer #13.05.2008 19:07  @Сергей-4030#13.05.2008 18:49
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> PS Зря текст дал, теперь Еретик перепишет на C++ и будет говорить, что сам написал. ;)

Что-то мне подсказывает, что он не осилит его. По крайней мере быстро и эффективно. Например, хотя бы потому, что там используются две питоновских фишки, которых в Си нет - ассоциативные массивы и целочисленные вычисления с нелимитированной точностью (у меня же там битовые маски размером с разрадностью в число клеток на поле).
   
RU Balancer #13.05.2008 19:09
+
-
edit
 

Balancer

администратор
★★★★★
Зато я решил по проколу Питоновскую программу на D переложить. Даже "Hello, world" на этом языке не писал :) Копаюсь сейчас в Интернете, ищу работу с динамическими многомерными массивами. А битовые массивы решил заменить на динамические массивы char'ов :)
   
US Сергей-4030 #13.05.2008 19:17  @Balancer#13.05.2008 19:04
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>> А время в чем там? В миллисекундах?
Balancer> Нет, в секундах :D А проигрышь Яве при прочих равных в этих условиях должен быть раз в 5..10, наверное.

Похоже, повороты слишком много времени отнимают.
   
US Сергей-4030 #13.05.2008 19:21
+
-
edit
 

Сергей-4030

исключающий третье
★★
И еще - решения хранятся неоптимально, много лишних разрядов, может поэтому вычисления поворотов так долго? У тебя получается 1 бит на одну клетку, что сильно избыточно.
   
US Сергей-4030 #13.05.2008 19:23
+
-
edit
 

Сергей-4030

исключающий третье
★★
Кстати, треды помогают довольно прилично, раза в полтора быстрее, если на нескольких тредах делать (конечно, выигрыш только если процессор многоядерный). Не хочешь разбить на треды? Полезное упражнение в Питоне. ;)
   
UA Murkt #13.05.2008 19:28  @Balancer#13.05.2008 19:04
+
-
edit
 

Murkt

Pythoneer
☆
Сергей-4030>> А время в чем там? В миллисекундах?
Balancer> Нет, в секундах :D А проигрышь Яве при прочих равных в этих условиях должен быть раз в 5..10, наверное.
Откуда такие цифры? Раз в 50-100 должно быть медленнее, это ж просто исполнение питоновского кода без единой оптимизации.
   
US Сергей-4030 #13.05.2008 19:35  @Murkt#13.05.2008 19:28
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>>> А время в чем там? В миллисекундах?
Balancer>> Нет, в секундах :D А проигрышь Яве при прочих равных в этих условиях должен быть раз в 5..10, наверное.
Murkt> Откуда такие цифры? Раз в 50-100 должно быть медленнее, это ж просто исполнение питоновского кода без единой оптимизации.

В любом случае, получается target = 14-28 секунд. А особо оптимизировать там и нечего. Массив ассоциативный наверняка внутри пооптимизирован. Остаются, имхо, сами повороты (не проверка на существующий результат, а сами повороты). Я свои соображения по поводу того, где может быть затык в поворотах, высказал. :)
Кстати еще, в transformed_results не имеет смысла хранить сами значения получившихся решений, достаточно хранить хэш-код какой-нибудь.
   
US Сергей-4030 #13.05.2008 19:37
+
-
edit
 

Сергей-4030

исключающий третье
★★
На самом деле, наверняка очень помогли бы MMX-инструкции, повороты делать. Вот они, действительно, могли бы привести C++ на суперпервое место. С другой стороны, можно подключить какую-нибудь native библиотеку под это дело.
   
UA Murkt #13.05.2008 19:40  @Сергей-4030#13.05.2008 19:35
+
-
edit
 

Murkt

Pythoneer
☆
Сергей-4030> Остаются, имхо, сами повороты (не проверка на существующий результат, а сами повороты). Я свои соображения по поводу того, где может быть затык в поворотах, высказал. :)
Сергей-4030> Кстати еще, в transformed_results не имеет смысла хранить сами значения получившихся решений, достаточно хранить хэш-код какой-нибудь.
Я ни твой код, ни код Балансера не смотрел, так что ничего сказать не могу. Меня такие задачки просто не привлекают.
   
US Сергей-4030 #13.05.2008 20:05
+
-
edit
 

Сергей-4030

исключающий третье
★★
Кстати, просьба не бить за методы типа

static int pos(long body, int y)

Изначально это было

int pos(int y)

но оказалось, что со статическими функциями быстрее выходит процентов на 10, надо думать потому как разыменовывать указатель на this не надо.
   
RU Balancer #13.05.2008 20:22
+
-
edit
 

Balancer

администратор
★★★★★
На D вариант готов. Для доски 14x14 считает 21 секунду. Для 16x16 сейчас запустил, посмотрим. Но, боюсь, результата ждать долго :) Т.к. 13x13 он считает за 3 секунды, а 12x12 за 0.6 сек... Такими темпами он 16x16 может считать минут десять...

[D] Balancer - Pastebin.com

// pastebin.com
 


За код просьба не пинать, я на Ди пишу впервые в жизни :D
   
RU Balancer #13.05.2008 20:24  @Сергей-4030#13.05.2008 19:17
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> Похоже, повороты слишком много времени отнимают.

Не-а, они запоминаются только когда найдено решение. А это редко бывает. Профайлер показывает, что основное время - основной цикл, рекурсивная функция queens(). Там же по факту выходит 2^N вложенных циклов, где N - разрядность доски. И всё в одной функции. Потом уже, но с небольшим отставанием идёт setup и clean. А вот set_result, который и прописывает все ротации, вызывается редко.
   
RU Balancer #13.05.2008 20:25  @Сергей-4030#13.05.2008 19:21
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> И еще - решения хранятся неоптимально, много лишних разрядов, может поэтому вычисления поворотов так долго? У тебя получается 1 бит на одну клетку, что сильно избыточно.

Угу. Но я же говорю, это первое решение, которое в голову пришло :)
   
RU Balancer #13.05.2008 21:00
+
-
edit
 

Balancer

администратор
★★★★★
Ы. 25 минут вычислений при загрузке процессора в 60..80% и сожрано 1.3ГБ оперативки... При этом, заказов памяти кроме обычной рекурсии нет. Выходит, столько рекурсий накрутилось...
   
US Сергей-4030 #13.05.2008 21:19  @Balancer#13.05.2008 21:00
+
-
edit
 

Сергей-4030

исключающий третье
★★
Balancer> Ы. 25 минут вычислений при загрузке процессора в 60..80% и сожрано 1.3ГБ оперативки... При этом, заказов памяти кроме обычной рекурсии нет. Выходит, столько рекурсий накрутилось...

Ну конечно. ;) А results_transformed забыл? Представляешь, сколько туда мусора набилось? Не говоря о просто results. Кстати, а сколько решений получилось? У нас одинаковые ответы получаются?

PS Треды наверняка помогут сократить до ~15 минут время выполнения.
   
US Сергей-4030 #13.05.2008 21:22
+
-
edit
 

Сергей-4030

исключающий третье
★★
Рекурсия, кстати, слезы - чего там, 16 уровней, в стеке было максимум 54 вызова. Даже если бы параметры в стеке передавались - слезы, никаких гигабайтов и близко нет. А там наверняка только ссылки в стеке.
   
RU Balancer #13.05.2008 21:36  @Сергей-4030#13.05.2008 21:19
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> Ну конечно. ;) А results_transformed забыл?

Ай, блин. У меня в памяти только число решений тобой приведённое отложилось, по нему нормально выходит. А с этими, да её с учётом того, что я строками запоминаю :D Надо попробовать с битовыми массивами поиграть. А то оно уже 1.8Гб сожрало :)

Сергей-4030> Представляешь, сколько туда мусора набилось? Не говоря о просто results.

results - небольшой (относительно).

Сергей-4030> Кстати, а сколько решений получилось? У нас одинаковые ответы получаются?

16x16 не досчиталось ещё. Для 8x8 было верно. Для 12x12 я приводил.

Сергей-4030> PS Треды наверняка помогут сократить до ~15 минут время выполнения.

У меня процессор ещё одноядерный :)
   
RU Balancer #13.05.2008 21:41  @Сергей-4030#13.05.2008 21:22
+
-
edit
 

Balancer

администратор
★★★★★
Сергей-4030> Рекурсия, кстати, слезы - чего там, 16 уровней, в стеке было максимум 54 вызова.

Уровень - фигня. Вот общее число вызовов. Для 8 клеток:

max_level = 7
rec_count = 1965

Для 12:

max_level = 11
rec_count = 841989

Для 14:

max_level = 13
rec_count = 26992957

Я с этим на тестах рекурсивного Аккермана сталкивался. Уровень вложений не высокий, но много "ждущих" вызовов. И при передаче всего трёх int'ов на их значениях, типа (3,8,8) уже полумегабайта оперативки не хватает. Одни только вызовы...
   
1 2 3 4 5 6 7 … 29

в начало страницы | новое
Форумы » Наука и техника » Компьютерный » Программирование » Что, господа суровые С++ программисты, поспорим…
Copyright © Balancer 1997..2020
Создано 06.02.2008
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru