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

Оптимизация программы по памяти - C++

Восстановить пароль Регистрация
 
svizzle
0 / 0 / 0
Регистрация: 19.05.2014
Сообщений: 2
19.05.2014, 16:45     Оптимизация программы по памяти #1
Здравствуйте, дорогие коллеги!

Прошу вашей помощи. Кто чем поможет.
Есть минимальная программа рекомендательной системы( код ниже ). Работает по модели baseline predictors, сложного ничего нет. Получается так что программа есть много памяти при загрузке больших данных. Как же можно ее оптимизировать?( что бы использовалось меньше памяти ).

Спасибо за внимание!

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
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>
#include <iomanip>
 
 
using namespace std;
 
const int MAX_SIZE_USER = 10000;                // максимальное количество пользователей или фильмов
 
typedef vector<float> typ_float;
 
/**
* @description Вычисление значения BIAS.
* @params сумма всех оценок, количество оценок, общий средний рейтинг
* @return BIAS значение 
*/
float bias( float sum, int count, float average ){
    return (sum / count ) - average;
}
 
int main() {
    
    int tmp_user, tmp_item, tmp_rate;           // для чтения таблиц
 
    short max_rate;                             // максимально возможная оценка 
    int count_user, count_items;                // количество пользователей и фильмов
    int count_learn_items, count_test_items;    // количество оцененных и неоцененных фильмов   
    float raw_average = 0;                      // общее среднее значение оценок
    
    vector<typ_float> table_learn;
    typ_float tmp;
 
    typ_float bias_users;
    typ_float bias_items;
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
 
    cin >> max_rate >> count_user >> count_items >> count_learn_items >> count_test_items;
 
    tmp.assign(count_items, 0 );
    table_learn.assign( count_user, tmp );
    bias_users.assign(count_user, 0);
    bias_items.assign(count_items, 0);
 
    tmp.clear();
 
    cin.ignore(1000, '\n' );
 
    //читаем данные обучаемой таблицы и формируем матрицу
    for( int i = 0; i < count_learn_items; i++ ){
 
        cin >> tmp_user >> tmp_item >> tmp_rate;
 
        table_learn[tmp_user][tmp_item] = tmp_rate;
        raw_average += tmp_rate;
    }
 
    raw_average /= count_learn_items;       // общий рейтинг
 
    int tmp_count_user;
    int tmp_count_item;
 
    float tmp_value_user;
    float tmp_value_item;
 
    // BIAS пользователей
    for( int i = 0; i < count_user; i++ ){
 
        tmp_value_user = tmp_value_item = tmp_count_item = tmp_count_user = 0;
 
        for (int j = 0; j < count_items; j++)
        {
            if( table_learn[i][j] ){
                tmp_value_user += table_learn[i][j]; tmp_count_user++;
            }
 
            if( table_learn[j][i] ){
                tmp_value_item += table_learn[j][i]; tmp_count_item++;
            }
        }
 
        bias_users[i] = bias( tmp_value_user, tmp_count_user, raw_average );
        bias_items[i] = bias( tmp_value_item, tmp_count_item, raw_average );
    }
 
 
    float result = 0;
 
    // результат
    for( int i = 0; i < count_test_items; i++ ){
        
        cin >> tmp_user >> tmp_item;
 
        result = raw_average + bias_items[tmp_item] + bias_users[tmp_user];
 
        result = ( result > max_rate ) ? max_rate : result;
 
        cout << fixed << setprecision(4) << result << endl;
    }
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2014, 16:45     Оптимизация программы по памяти
Посмотрите здесь:

C++ Оптимизация программы на С++
Оптимизация простой программы C++
Оптимизация программы C++
Оптимизация программы C++
Оптимизация программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
19.05.2014, 17:47     Оптимизация программы по памяти #2
Для N данных это (N * N * sizeof(float) + N * sizeof(float) + N * sizeof(float)) чистой + еще мета информация байт:
Где метаинформация это:
1. Для массивов bias_users и bias_items ее практически нет (sizeof(vector) + размер хедера аллокации).
2. Для массива table_learn это N рамеров хедеров аллокации.

Так вот, можно воспользоватся пулом памяти. Который избавит от метаинформации. Общая идея такая: аллоцируем N * K памяти. а потом раздаем K раз, вместо K раз аллокации по N.

Можете сделать сами это не сложно, если не мудрить. А лучше воспользоватся boost:ool
svizzle
0 / 0 / 0
Регистрация: 19.05.2014
Сообщений: 2
19.05.2014, 17:52  [ТС]     Оптимизация программы по памяти #3
Цитата Сообщение от stima Посмотреть сообщение
Для N данных это (N * N * sizeof(float) + N * sizeof(float) + N * sizeof(float)) чистой + еще мета информация байт:
Где метаинформация это:
1. Для массивов bias_users и bias_items ее практически нет (sizeof(vector) + размер хедера аллокации).
2. Для массива table_learn это N рамеров хедеров аллокации.

Так вот, можно воспользоватся пулом памяти. Который избавит от метаинформации. Общая идея такая: аллоцируем N * K памяти. а потом раздаем K раз, вместо K раз аллокации по N.

Можете сделать сами это не сложно, если не мудрить. А лучше воспользоватся boost::pool
Спасибо!
Убрал несколько массивов по памяти нормально. Теперь по скорости не проходит. Что по скорости можно сделать?

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
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>
#include <iomanip>
 
 
using namespace std;
 
const int MAX_SIZE_USER = 10000;                // максимальное количество пользователей или фильмов
 
typedef vector<unsigned short> typ_short;
 
/**
* @description Вычисление значения BIAS.
* @params сумма всех оценок, количество оценок, общий средний рейтинг
* @return BIAS значение 
*/
float bias( int sum, int count, float average ){
    return (sum / count ) - average;
}
 
int main() {
    
    short tmp_user, tmp_item, tmp_rate;         // для чтения таблиц
    short max_rate;                             // максимально возможная оценка 
    short count_user, count_items;              // количество пользователей и фильмов
 
    int count_learn_items, count_test_items;    // количество оцененных и неоцененных фильмов   
    int tmp_count_user;
    int tmp_count_item;
    int tmp_value_user;
    int tmp_value_item;
 
    float raw_average = 0;                      // общее среднее значение оценок
    float result = 0;
 
    vector<typ_short> table_learn;
    typ_short tmp;
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    cin >> max_rate >> count_user >> count_items >> count_learn_items >> count_test_items;
 
    tmp.assign(count_items, 0 );
    table_learn.assign( count_user, tmp );
 
    //читаем данные обучаемой таблицы и формируем матрицу
    for( int i = 0; i < count_learn_items; i++ ){
 
        cin >> tmp_user >> tmp_item >> tmp_rate;
 
        table_learn[tmp_user][tmp_item] = tmp_rate;
        raw_average += tmp_rate;
    }
    raw_average /= count_learn_items;       // общий рейтинг
 
 
 
    //читаем данные обучаемой таблицы и формируем матрицу
    for( int i = 0; i < count_test_items; i++ ){
        
        cin >> tmp_user >> tmp_item;
 
        tmp_value_user = tmp_value_item = tmp_count_item = tmp_count_user = 0;
 
        for (int j = 0; j < count_items; j++)
        {
            if( table_learn[j][tmp_item] && ++tmp_count_item)
                tmp_value_item += table_learn[j][tmp_item];
        }
 
        for( int j = 0; j < count_user; j++ )
        {
            if( table_learn[tmp_user][j] && ++tmp_count_user )
                tmp_value_user += table_learn[tmp_user][j];
        }
 
        result = raw_average + bias( tmp_value_user, tmp_count_user, raw_average ) + bias( tmp_value_item, tmp_count_item, raw_average );
 
        result = ( result > max_rate ) ? max_rate : result;
 
        cout << fixed << setprecision(4) << result << endl;
    }
 
    return 0;
}
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
19.05.2014, 18:07     Оптимизация программы по памяти #4
Цитата Сообщение от svizzle Посмотреть сообщение
if( table_learn[tmp_user][j] && ++tmp_count_user )
Не делайте так никогда!.
1. Не читаемо.
2. У Вас преинкримент. А по идее должен быть пост.
3. Можете попасть на порядок вычисления операторов.

Добавлено через 28 секунд
Это спокойно паралелится
Цитата Сообщение от svizzle Посмотреть сообщение
for (int j = 0; j < count_items; j++)
* * * * {
* * * * * * if( table_learn[j][tmp_item] && ++tmp_count_item)
* * * * * * * * tmp_value_item += table_learn[j][tmp_item];
* * * * }
for( int j = 0; j < count_user; j++ )
* * * * {
* * * * * * if( table_learn[tmp_user][j] && ++tmp_count_user )
* * * * * * * * tmp_value_user += table_learn[tmp_user][j];
* * * * }
Добавлено через 7 минут
http://www.cplusplus.com/reference/future/async/
п.с. Если не ясно можно и через обычные потоки.

Добавлено через 43 секунды
А пулом всетаки воспользуйтесь сократит использование памяти значительно.
Yandex
Объявления
19.05.2014, 18:07     Оптимизация программы по памяти
Ответ Создать тему
Опции темы

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