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

Потоки и запоминание итераторов - C++

Восстановить пароль Регистрация
 
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 01:21     Потоки и запоминание итераторов #1
Жду помощи...
хочу, чтобы 2 потока запоминали итераторы, чтобы потом можно было свапнуть разыменованные иттераторы...но проблема с синхронизацией.
Как вызывать события? как они должны выглядеть...и..есть ли смысл заморачиваться с этим?
Код получается примерно такой:
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
122
123
124
125
126
127
128
#include "stdafx.h"
#include <Windows.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
static vector<int>::iterator it1;
static vector<int>::iterator it2;
 
template <typename T>
T average(T it1, T it2, T it3)
{
    if (*it1 <= *it2)
    {
        if (*it3 <= *it1)
            return it1;
        if (*it3 >= *it2)
            return it2;
        return it3;
    }
    if (*it3 <= *it2)
        return it2;
    if (*it3 >= *it1)
        return it1;
    return it3;
}
 
template <typename T>
struct para
{
    T begin,end;
    int num;
    para (T b, T e, int n)
    {
        begin = b;
        end = e;
        num = n;
    }
};
 
typedef para<vector<int>::iterator> PARAMS;
 
 
DWORD WINAPI func1(PVOID param)
{
    PARAMS* p = static_cast< PARAMS * > (param);
    int a = p->num;
    while(p->begin != p->end)
    {
        if(*p->begin >= a)
        {
            it1 = p->begin;
            //создать 1-ое событие
            //ждать 3 событие
        }
        ++p->begin;
    }
 
    return 0;
}
 
DWORD WINAPI func2(PVOID param)
{
    PARAMS* p = static_cast< PARAMS * > (param);
    int a = p->num;
    while(p->begin != p->end)
    {
        if(*p->begin <= a)
        {
            it1 = p->begin;
            //создать 2-ое событие
            //ждать 3 событие
        }
    }
    return 0;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
 
    vector<int> b;
    for(int i = 0; i< 10; ++i)
        b.push_back(rand());
    /*for(unsigned int i = 0; i<b.size(); ++i)
        cout<<b[i]<<"  ";
    cout<<'\n';*/
 
    auto p_ave = b.begin();
    advance(p_ave,b.size()/2);
    
    /*cout<< *p_ave;
    cout<<'\n';*/
    swap(*p_ave, *average(b.begin(),--b.end(),p_ave));
    /*cout<<'\n';
    for(unsigned int i = 0; i<b.size(); ++i)
        cout<<b[i]<<"  ";*/
    
    
    
    
    
    
    
    
    
    /*HANDLE potok[2];
    potok[0] = CreateThread(NULL, 0, func, &p1, 0, NULL);
    potok[1] = CreateThread(NULL, 0, func, &p2, 0, NULL);
    WaitForMultipleObjects(2, potok, FALSE, INFINITE);
    */
    PARAMS p1(b.begin(),p_ave,*p_ave);
    PARAMS p2(p_ave, b.end(), *p_ave);
    
    
    HANDLE potok[2];
    potok[0] = CreateThread(NULL, 0, func1, &p1, 0, NULL);
    potok[1] = CreateThread(NULL, 0, func2, &p2, 0, NULL);
    
    //ждать 1 и 2 события
    swap(*it1, *it2);
    //инициализировать 3-е событие
    //WaitForMultipleObjects(2, potok, FALSE, INFINITE);
 
    return 0;
}
Изначально стояла задача о сортировке массива с помощью двух потоков (для 100% загрузки двухядерного процессора)
В приведённой выше программе делается предварительный шаг, чтобы получить массив вида
МЕНЬШЕ ЧИСЛА | ЧИСЛО | БОЛЬШЕ ЧИСЛА
а потом отдельно для 1 и 2 части вызвать независемые потоки. и получить отсортированный массив с помощью sort().
P.s. сортировка ОБЯЗАТЕЛЬНО с помощью sort
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2012, 01:21     Потоки и запоминание итераторов
Посмотрите здесь:

C++ Не видит класс итераторов
C++ Перегрузка итераторов
C++ Применение итераторов
C++ использование потоковых итераторов
Двусвязный список с поддержкой итераторов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Питекантроп
 Аватар для Питекантроп
246 / 140 / 6
Регистрация: 14.06.2010
Сообщений: 340
13.03.2012, 04:26     Потоки и запоминание итераторов #2
Цитата Сообщение от IcyWind Посмотреть сообщение
В приведённой выше программе делается предварительный шаг, чтобы получить массив вида
МЕНЬШЕ ЧИСЛА | ЧИСЛО | БОЛЬШЕ ЧИСЛА
а потом отдельно для 1 и 2 части вызвать независемые потоки. и получить отсортированный массив с помощью sort().
Йа предлагаю несколько другой принцип: Разбить ровно пополам, отсортировать, а потом слить воедино.

Смотрим код
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
#include <iostream>
#include <vector>
#include <algorithm>
 
#include "windows.h"
#include "time.h"
 
using namespace std;
 
DWORD WINAPI thr_sort_int(void * prm)
{
        vector<int>::iterator * it_p = (vector<int>::iterator*)prm;
        sort(*it_p,*(it_p + 1));
        return 0;
}
 
void sort2_int(vector<int>::iterator it1, vector<int>::iterator it2)
{
        vector<int>::iterator iter_to_sort[2];
        iter_to_sort[0] = it1;
        iter_to_sort[1] = it1 + (it2 - it1) / 2;
        HANDLE th = CreateThread(NULL, 0, thr_sort_int, &iter_to_sort, 0, NULL);
        sort(iter_to_sort[1] + 1, it2);
        WaitForSingleObject(th, 1000000);
        inplace_merge(iter_to_sort[0],iter_to_sort[1] + 1, it2);
}
 
int main()
{
        int size = 20000;
        vector<int> arr(size);
        srand(time(0));
        for (int i = 0; i < size; ++i) arr[i] = rand();
 
        sort2_int(arr.begin(), arr.end());
 
   //     for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++)
    //            cout<<*it<<" ";
        cout<<endl<<endl;
 
        for (int i = 0; i < size; ++i) arr[i] = rand();
        int tm = clock();
        sort2_int(arr.begin(), arr.end());
        cout<<"time thr2: "<< 0.001 * (clock() - tm)<<endl;
 
        for (int i = 0; i < size; ++i) arr[i] = rand();
        tm = clock();
        sort(arr.begin(), arr.end());
        cout<<"time thr1: "<< 0.001 * (clock() - tm)<<endl;
    return 0;
}
У меня выигрыш от двух потоков получается где-то с 15К
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 16:03  [ТС]     Потоки и запоминание итераторов #3
Да, изначально был такой вариант)
даже смог его реализовать
но уперся в то, что нужно построить двухпоточный аналог inplace_merge
на этом и запнулся...не могу заставить 2 потока взаимодействовать...
сегодня ещё посмотрю код inplace_merge, может что в голову и придёт...
Питекантроп
 Аватар для Питекантроп
246 / 140 / 6
Регистрация: 14.06.2010
Сообщений: 340
13.03.2012, 16:22     Потоки и запоминание итераторов #4
Цитата Сообщение от IcyWind Посмотреть сообщение
что нужно построить двухпоточный аналог inplace_merge
зачем?
inplace_merge работает со скоростью О(N), поэтому на него затраты небольшие. Кроме того, при слиянии идет постоянное чередование действий, поэтому его сложно будет распараллелить.
Ваш же вариант МЕНЬШЕ ЧИСЛА | ЧИСЛО | БОЛЬШЕ ЧИСЛА может быть неэффективным из-за неверного выбора медианы.
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 19:03  [ТС]     Потоки и запоминание итераторов #5
Да, мой вариант был продиктован как раз тем, что мне не удалось создать аналог inplace_merge.
поэтому решил сначало выбрать элемент...пусть плохо...но потом не заморачиться с ним.
Да, О(N), но если пустить 2 потока.
один из begin() второй из "midle()", понятное дело, что выигрышь будет, конечно, не в 2 раза, но довольно существенный.
Так что...пока стоит задача аналога inplace_merge в 2 потока.

Добавлено через 2 часа 16 минут
Что я делаю не так...
сортировка одним потоком ВСЕГДА быстрее, чем двумя...даже при 200 000 000 числах...
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
#include "stdafx.h"
#include <Windows.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;
 
 
DWORD WINAPI func(void* param)
{
    vector<int>::iterator* p = static_cast< vector<int>::iterator* > (param);
    //cout<<endl<<"Из потока: ";
    sort(*p, *(p+1));
    //ExitThread(0);
    return 0;
}
 
 
const int N = 2000000;
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(0, "Rus");
    srand(time(0));
    vector<int> b;
    for(int i = 0; i< N; ++i)
        b.push_back(rand());
 
    //2 potoka
    long start = clock();
    auto p_ave = b.begin();
    advance(p_ave,b.size()/2);
 
    vector<int>::iterator p[2];
    p[0] = b.begin();
    p[1] = p_ave;
    
    HANDLE potok = CreateThread(NULL, 0, func, p, 0, NULL);
    
    //WaitForMultipleObjects(2, potok, FALSE, INFINITE);
    sort(p_ave,b.end());
    WaitForSingleObject(potok, INFINITE);
    
    /*for(unsigned int i = 0; i< b.size();++i)
        cout<<b[i]<<" ";*/
 
 
    inplace_merge(b.begin(), p_ave, b.end());
 
    /*for(unsigned int i = 0; i< b.size();++i)
        cout<<b[i]<<" ";*/
    
    cout<<"Два потока. Время = "<<0.001*(clock() - start)<<"Сек"<<endl;
 
    
    for(unsigned int i = 0; i< b.size();++i)
        b[i]=rand();
    //1 potok
    start = clock();
    sort(b.begin(), b.end());
    /*for(unsigned int i = 0; i< b.size();++i)
        cout<<b[i]<<" ";*/
    cout<<"Один поток. Время = "<<0.001*(clock() - start)<<"Сек"<<endl;
    return 0;
}
Добавлено через 15 минут
Ого как! Поменял "debug" версию компиляции на "Release" и всё поменялось...очень круто поменялось...

Добавлено через 3 минуты
А кто-нибудь может это объяснить?
Питекантроп
 Аватар для Питекантроп
246 / 140 / 6
Регистрация: 14.06.2010
Сообщений: 340
13.03.2012, 22:23     Потоки и запоминание итераторов #6
в дебаге не стоят по умолчанию опции оптимизации. + добавляется лишняя отладочная информация в файл. Зайди в опции проетка, с\с++, оптимизация. И сравни опции в отладочной и релизной конфигурации
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 22:26  [ТС]     Потоки и запоминание итераторов #7
Ага...спасибо...но даже в релизе по дефолту стоят не все опции.
А ещё вопросик
Я, когда тестровал, заметил, что, если в вектор сувать большее примерно 100 000 000 элементов вылазеет ошибка на этапе выполнения.
Тут есть объяснение?
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
13.03.2012, 22:29     Потоки и запоминание итераторов #8
Цитата Сообщение от IcyWind Посмотреть сообщение
100 000 000
это как минимум 4 * 100 000 000 те, не меньше полутора гигов, у вас памяти то хватит?
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 22:33  [ТС]     Потоки и запоминание итераторов #9
Да, слежу внимательно. Занято 2,2. Всего 4

Добавлено через 1 минуту
Причём с 100 000 000 работает. и сортирует...секунд за 8...
а вот с 200 000 000 уже не запускается

Добавлено через 2 минуты
в том смысле, что 2,2 занято, когда работает программа с 100 000 000.
Питекантроп
 Аватар для Питекантроп
246 / 140 / 6
Регистрация: 14.06.2010
Сообщений: 340
13.03.2012, 22:54     Потоки и запоминание итераторов #10
Цитата Сообщение от IcyWind Посмотреть сообщение
Ага...спасибо...но даже в релизе по дефолту стоят не все опции.
Все опции не нужны. Там есть оптимизация по объему и по скорости. По объему не надо.

Цитата Сообщение от IcyWind Посмотреть сообщение
Я, когда тестровал, заметил, что, если в вектор сувать большее примерно 100 000 000 элементов вылазеет ошибка на этапе выполнения.
Тут есть объяснение?
http://ru.wikipedia.org/wiki/New_(C%...86.D0.B8.D1.8F

Добавлено через 2 минуты
Цитата Сообщение от alex_x_x Посмотреть сообщение
это как минимум 4 * 100 000 000 те, не меньше полутора гигов, у вас памяти то хватит?
это по идее немного менее 400 метров. Возможно, ОС в данный момент не может найти в памяти свободный участок такого размера, поэтому БОЛТ
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 23:50     Потоки и запоминание итераторов
Еще ссылки по теме:

C++ Копирование файла с использованием итераторов
C++ Конфликт итераторов
Равенство пустых итераторов C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
IcyWind
8 / 8 / 2
Регистрация: 19.09.2011
Сообщений: 268
13.03.2012, 23:50  [ТС]     Потоки и запоминание итераторов #11
Переход на вашу ссылку не работает
но наверно да...наверно не может выделить столько памяти последовательно под вектор...
Yandex
Объявления
13.03.2012, 23:50     Потоки и запоминание итераторов
Ответ Создать тему
Опции темы

Текущее время: 21:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru