Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вернуть из функции std::map, оптимально быстрым способом 
V
    Опции темы
Alca
Дата 23.9.2008, 11:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
Вернуть из функции std::map оптимально быстрым способом?
(без передачи std::map по ссылке или указателю в функцию)
Код

typedef std::map<std::string, std::string, std::less<std::string>> TStringMap;
TStringMap Func() {
    TStringMap smInfo;
    //заполняю 
    return smInfo;
}



--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
Alek86
Дата 23.9.2008, 11:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
Код
typedef std::map<std::string, std::string, std::less<std::string>> TStringMap;
typedef std::auto_ptr<TStringMap> StringMapPtr;
StringMapPtr Func() {
    StringMapPtr p_smInfo = new StringMap;
    //заполняю 
    return p_smInfo;
}



--------------------
user posted image    user posted image
PM MAIL   Вверх
Lazin
Дата 23.9.2008, 11:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(Alca @  23.9.2008,  11:30 Найти цитируемый пост)
typedef std::map<std::string, std::string, std::less<std::string>> TStringMap;

можно less не указывать, оно по умолчанию less
Код

void Func(TStringMap& out) 
{
    //заполняю 
    out[...] = ...;
}

TStringMap mymap;
Func(mymap);



--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Torsten
Дата 23.9.2008, 12:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 174
Регистрация: 10.6.2008
Где: Pskov

Репутация: 3
Всего: 7
Цитата(Alca @  23.9.2008,  11:30 Найти цитируемый пост)
без передачи std::map по ссылке или указателю в функцию

ну остается 3 варианта :
1) вернуть по значению  (крайне не эффективно)
2) вернуть по указателю (нужно сохранить обезательно указатель и не забыть потом очистить память)
3) по ссылке - тут сразу будет креш программы, да и компилятор должен предупредить о local variable.

Наиболее удачен вариант возращать smart_ptr или принимать в smart_ptr, т.е. чтобы после возращения указателя функцией у нее у указателя появился хозяин.
Ну и еще как извращенный вариант - сделать переменную static и возращать по ссылки или указателю.


--------------------
We have no begining, we have no end. We are infinite.
PM MAIL   Вверх
Lazin
Дата 23.9.2008, 12:14 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(Alca @  23.9.2008,  11:30 Найти цитируемый пост)
без передачи std::map по ссылке или указателю в функцию

не обратил внимания, а что в этом плохого?


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alca
Дата 23.9.2008, 12:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
Цитата

а что в этом плохого?

Ничего.
Код

TStringMap Func()

Для меня так нагляднее.
Всем спасибо.

Это сообщение отредактировал(а) Alca - 23.9.2008, 12:24


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
maxim1000
Дата 23.9.2008, 18:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
Цитата(Torsten @  23.9.2008,  12:00 Найти цитируемый пост)
вернуть по значению  (крайне не эффективно)

измерения проводились?
а то есть такая штука, как RVO - return value optimization, которая как раз и направлена на подобные ситуации...

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


--------------------
qqq
PM WWW   Вверх
Alca
Дата 25.9.2008, 14:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
Цитата

измерения проводились?

Вот решил потестить:
Код

#include <windows.h>
#include <fstream>
#include <string>
#include <iostream>
#include <stdio.h>
#include <map>
#include "CXString.hpp"
#include "CFsoString.hpp"
#include "CPerform.hpp"  //GetThreadTimes

using namespace std;
typedef std::map<std::string, std::string, std::less<std::string>> TStringMap;
//---------------------------------------------------------------------------
//вернуть по значению
TStringMap FuncA() {
    TStringMap dic;
    
    dic["Key0"] = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    dic["Key1"] = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    dic["Key2"] = "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222";
    dic["Key3"] = "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333";
    dic["Key4"] = "4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444";
    dic["Key5"] = "5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555";
    dic["Key6"] = "6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666";
    dic["Key7"] = "7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777";
    dic["Key8"] = "8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    dic["Key9"] = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
    
    return dic;
}
//---------------------------------------------------------------------------
//вернуть по ссылке
bool FuncB(TStringMap &smDic) {
    smDic["Key0"] = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    smDic["Key1"] = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    smDic["Key2"] = "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222";
    smDic["Key3"] = "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333";
    smDic["Key4"] = "4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444";
    smDic["Key5"] = "5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555";
    smDic["Key6"] = "6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666";
    smDic["Key7"] = "7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777";
    smDic["Key8"] = "8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    smDic["Key9"] = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
    
    return true;
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[]) {
    CPerform P("___Testing perfomance.txt");
    
    //-------------------------------------
    //A
    P.vStart(2);
    TStringMap smDicA;
    for (int i = 0; i < 10000; i ++) {
        smDicA = FuncA();
    }
    P.vStop();
    //-------------------------------------

    Sleep(10);
    
    //-------------------------------------
    //B
    P.vStart(2);
    TStringMap smDicB;
    for (int i = 0; i < 10000; i ++) {
        FuncB(smDicB);
    }
    P.vStop();
    //-------------------------------------
    
    P.vOpenLog();        


    system("pause");

    return 0;
}
//---------------------------------------------------------------------------

Результат на лицо:
Цитата

DEBUG
[2008-09-25 14:15:33]  ------------------------------
[2008-09-25 14:15:43]  0:00:10:375
[2008-09-25 14:15:45]  0:00:01:906
[2008-09-25 14:15:48]  ------------------------------

RELEASE
[2008-09-25 14:16:15]  ------------------------------
[2008-09-25 14:16:16]  0:00:00:328
[2008-09-25 14:16:16]  0:00:00:031
[2008-09-25 14:16:18]  ------------------------------

maxim1000, +1


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
Lazin
Дата 25.9.2008, 14:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
я думаю разница скорее из-за того, что во втором случае, создание TStringMap вынесено за цикл, а в первом происходит при каждой итерации


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
maxim1000
Дата 25.9.2008, 15:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
и не только создание, а ещё и удаление предыдущего
подобная оптимизация основывается на том, что для приёма результата работы функции создаётся объект прямо в той же строчке, т.е. его не нужно чистить от предыдущих данных
тогда вместо (создание снаружи, создание внутри, присваивание) можно делать просто (создания снаружи)

я бы предложил попробовать так:
Код

#include <windows.h>
#include <fstream>
#include <string>
#include <iostream>
#include <stdio.h>
#include <map>
#include "CXString.hpp"
#include "CFsoString.hpp"
#include "CPerform.hpp"  //GetThreadTimes
using namespace std;
typedef std::map<std::string, std::string, std::less<std::string>> TStringMap;
//---------------------------------------------------------------------------
//вернуть по значению
TStringMap FuncA() {
    TStringMap dic;
    
    dic["Key0"] = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    dic["Key1"] = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    dic["Key2"] = "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222";
    dic["Key3"] = "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333";
    dic["Key4"] = "4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444";
    dic["Key5"] = "5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555";
    dic["Key6"] = "6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666";
    dic["Key7"] = "7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777";
    dic["Key8"] = "8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    dic["Key9"] = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
    
    return dic;
}
//---------------------------------------------------------------------------
//вернуть по ссылке
bool FuncB(TStringMap &smDic) {
    smDic["Key0"] = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    smDic["Key1"] = "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111";
    smDic["Key2"] = "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222";
    smDic["Key3"] = "3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333";
    smDic["Key4"] = "4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444";
    smDic["Key5"] = "5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555";
    smDic["Key6"] = "6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666";
    smDic["Key7"] = "7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777";
    smDic["Key8"] = "8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    smDic["Key9"] = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
    
    return true;
}
//---------------------------------------------------------------------------
int main(int argc, char* argv[]) {
    CPerform P("___Testing perfomance.txt");
    
    //-------------------------------------
    //A
    P.vStart(2);
    for (int i = 0; i < 10000; i ++) {
      TStringMap smDicA = FuncA();
      std::cout<<smDicA.begin()->first<<std::endl;//to prevent too much optimization :)
    }
    P.vStop();
    //-------------------------------------
    Sleep(10);
    
    //-------------------------------------
    //B
    P.vStart(2);
    for (int i = 0; i < 10000; i ++) {
      TStringMap smDicB;
      FuncB(smDicB);
      std::cout<<smDicB.begin()->first<<std::endl;//to prevent too much optimization :)
    }
    P.vStop();
    //-------------------------------------
    
    P.vOpenLog();        
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------


Добавлено через 2 минуты и 51 секунду
P.S. Честно говоря, я сам не знаю толком условия работы RVO, могу только предполагать smile


--------------------
qqq
PM WWW   Вверх
Alca
Дата 25.9.2008, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
Код

/*GetTickCount()*/
DEBUG:
[2008-09-25 15:38:24]  ------------------------------
[2008-09-25 15:38:41]  0:00:16:546
[2008-09-25 15:38:54]  0:00:13:187
[2008-09-25 15:39:01]  ------------------------------

RELEASE
[2008-09-25 15:39:48]  ------------------------------
[2008-09-25 15:39:53]  0:00:05:516
[2008-09-25 15:39:58]  0:00:04:985
[2008-09-25 15:40:03]  ------------------------------

P.S. Вот вам и возврат по значению...

Это сообщение отредактировал(а) Alca - 25.9.2008, 15:53


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
W4FhLF
Дата 25.9.2008, 16:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


found myself
****


Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121
В данном случае копирование объекта вносит издержки равные 10% от времени исполнения(если, конечно, это именно копирование объекта). Но эти издержки будут расти с увеличением размера возвращаемого объекта. 

Alca, вощьми map размером не 10 элементов, а 1000, разница должна быть более ощутима. 


--------------------
"Бог умер" © Ницше
"Ницше умер" © Бог
PM ICQ   Вверх
maxim1000
Дата 25.9.2008, 16:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
нннда... похоже, не сработала...

Добавлено через 1 минуту и 49 секунд
вообще, конечно, зря я написал std::cout - довольно медленная операция, можно было бы просто суммировать первые символы строк, чтобы поменьше влиять на статистику
но всё равно разница остаётся...


--------------------
qqq
PM WWW   Вверх
Alca
Дата 25.9.2008, 17:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
map на 1000 элементов (убрал std::cout):
Код

/*GetTickCount()*/
DEBUG:
[2008-09-25 17:06:42]  0:01:38:391
[2008-09-25 17:08:03]  0:01:20:735

RELEASE
[2008-09-25 17:08:33]  0:00:02:094
[2008-09-25 17:08:35]  0:00:02:078



--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
J0ker
Дата 25.9.2008, 17:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 986
Регистрация: 17.9.2008

Репутация: 4
Всего: 14
Цитата(maxim1000 @  23.9.2008,  18:49 Найти цитируемый пост)
а то есть такая штука, как RVO - return value optimization, которая как раз и направлена на подобные ситуации...

RVO выполняется в случае
Код

return type(params);

и случаях котоые могут быть к ему сведены


Это сообщение отредактировал(а) J0ker - 25.9.2008, 17:36


--------------------
user posted image
PM MAIL   Вверх
MTWizard
Дата 7.5.2009, 15:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 8.10.2007
Где: Київ

Репутация: 3
Всего: 4
Цитата(J0ker @  25.9.2008,  17:33 Найти цитируемый пост)
RVO выполняется в случае return type(params); и случаях котоые могут быть к ему сведены

есть ещё NRVO smile

Это сообщение отредактировал(а) MTWizard - 7.5.2009, 15:09
PM MAIL   Вверх
Alca
Дата 7.5.2009, 15:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 7
Всего: 50
NRVO - это чего такое?

Добавлено через 2 минуты
Нашел
http://alenacpp.blogspot.com/2008/02/rvo-nrvo.html



--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1150 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.