Форум программистов, компьютерный форум CyberForum.ru

Задача поиска множественных путей в графе - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Преобразование hwnd в int http://www.cyberforum.ru/cpp-beginners/thread1494031.html
Знаю что тема уже заезжена и полно подобных обсуждений, но не смог применить к своему либо не подошло. Требуется получить из edit и записать в другой модуль числа. Написал код, он работает в идеальных условиях, но если ввести что то подобное "-12е4", то на выходе получу число "12". Написал ещё проверку на ввод не числа, но она работает если ввести только не числа, при вводе чисел и букв...
C++ Int выходит за пределы Добрый день!Проблема в следующем. Работаю с числами аля 13045652312. И нахожу остаток от деления. Но int не в ходит в пределы. Если пишу допустим k=pow(x,c)%a; то пишет,что перегруженная функция. если пишу,что k=a%c; И пишу допустим тип double то выдаёт ошибку. Подскажите как сделать? http://www.cyberforum.ru/cpp-beginners/thread1494025.html
Флаг skipws C++
Как работает флаг cin.unsetf(ios::skipws), какие именно разделители он пропускает? Почему если я хочу считать строку с пробелами, то считает только до пробела?
C++ Вывести на экран таблицу символов в формате «ASCII-код – символ»
Не понимаю, как делать это задание, уже весь интернет перерыл.
C++ Решение матричного уравнения AX=B http://www.cyberforum.ru/cpp-beginners/thread1493992.html
Помогите пожалуйста! Нужна программа для решения матричного уравнения AX=B
C++ Преобразовать текст, расположив в нем слова в алфавитном порядке Помогите пожалуйста!!! Разработать алгоритм и программу. Вводится тест из заглавных и строчных русских букв, пробелов. Количество символов в тексте не должно превышать 300. Преобразовать текст, расположив в нем слова в алфавитном порядке. Вывести преобразованный текст. подробнее

Показать сообщение отдельно
Iakov
0 / 0 / 0
Регистрация: 06.07.2015
Сообщений: 8
06.07.2015, 16:46     Задача поиска множественных путей в графе
Добрый день.
Возникла задача поиска множественных путей в графе. Задача объемная и по объему вычислений и по памяти. По моему разумению задача может быть хорошо распараллелена.
Решил использовать многопоточность на C++ (VS 2010 х64). Написал тест с использованием API-шных функций по добавлению в vector элементов внутри каждого потока. Вроде как все работает без ошибок. Но возникло несколько вопросов.

1. Не могу, как не старался, загрузить все (ну или хотя бы почти все) ядра. У меня сервер - 4 процессора по 16 ядер в каждом. Максимум, что могу загрузить - 13 ядер одного процессора. При этом, если задаю количество потоков больше 64, то вообще все "ломается" - неправильно и не до конца работает добавление элементов к вектору.
2. Сравнил скорость расчета в однопоточном варианте и в многопоточном. У меня получается, что в однопоточном варианте суммарная скорость расчетов где-то в 2.5 раза быстрее чем в многопоточном, независимо от количества threads. В диспетчере задач наблюдал, что в однопоточном варианте одно ядро грузится под 100 процентов, а в многопоточном варианте несколько ядер загружаются на 15-20 процентов.

Буду очень признателен, если кто-нибудь сможет подсказать, что происходит и как это победить.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <tchar.h>
#include <cstdio>
 
#include <vector>
#include <cmath>
#include <string>
 
#include <process.h>
#include <windows.h>
#include <ctime>
using namespace std;
 
#define THREADS_NUMBER 17
 
#define ITERATIONS_NUMBER 10000000
 
#define PAUSE 10 /* ms */
 
DWORD dwCounter = 0;
vector<vector<int>> vt;
 
vector<vector<int>> vt_t;
 
 
    unsigned __stdcall ThreadProc(CONST LPVOID lpParam) {
    CONST HANDLE hMutex = (CONST HANDLE)lpParam;
   int iloc=0;
     WaitForSingleObject(hMutex, INFINITE);
     
     iloc=dwCounter;
     dwCounter++;
     ReleaseMutex(hMutex);
     Sleep(PAUSE);
 
   for(int i = 0; i < ITERATIONS_NUMBER; i++) {
       vt[iloc].push_back(i);     
   }
        //printf(" Into %d\n", iloc);
   ExitThread(0);
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    
unsigned int start_time1 =  clock(); 
// однопоточный тест
    for( int i1=0; i1< THREADS_NUMBER; i1++)
   {
        vector<int> vj;
       vt_t.push_back(vj);
   }
 
   for( int iloc=0; iloc< THREADS_NUMBER; iloc++)
   {
        for(int i = 0; i < ITERATIONS_NUMBER; i++) {
            vt_t[iloc].push_back(i);     
         }
   }
 
   unsigned int end_time1 =  clock(); 
 
 
    TCHAR szMessage[256];
    unsigned threadID;
 
   for( int i1=0; i1< THREADS_NUMBER; i1++)
   {
        vector<int> vj;
       vt.push_back(vj);
   }
 
   //многопоточность
   unsigned int start_time2 =  clock(); 
 
    int i;
   HANDLE hThreads[THREADS_NUMBER];
   CONST HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   CONST HANDLE hMutex = CreateMutex(NULL, FALSE, NULL);
   if(NULL == hMutex) {
     printf(" No Mutex\n");
   }
 
   for(i = 0; i < THREADS_NUMBER; i++) {
    hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, &ThreadProc, hMutex, 0, &threadID);
     if(NULL == hThreads[i]) {
        printf(" No thr\n");
     }
   }
 
   WaitForMultipleObjects(THREADS_NUMBER, hThreads, TRUE, INFINITE);
 
unsigned int end_time2 =  clock(); 
 
   int svt;
   int ival;
   // проверка правильности расчетов
   printf("Counter = %d\r\n", dwCounter);
   for(int iz=0; iz<vt.size(); iz++)
   {
        try {
       svt=vt[iz].size();
       ival=vt[iz][svt-1];
       printf("iz=%d ij=%d value=%d \n", iz, svt, ival);
        } catch (...)
        {
            printf("Counter = %d\r\n", dwCounter);
        }
   }
 
        printf(" time1 = %ld  time2= %ld \n", end_time1-start_time1, end_time2-start_time2);
   for(i = 0; i < THREADS_NUMBER; i++) {
     CloseHandle(hThreads[i]);
   }
   CloseHandle(hMutex);
   ExitProcess(0);
    
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 02:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru