Hi,
I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".
One of my classes possesses an STL map of the structure
map< string, string myMap;
The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}
// Otherwise
string myString( lab );
return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?
And in general, do you have any suggestions how to improve the function
"findString"?
Regards,
Chris 7 6072
Christian Christmann wrote:
Hi,
I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".
One of my classes possesses an STL map of the structure
map< string, string myMap;
The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
map< string, string >::const_iterator it = myMap.find( tmp );
>
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
return it->second;
}
// Otherwise
string myString( lab );
Why again?
return tmp;
>
return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?
You could try a different comparison predicate: if many of your string have
a common prefix, lexicographic comparison may look at many characters
before being able to decide. In this case, short-lex order could take
advantage of strings being of different lengths.
Also, if your map is more or less static, i.e., built once and used
afterward for searching only, you could use
std::vector< std::pair< std::string, std::string
instead: put all pairs in there, sort, and do table lookup by binary search.
However, that should not make a big difference.
Another option is to use an unordered_map instead where you can play around
with a hash function.
And in general, do you have any suggestions how to improve the function
"findString"?
See above: I wondered why you are going through c_str(). Your map knows
strings, just use them.
Best
Kai-Uwe Bux
Christian:
Try implementing something like this:
//your map deffinition (take care of the memory!!!)
typedef map< string, string* my_map_t;
//your function deffinition
const string & findString( const string & lab );
const string & findString( const char * lab );
This way, the map::find funciton itself will execute more efficiently,
and you wont have to dereference the pointer or create a temp object in
your function, just return a reference to the map's string.
Hope this help.
Christian Christmann wrote:
Hi,
I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".
One of my classes possesses an STL map of the structure
map< string, string myMap;
The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}
// Otherwise
string myString( lab );
return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?
And in general, do you have any suggestions how to improve the function
"findString"?
Regards,
Chris
flagos wrote:
Christian:
Try implementing something like this:
//your map deffinition (take care of the memory!!!)
typedef map< string, string* my_map_t;
//your function deffinition
const string & findString( const string & lab );
const string & findString( const char * lab );
This way, the map::find funciton itself will execute more efficiently,
and you wont have to dereference the pointer or create a temp object in
your function, just return a reference to the map's string.
Hope this help.
Coud you please explain why this way helps memory? And, how?
Michael
Christian Christmann wrote:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}
// Otherwise
string myString( lab );
return myString;
}
Try this:
inline string findString( const char *lab )
{
map< string, string >::const_iterator it = myMap.find(lab);
if ( it != myMap.end() ) {
return it->second;
}
// Otherwise
return lab;
}
If this makes compile errors, try this:
inline string findString( const char *lab )
{
map< string, string >::const_iterator it = myMap.find(string(lab));
if ( it != myMap.end() ) {
return it->second;
}
// Otherwise
return string(lab);
}
Regards
Thorsten
Christian Christmann wrote:
Hi,
I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".
One of my classes possesses an STL map of the structure
map< string, string myMap;
The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
I'm confused as to why you make a local string object here and then
convert back to char* to then pass it back to something expecting a
string.
>
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
Again, why the temporary? etc...
}
// Otherwise
string myString( lab );
return myString;
}
You might want to consider putting the string in the map. in the
case it's not found. Any how, the below is a more succint way
of expressing the exact same thing (without all the extra copies).
string findString(const char* lab) {
map<string, string>::const_iterator it = myMap.find(lab);
if(it != myMap.end()
return it->second;
else
return lab;
}
If this makes compile errors, try this: inline string findString( const
char *lab ) {
map< string, string >::const_iterator it = myMap.find(string(lab));
if ( it != myMap.end() ) {
return it->second;
}
}
// Otherwise
return string(lab);
}
}
Just another idea: In order to avoid calling string's constructor, one
could return a reference:
inline const string& findString( const string&lab ) {
map< string, string >::const_iterator it = myMap.find(lab);
if ( it != myMap.end() ) {
return it->second;
}
// Otherwise
return lab
}
"Christian Christmann" <pl*****@yahoo.dewrote in message
news:44***********************@newsread4.arcor-online.net...
Hi,
I've profiled one of my C++ projects and figured out that the
program spends a lot of time with STL map's function "find".
One of my classes possesses an STL map of the structure
map< string, string myMap;
The function that consumes a substantial fraction of the
program execution, searches in the map:
string findString( const char *lab )
{
string tmp( lab );
map< string, string >::const_iterator it = myMap.find( tmp.c_str() );
if ( it != myMap.end() ) {
string myString( it->second.c_str() );
return myString;
}
// Otherwise
string myString( lab );
return myString;
}
Do you see any possibility to optimize the "find" function on "myMap"?
you could use what I call a string-tree:
template<class T>
class CStringTree
{ private:
std::auto_ptr<CStringTreem_sChildren[256];
T m_s;
public:
void addEntry(const char *_p, const T &_r)
{ if (*_p)
{ if (!m_sChildren[*_p].get())
m_sChildren[*_p] = std::auto_ptr<CStringTree>(new
CStringTree);
m_sChildren[*_p].get()->addEntry(_p + 1, _r);
}
else
{ if (!m_sChildren[0].get())
m_sChildren[0] = std::auto_ptr<CStringTree>(new
CStringTree);
m_sChildren[0].get()->m_s = _r;
}
}
const T *findEntry(const char *_p)
{ if (*_p)
if (!m_sChildren[*_p].get())
return 0;
else
return m_sChildren[*_p].get()->findEntry(_p + 1);
else
if (!m_sChildren[0].get())
return 0;
else
return &m_sChildren[0].get()->m_s;
}
};
Creating an entry in a string tree may take more time than creating an entry
in a map.
But finding an entry is considerable faster. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Dave |
last post by:
Hello all,
I have written an expression interpreter, and a profiler has told me that a
specific part of it is in need of optimization. My purpose in posting to
this newsgroup is to solicit...
|
by: mcassiani |
last post by:
Hi,
I need use map faster as possible (I store in the map data about open
network connections).
First a question, this code fragment is from "The C++ Programming........
|
by: MariusI |
last post by:
I stumbled over an optimization (or lack of one, to be specific) when viewing
IL opcodes generated by the compiler using ms .net 2003. I was testing fast
pixel manipulation using Bitmap.LockBits...
|
by: Jazzkt |
last post by:
I wrote a little code using the map container available in the STL of C++.
The trouble I am having is that the find() member function is working
properly. When I try to find a key, if that key is...
|
by: Mervin Williams |
last post by:
I am building a web application that will have a single form that will be
populated with data from 8-10 tables. The easiest way to implement the data
tier would be to use DataSets and Data...
|
by: Ole Nielsby |
last post by:
I just wonder if this is possible with C++/clr.
I'm trying to .NET-enable an interpreter for a Lisp flavoured
language, the interpreter written in NASM which I have
managed to port to MASM....
|
by: telnet2008 |
last post by:
Hi,everyone:
the questionly code:
#include <iostream>
using namespace std;
class test
{
int x;
|
by: wqe |
last post by:
Hi,everyone:
the questionly code:
#include <iostream>
using namespace std;
class test
{
int x;
|
by: baudolino |
last post by:
I have a map<string, time_t>; string represents a filesystem path, time_t is a timestamp associated with that path. My problem is to find the best version of a directory and its subdirectories,...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: jfyes |
last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
|
by: PapaRatzi |
last post by:
Hello,
I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Shællîpôpï 09 |
last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
| |