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

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

Теги:Java, задачи, компьютеры, программирование
 
Новый опрос Новый фотосет Новая тема Написать сообщение в тему
1 … 4 5 6 7 8 … 29
KZ vsb #07.07.2008 15:09  @anonymous_lor#07.07.2008 15:04
+
-
edit
 

vsb

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

Во-первых она мультитредовая. Во-вторых я алгоритм поиска позиций немного улучшил. В-третьих С не быстрее С++ :)
 
RU anonymous_lor #07.07.2008 15:16
+
-
edit
 

anonymous_lor

новичок

ну так ты мультитредовую с мультитредовой явной сравнивай ...

хм ... посмотрел текст - точна ... у тебя функция solve - главная функция алгоритма нерекурсивная ... скорей всего это как раз и дает огромный плюс ...
 
RU anonymous_lor #07.07.2008 15:18
+
-
edit
 

anonymous_lor

новичок

в профайлере у меня как раз чаще вего идет вызов этой функции solve и цикл по клеткам там где смотрится что они свободные ...
вот надо делать мультитредность и нерекурсивность ...
 
KZ vsb #07.07.2008 15:20  @anonymous_lor#07.07.2008 15:16
+
-
edit
 

vsb

новичок
anonymous_lor> ну так ты мультитредовую с мультитредовой явной сравнивай ...

Я и сравниваю. Если один тред пускать и там и там, получается раза в 3 выигрыш. Если 2 треда, получается в 4 :) На джаве она как то плохо масштабируется, у меня лучше, хоть и прикручено ржавыми гвоздями. Очень интересно посмотреть на четырёх процессорах, но нет такого железа под рукой.

anonymous_lor> хм ... посмотрел текст - точна ... у тебя функция solve - главная функция алгоритма нерекурсивная ... скорей всего это как раз и дает огромный плюс ...

Огромный плюс даёт массив free_verticals, на самом деле. Ну нерекурсивность тоже помогает.

Впрочем я тестировал какой то старый вариант на Java, если сегодня скачаю VS, потестирую последний выложенный.
 
RU anonymous_lor #07.07.2008 15:27
+
-
edit
 

anonymous_lor

новичок

> Очень интересно посмотреть на четырёх процессорах, но нет такого железа под рукой.

я думаю смогу где-то посмотреть на 4-х и даже 8-ми процессорах ... но скорей всего завтра ...
 
RU anonymous_lor #07.07.2008 15:28
+
-
edit
 

anonymous_lor

новичок

free_verticals конечно тоже хорошо, но имхо здесь как раз нерекурсивность решает ...
 
KZ vsb #07.07.2008 15:32  @anonymous_lor#07.07.2008 15:28
+
-
edit
 

vsb

новичок
anonymous_lor> free_verticals конечно тоже хорошо, но имхо здесь как раз нерекурсивность решает ...

Введение free_verticals ускорило алгоритм примерно в 2 раза :) Правда это было ещё в первой версии, где массив задавался константой и компилятор разворачивал кучу циклов. Надо будет тот вариант реанимировать, кстати, хоть и не совсем честно, зато он жутко быстрый.
 
UA Maverik #07.07.2008 21:30
+
-
edit
 

Maverik

новичок
76 секунд на Атлоне 2ГГц, памяти 540Мб в пике.
code cpp
  1. #include <stdio.h>
  2. #include <glib.h>
  3.  
  4. #define A 16
  5. #define B 16
  6. #define N 16
  7.  
  8. gboolean equal(char *p1, char *p2) {
  9.   int i;
  10.   for (i = 0; i<N; i+=1) {
  11.     if (p1[i]!=p2[i]) {
  12.       return 0;
  13.     }
  14.   }
  15.   return 1;
  16. }
  17.  
  18. int main() {
  19.   int i, j, k, p, pi;
  20.  
  21.   char POZA[N+1], Z[B+1], *r;
  22.   char *new_poza[8];
  23.   int VOS[B+A-1], ZAK[B+A-1];
  24.   GHashTable *results = g_hash_table_new(g_str_hash, equal);
  25.  
  26.   POZA[N] = 0;
  27.   for (k = 0; k<=B; k+=1) { Z[k] = k+1; }
  28.   for (k = 1-A; k<B; k+=1) { VOS[k+A-1] = 0; }
  29.   for (k = 2; k<=B+A; k+=1) { ZAK[k-2] = 0; }
  30.   i = k = 0;
  31.  
  32.  PER: i += 1; if (i>N) { goto ZAP; } p = 0;
  33.  BOK: j = p; p = Z[j]; if (p>N) { goto ZAD; }
  34.  PRV: if (VOS[p-i+A-1] || ZAK[p+i-2]) { goto BOK; }
  35.  PRP: VOS[p-i+A-1] = ZAK[p+i-2] = 1;
  36.   Z[j] = Z[p]; Z[p] = j; POZA[i-1] = p;
  37.   goto PER;
  38.  
  39.  ZAP:
  40.   if (!(r = g_hash_table_lookup(results, POZA))) {
  41.     k += 1;
  42.     new_poza[0] = (char *)malloc(N+1);
  43.     new_poza[1] = (char *)malloc(N+1);
  44.     new_poza[2] = (char *)malloc(N+1);
  45.     new_poza[3] = (char *)malloc(N+1);
  46.     new_poza[4] = (char *)malloc(N+1);
  47.     new_poza[5] = (char *)malloc(N+1);
  48.     new_poza[6] = (char *)malloc(N+1);
  49.     new_poza[7] = (char *)malloc(N+1);
  50.     for (pi=0; pi<N; pi+=1) {
  51.       new_poza[0][pi] = POZA[pi];
  52.       new_poza[1][N-1-pi] = POZA[pi];
  53.       new_poza[2][pi] = N+1-POZA[pi];
  54.       new_poza[3][N-1-pi] = N+1-POZA[pi];
  55.       new_poza[4][POZA[pi]-1] = pi+1;
  56.       new_poza[5][N-POZA[pi]] = pi+1;
  57.       new_poza[6][POZA[pi]-1] = N-pi;
  58.       new_poza[7][N-POZA[pi]] = N-pi;
  59.     }
  60.     new_poza[0][N] = 0;
  61.     new_poza[1][N] = 0;
  62.     new_poza[2][N] = 0;
  63.     new_poza[3][N] = 0;
  64.     new_poza[4][N] = 0;
  65.     new_poza[5][N] = 0;
  66.     new_poza[6][N] = 0;
  67.     new_poza[7][N] = 0;
  68.     g_hash_table_insert(results, new_poza[0], new_poza[0]);
  69.     g_hash_table_insert(results, new_poza[1], new_poza[1]);
  70.     g_hash_table_insert(results, new_poza[2], new_poza[2]);
  71.     g_hash_table_insert(results, new_poza[3], new_poza[3]);
  72.     g_hash_table_insert(results, new_poza[4], new_poza[4]);
  73.     g_hash_table_insert(results, new_poza[5], new_poza[5]);
  74.     g_hash_table_insert(results, new_poza[6], new_poza[6]);
  75.     g_hash_table_insert(results, new_poza[7], new_poza[7]);
  76.   }
  77.  
  78.  ZAD: i -= 1; if (i==0) { goto VSJO; }
  79.  VYP: p = POZA[i-1]; j = Z[p]; Z[p] = Z[j]; Z[j] = p;
  80.   VOS[p-i+A-1] = ZAK[p+i-2] = 0;
  81.   goto BOK;
  82.  
  83.  VSJO:
  84.   printf("%d %d\n", g_hash_table_size(results), k);
  85.  
  86.   return 0;
  87. }
 
Это сообщение редактировалось 07.07.2008 в 22:03
UA Maverik #07.07.2008 21:37
+
-
edit
 

Maverik

новичок
Черт, code не работает. Как отформатировать?
 
RU anonymous_lor #07.07.2008 22:01
+
-
edit
 

anonymous_lor

новичок

code работает ... должно форматироваться ...
 
UA Maverik #07.07.2008 22:04  @anonymous_lor#07.07.2008 22:01
+
-
edit
 

Maverik

новичок
anonymous_lor> code работает ... должно форматироваться ...

Отак-от оно форматируется:

code text
  1. #include <stdio.h>
  2. #include <glib.h>
  3.  
  4. #define A 16
  5. #define B 16
  6. #define N 16
  7.  
  8. gboolean equal(char *p1, char *p2) {
  9.   int i;
  10.   for (i = 0; i<N; i+=1) {
  11.     if (p1[i]!=p2[i]) {
  12.       return 0;
  13.     }
  14.   }
  15.   return 1;
  16. }
  17.  
  18. int main() {
  19.   int i, j, k, p, pi;
  20.  
  21.   char POZA[N+1], Z[B+1], *r;
  22.   char *new_poza[8];
  23.   int VOS[B+A-1], ZAK[B+A-1];
  24.   GHashTable *results = g_hash_table_new(g_str_hash, equal);
  25.  
  26.   POZA[N] = 0;
  27.   for (k = 0; k<=B; k+=1) { Z[k] = k+1; }
  28.   for (k = 1-A; k<B; k+=1) { VOS[k+A-1] = 0; }
  29.   for (k = 2; k<=B+A; k+=1) { ZAK[k-2] = 0; }
  30.   i = k = 0;
  31.  
  32.  PER: i += 1; if (i>N) { goto ZAP; } p = 0;
  33.  BOK: j = p; p = Z[j]; if (p>N) { goto ZAD; }
  34.  PRV: if (VOS[p-i+A-1] || ZAK[p+i-2]) { goto BOK; }
  35.  PRP: VOS[p-i+A-1] = ZAK[p+i-2] = 1;
  36.   Z[j] = Z[p]; Z[p] = j; POZA[i-1] = p;
  37.   goto PER;
  38.  
  39.  ZAP:
  40.   if (!(r = g_hash_table_lookup(results, POZA))) {
  41.     k += 1;
  42.     new_poza[0] = (char *)malloc(N+1);
  43.     new_poza[1] = (char *)malloc(N+1);
  44.     new_poza[2] = (char *)malloc(N+1);
  45.     new_poza[3] = (char *)malloc(N+1);
  46.     new_poza[4] = (char *)malloc(N+1);
  47.     new_poza[5] = (char *)malloc(N+1);
  48.     new_poza[6] = (char *)malloc(N+1);
  49.     new_poza[7] = (char *)malloc(N+1);
  50.     for (pi=0; pi<N; pi+=1) {
  51.       new_poza[0][pi] = POZA[pi];
  52.       new_poza[1][N-1-pi] = POZA[pi];
  53.       new_poza[2][pi] = N+1-POZA[pi];
  54.       new_poza[3][N-1-pi] = N+1-POZA[pi];
  55.       new_poza[4][POZA[pi]-1] = pi+1;
  56.       new_poza[5][N-POZA[pi]] = pi+1;
  57.       new_poza[6][POZA[pi]-1] = N-pi;
  58.       new_poza[7][N-POZA[pi]] = N-pi;
  59.     }
  60.     new_poza[0][N] = 0;
  61.     new_poza[1][N] = 0;
  62.     new_poza[2][N] = 0;
  63.     new_poza[3][N] = 0;
  64.     new_poza[4][N] = 0;
  65.     new_poza[5][N] = 0;
  66.     new_poza[6][N] = 0;
  67.     new_poza[7][N] = 0;
  68.     g_hash_table_insert(results, new_poza[0], new_poza[0]);
  69.     g_hash_table_insert(results, new_poza[1], new_poza[1]);
  70.     g_hash_table_insert(results, new_poza[2], new_poza[2]);
  71.     g_hash_table_insert(results, new_poza[3], new_poza[3]);
  72.     g_hash_table_insert(results, new_poza[4], new_poza[4]);
  73.     g_hash_table_insert(results, new_poza[5], new_poza[5]);
  74.     g_hash_table_insert(results, new_poza[6], new_poza[6]);
  75.     g_hash_table_insert(results, new_poza[7], new_poza[7]);
  76.   }
  77.  
  78.  ZAD: i -= 1; if (i==0) { goto VSJO; }
  79.  VYP: p = POZA[i-1]; j = Z[p]; Z[p] = Z[j]; Z[j] = p;
  80.   VOS[p-i+A-1] = ZAK[p+i-2] = 0;
  81.   goto BOK;
  82.  
  83.  VSJO:
  84.   printf("%d %d\n", g_hash_table_size(results), k);
  85.  
  86.   return 0;
  87. }
 
US Сергей-4030 #07.07.2008 22:07  @anonymous_lor#07.07.2008 09:52
+
-
edit
 

Сергей-4030

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

Что и ожидалось. ;) Ну, еще можно заключить, что код на С++ был получен через 6 месяцев после кода на Java и при этом только после того, как этот самый текст на Java был опубликован (т.е. "чисто" сишное решение так и не было представлено). ;)
 
UA Maverik #07.07.2008 22:08
+
-
edit
 

Maverik

новичок

Pastebin.com Unknown Paste ID

// pastebin.com
 

 
US Сергей-4030 #07.07.2008 22:09  @Maverik#07.07.2008 21:30
+
-
edit
 

Сергей-4030

исключающий третье
★★
Maverik> 76 секунд на Атлоне 2ГГц, памяти 540Мб в пике.
Maverik> #include <stdio.h>
Maverik> #include <glib.h>
Maverik> #define A 16
...

Как-то больно уж напряжно читать, может как-нибудь причешете малость? Просто влом по меткам ходить. :(
 
UA Maverik #07.07.2008 22:12  @Сергей-4030#07.07.2008 22:07
+
-
edit
 

Maverik

новичок
Сергей-4030> Ну, еще можно заключить, что код на С++ был получен через 6 месяцев после кода на Java

Фигасе...

Сергей-4030> и при этом только после того, как этот самый текст на Java был опубликован (т.е. "чисто" сишное решение так и не было представлено). ;)

Ну, вот представлено решение, к Яве не имеет ни малейшего отношения, более того, решение на Яве я вообще ниасилил — слишком многа букв.

Кстати, по ходу видел народ в недоумении — goto в Яве, вроде бы, есть, но он, вроде бы, не работает. Как это может быть?
 
UA Maverik #07.07.2008 22:13  @Сергей-4030#07.07.2008 22:09
+
-
edit
 

Maverik

новичок
Сергей-4030> Как-то больно уж напряжно читать, может как-нибудь причешете малость? Просто влом по меткам ходить. :(

Читабельности в условиях не было. Я, вон, тоже все глаза об решение на Яве поломал. И ничо, не жалуюсь...
 
US Сергей-4030 #07.07.2008 22:15
+
-
edit
 

Сергей-4030

исключающий третье
★★
Да кто ж с вас потребует. Просто типа просьба. :)

PS Сохранять "new_posa" в хэш-таблице - избыточно, можно хранить только хэш-код вместо целого массива. Тем более, что хэш-функцию с заведомым отсутствием коллизий в нашем случае написать легко.
 
UA Maverik #07.07.2008 22:18  @Сергей-4030#07.07.2008 22:15
+
-
edit
 

Maverik

новичок
Сергей-4030> PS Сохранять "new_posa" в хэш-таблице - избыточно, можно хранить только хэш-код вместо целого массива.

Хэш-коллизия — штука жутко вредная. Тут лучше бы перебдедь, чем недобдедь.

Сергей-4030> Тем более, что хэш-функцию с заведомым отсутствием коллизий в нашем случае написать легко.

На Яве она есть? Во фрагментец можно тыкнуть?
 
US Сергей-4030 #07.07.2008 22:19  @Maverik#07.07.2008 22:12
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>> Ну, еще можно заключить, что код на С++ был получен через 6 месяцев после кода на Java
Maverik> Фигасе...

Факты, однако.

Сергей-4030>> и при этом только после того, как этот самый текст на Java был опубликован (т.е. "чисто" сишное решение так и не было представлено). ;)
Maverik> Ну, вот представлено решение, к Яве не имеет ни малейшего отношения, более того, решение на Яве я вообще ниасилил — слишком многа букв.

Извините, не поверю. Больно уж кривовато у вас получилось использование хэша - ненатуральненько. ;)

Maverik> Кстати, по ходу видел народ в недоумении — goto в Яве, вроде бы, есть, но он, вроде бы, не работает. Как это может быть?

Да вот так, goto - ключевое слово, но не используется ни в каких конструкциях. Сделано для облегчения жизни при портировании сишных текстов на Джаву.
 
UA Maverik #07.07.2008 22:22  @Сергей-4030#07.07.2008 22:15
+
-
edit
 

Maverik

новичок
Сергей-4030> Да кто ж с вас потребует. Просто типа просьба. :)

Увы... Решение в духе "старой школы" — с блок-схемой в основе...
 
US Сергей-4030 #07.07.2008 22:22  @Maverik#07.07.2008 22:18
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>> PS Сохранять "new_posa" в хэш-таблице - избыточно, можно хранить только хэш-код вместо целого массива.
Maverik> Хэш-коллизия — штука жутко вредная. Тут лучше бы перебдедь, чем недобдедь.
Сергей-4030>> Тем более, что хэш-функцию с заведомым отсутствием коллизий в нашем случае написать легко.
Maverik> На Яве она есть? Во фрагментец можно тыкнуть?

Естественно, есть. В моем тексте позиция представляется одним integer, который одновременно и является значением хэш-функции. Две разные позиции заведомо имеют разные хэш-функции.
 
US Сергей-4030 #07.07.2008 22:23  @Maverik#07.07.2008 22:22
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>> Да кто ж с вас потребует. Просто типа просьба. :)
Maverik> Увы... Решение в духе "старой школы" — с блок-схемой в основе...

Читать больно уж тяжко. Тем более, экономятся-то на вызовах копейки, по большому счету.
 
UA Maverik #07.07.2008 22:25  @Сергей-4030#07.07.2008 22:19
+
-
edit
 

Maverik

новичок
Сергей-4030>>> Ну, еще можно заключить, что код на С++ был получен через 6 месяцев после кода на Java
Maverik>> Фигасе...
Сергей-4030> Факты, однако.

Какие факты?! Это ничо, что представленное решение было сделано задолго до решения на Яве? Вообще тогда, когда Явы еще в проекте не было?

Maverik>> Ну, вот представлено решение, к Яве не имеет ни малейшего отношения, более того, решение на Яве я вообще ниасилил — слишком многа букв.
Сергей-4030> Извините, не поверю. Больно уж кривовато у вас получилось использование хэша - ненатуральненько. ;)

Да, хэш навесил сам, но тут уже свойство предметной области. Хэши ведь отнюдь не в Яве впервые появились.
 
US Сергей-4030 #07.07.2008 22:28  @Maverik#07.07.2008 22:25
+
-
edit
 

Сергей-4030

исключающий третье
★★
Сергей-4030>>>> Ну, еще можно заключить, что код на С++ был получен через 6 месяцев после кода на Java
Maverik> Maverik>> Фигасе...
Сергей-4030>> Факты, однако.
Maverik> Какие факты?! Это ничо, что представленное решение было сделано задолго до решения на Яве? Вообще тогда, когда Явы еще в проекте не было?

Нигде на задокументировано. ;) А Джавовское - задокументировано в топике. Да вы не принимайте близко к сердцу.

Maverik> Maverik>> Ну, вот представлено решение, к Яве не имеет ни малейшего отношения, более того, решение на Яве я вообще ниасилил — слишком многа букв.
Сергей-4030>> Извините, не поверю. Больно уж кривовато у вас получилось использование хэша - ненатуральненько. ;)
Maverik> Да, хэш навесил сам, но тут уже свойство предметной области. Хэши ведь отнюдь не в Яве впервые появились.

То есть, хэш все-таки появился после представления Балансерова и моего вариантов? ;) Так, или не так?
 
UA Maverik #07.07.2008 22:28  @Сергей-4030#07.07.2008 22:23
+
-
edit
 

Maverik

новичок
Сергей-4030> Читать больно уж тяжко. Тем более, экономятся-то на вызовах копейки, по большому счету.

Ну, про "копейки" мы тут уже шестую страницу смотрим. А "на вызовах" сам алгоритм поломаться может.
 
1 … 4 5 6 7 8 … 29

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