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

...
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 в Си и в Питоне. Типа, продолжается троллинг?

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

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

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.

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

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%. Интересно насколько ускорится, если избавиться от постоянного распределение памяти при входе в процедуры ? Здесь это сделать возможно, потому как глубина вызовов равна размеру доски. Только все это пробовать в яве не стоит.

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

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. }

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. }

Вообще, addKnownPosition вряд ли имеет смысл особо править - редко вызывается, не имеет смысла. arrange, addQueen, removeQueen - вот куда следует смотреть. М.б. стоит переопределить хэш-функцию и написать свою реализацию хэш-массива. Наверняка развертка рекурсии в код даст хороший выигрыш.

И еще, конечно, синхронизация. У меня мультипотоковость сделана достаточно наивно - времени тратить не хотелось. Поэтому до 40% времени проводим в wait(). Вот тут точно поле для улучшения непаханое. Я бы сказал, при правильной организации потоков те самые 40% в скорости и отыграются.

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

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

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

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

1. c:\TEMP\1>aqueens 16
2. 1846000
3. total solutions 1846955 in 110 seconds.

программа использует 900 МБайт памяти
итого монжо заключить что однопоточная сишная реализация работает быстрее чем многопоточная реализация на яве, использует меньше памяти, а также имеет более короткий исходный текст ... собственно многопоточную реализацию мобыть ещё осилю ... ну и оптимизации различные конечно можно проводить, собственно пока код без оптимизаций, тупо переписывание ...

попробовал у себя же на машине Java-реализацию, вот что получилось

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.

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

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

что за уродский форум, нафига мне аватарку прилепляют все время, я не хочу аватарку ...

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

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