Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign
patch : from std::map replace to hashmap
Loaden:
Hi, I write a new wxStringHashMap, It's use random key, like this:
--- Code: ---#include <iostream>
#include <map>
#include <vector>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <wx/string.h>
#include <wx/timer.h>
#include <wx/hashmap.h>
const size_t LOOPS = 9;
const size_t TIMES = 10000000;
const wxString FINDKEY = _T("_GLIBCXX_END_NAMESPACE_TR1");
class HashForWxStringMap
{
public:
HashForWxStringMap() {}
unsigned long operator()(const wxString& x) const
{
size_t len = x.length();
return size_t((128 ^ len) + *((unsigned int*)(x.c_str() + len - 4)));
}
HashForWxStringMap& operator=(const HashForWxStringMap&) { return *this; }
};
class EqualForWxStringMap
{
public:
EqualForWxStringMap() { }
bool operator()(const wxString& a, const wxString& b) const
{ return a == b; }
EqualForWxStringMap& operator=(const EqualForWxStringMap&) { return *this; }
};
WX_DECLARE_HASH_MAP(wxString, wxString, HashForWxStringMap, EqualForWxStringMap, HashForWxStringMapMap);
//WX_DECLARE_STRING_HASH_MAP(wxString, HashForWxStringMapMap);
typedef std::vector<wxString> RandomString;
const wxChar CCH[] = _T("_0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_");
const int RANDOM_NUM = 1000000;
void InitRandomString(RandomString& rs)
{
for (int i = 0; i < RANDOM_NUM + 1; ++i)
{
int len = 1 + rand() % (sizeof(CCH) / sizeof(wxChar) - 1);
wxChar* buf = new wxChar[len + 1];
for (int j = 0; j < len; ++j)
{
int x = rand() % (sizeof(CCH) / sizeof(wxChar) - 1);
buf[j] = CCH[x];
}
buf[len] = 0;
// std::wcout << buf << std::endl;
rs.push_back(buf);
delete[] buf;
}
}
int main()
{
srand((unsigned)time(NULL));
std::cout << "Please wait for random string..." << std::endl;
std::cout << std::endl;
RandomString rs;
InitRandomString(rs);
std::map<wxString, wxString> stdMap;
stdMap[_T("_GLIBCXX_STD")] = _T("std");
stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
stdMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
stdMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
stdMap[_T("_STD_BEGIN")] = _T("-namespace std {");
stdMap[_T("_STD_END")] = _T("}");
stdMap[_T("_GLIBCXX_STD2")] = _T("2std");
stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
stdMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
stdMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
stdMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
stdMap[_T("_STD_END2")] = _T("2}");
HashForWxStringMapMap hashMap;
hashMap[_T("_GLIBCXX_STD")] = _T("std");
hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
hashMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
hashMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
hashMap[_T("_STD_BEGIN")] = _T("-namespace std {");
hashMap[_T("_STD_END")] = _T("}");
hashMap[_T("_GLIBCXX_STD2")] = _T("2std");
hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
hashMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
hashMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
hashMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
hashMap[_T("_STD_END2")] = _T("2}");
int stdTotalTime = 0;
for (size_t i = 0; i < LOOPS; ++i)
{
wxStopWatch sw;
for (size_t j = 0; j < TIMES; ++j) stdMap.find(rs.at(i % RANDOM_NUM));
sw.Pause();
int time = sw.Time();
std::cout << "stdMap " << i + 1 << " : " << time << std::endl;
stdTotalTime += time;
}
std::cout << std::endl;
std::cout << "stdMap Total Time: " << stdTotalTime << std::endl;
double stdAverage = stdTotalTime / LOOPS;
std::cout << "stdMap Average Time: " << stdAverage << std::endl;
std::cout << "------------------------------\n" << std::endl;
int hashTotalTime = 0;
for (size_t i = 0; i < LOOPS; ++i)
{
wxStopWatch sw;
for (size_t j = 0; j < TIMES; ++j) hashMap.find(rs.at(i % RANDOM_NUM));
sw.Pause();
int time = sw.Time();
std::cout << "hashMap " << i + 1 << " : " << time << std::endl;
hashTotalTime += time;
}
std::cout << std::endl;
std::cout << "hashMap Total Time: " << hashTotalTime << std::endl;
double hashAverage = hashTotalTime / LOOPS;
std::cout << "hashMap Average Time: " << hashAverage << std::endl;
std::cout << "------------------------------\n" << std::endl;
std::cout << "(stdAverage - hashAverage) / stdAverage = " << (stdAverage - hashAverage) / stdAverage;
std::cout << std::endl;
return 0;
}
--- End code ---
--- Code: ---Please wait for random string...
stdMap 1 : 1265
stdMap 2 : 1266
stdMap 3 : 984
stdMap 4 : 1281
stdMap 5 : 1016
stdMap 6 : 1250
stdMap 7 : 828
stdMap 8 : 1234
stdMap 9 : 1125
stdMap Total Time: 10249
stdMap Average Time: 1138
------------------------------
hashMap 1 : 250
hashMap 2 : 250
hashMap 3 : 297
hashMap 4 : 250
hashMap 5 : 250
hashMap 6 : 250
hashMap 7 : 250
hashMap 8 : 266
hashMap 9 : 250
hashMap Total Time: 2313
hashMap Average Time: 257
------------------------------
(stdAverage - hashAverage) / stdAverage = 0.774165
Process returned 0 (0x0) execution time : 16.000 s
Press any key to continue.
--- End code ---
Loaden:
If change the hash function TO:
--- Code: ---class HashForWxStringMap
{
public:
HashForWxStringMap() {}
unsigned long operator()(const wxString& x) const
{
size_t len = x.length();
if (len >= sizeof(unsigned int) / sizeof(wxChar))
return size_t((128 ^ len) + *((unsigned int*)(x.c_str() + len - sizeof(unsigned int) / sizeof(wxChar))));
else if (len >= sizeof(unsigned short) / sizeof(wxChar))
return size_t((256 ^ len) + *((unsigned short*)(x.c_str() + len - sizeof(unsigned short) / sizeof(wxChar))));
else
return size_t((512 ^ len) + *(x.c_str() + len - sizeof(unsigned short)));
}
HashForWxStringMap& operator=(const HashForWxStringMap&) { return *this; }
};
--- End code ---
AND ONLY 9 replacement, report here:
--- Code: ---Please wait for random string...
stdMap 1 : 609
stdMap 2 : 610
stdMap 3 : 562
stdMap 4 : 1063
stdMap 5 : 562
stdMap 6 : 610
stdMap 7 : 1047
stdMap 8 : 765
stdMap 9 : 610
stdMap Total Time: 6438
stdMap Average Time: 715
------------------------------
hashMap 1 : 250
hashMap 2 : 328
hashMap 3 : 250
hashMap 4 : 250
hashMap 5 : 250
hashMap 6 : 234
hashMap 7 : 250
hashMap 8 : 250
hashMap 9 : 250
hashMap Total Time: 2312
hashMap Average Time: 256
------------------------------
(stdAverage - hashAverage) / stdAverage = 0.641958
--- End code ---
Loaden:
Here is final report:
--- Code: ---Please wait for random string...
stdMap 1 : 1032
stdMap 2 : 766
stdMap 3 : 609
stdMap 4 : 766
stdMap 5 : 578
stdMap 6 : 609
stdMap 7 : 1032
stdMap 8 : 1015
stdMap 9 : 609
stdMap Total Time: 7016
stdMap Average Time: 779
------------------------------
hashMap 1 : 250
hashMap 2 : 250
hashMap 3 : 250
hashMap 4 : 250
hashMap 5 : 250
hashMap 6 : 250
hashMap 7 : 250
hashMap 8 : 235
hashMap 9 : 250
hashMap Total Time: 2235
hashMap Average Time: 248
------------------------------
(stdAverage - hashAverage) / stdAverage = 0.681643
Process returned 0 (0x0) execution time : 12.703 s
Press any key to continue.
--- End code ---
DEMO (-O2):
--- Code: ---#include <iostream>
#include <map>
#include <vector>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <wx/string.h>
#include <wx/timer.h>
#include <wx/hashmap.h>
const size_t LOOPS = 9;
const size_t TIMES = 10000000;
const wxChar CCH[] = _T("_0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_");
const int RANDOM_NUM = 1000000;
typedef std::vector<wxString> RandomString;
class HashForWxStringMap
{
public:
HashForWxStringMap() {}
unsigned long operator()(const wxString& x) const
{
const size_t len = x.length();
const size_t intWxChar = sizeof(unsigned int) / sizeof(wxChar);
const size_t shortWxChar = sizeof(unsigned short) / sizeof(wxChar);
if (len >= intWxChar)
return size_t((128 ^ len) + *((unsigned int*)(x.c_str() + len - intWxChar)));
else if (len >= shortWxChar)
return size_t((256 ^ len) + *((unsigned short*)(x.c_str() + len - shortWxChar)));
else
return size_t((512 ^ len) + *(x.c_str() + len - 1));
}
HashForWxStringMap& operator=(const HashForWxStringMap&) { return *this; }
};
class EqualForWxStringMap
{
public:
EqualForWxStringMap() { }
bool operator()(const wxString& a, const wxString& b) const
{ return a == b; }
EqualForWxStringMap& operator=(const EqualForWxStringMap&) { return *this; }
};
WX_DECLARE_HASH_MAP(wxString, wxString, HashForWxStringMap, EqualForWxStringMap, wxStringHashMap);
void InitRandomString(RandomString& rs)
{
for (int i = 0; i < RANDOM_NUM + 1; ++i)
{
int len = 1 + rand() % (sizeof(CCH) / sizeof(wxChar) - 1);
wxChar* buf = new wxChar[len + 1];
for (int j = 0; j < len; ++j)
{
int x = rand() % (sizeof(CCH) / sizeof(wxChar) - 1);
buf[j] = CCH[x];
}
buf[len] = 0;
rs.push_back(buf);
delete[] buf;
}
}
int main()
{
srand((unsigned)time(NULL));
std::cout << "Please wait for random string..." << std::endl;
std::cout << std::endl;
RandomString rs;
InitRandomString(rs);
std::map<wxString, wxString> stdMap;
stdMap[_T("_GLIBCXX_STD")] = _T("std");
stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
stdMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
stdMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
stdMap[_T("_STD_BEGIN")] = _T("-namespace std {");
stdMap[_T("_STD_END")] = _T("}");
// stdMap[_T("_GLIBCXX_STD2")] = _T("2std");
// stdMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
// stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
// stdMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
// stdMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
// stdMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
// stdMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
// stdMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
// stdMap[_T("_STD_END2")] = _T("2}");
wxStringHashMap hashMap;
hashMap[_T("_GLIBCXX_STD")] = _T("std");
hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE")] = _T("+namespace");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE")] = _T("+namespace");
hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE")] = _T("}");
hashMap[_T("_GLIBCXX_END_NAMESPACE")] = _T("}");
hashMap[_T("_GLIBCXX_END_NAMESPACE_TR1")] = _T("}");
hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR1")] = _T("-namespace tr1 {");
hashMap[_T("_STD_BEGIN")] = _T("-namespace std {");
hashMap[_T("_STD_END")] = _T("}");
// hashMap[_T("_GLIBCXX_STD2")] = _T("2std");
// hashMap[_T("_GLIBCXX_BEGIN_NESTED_NAMESPACE2")] = _T("2+namespace");
// hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE2")] = _T("2+namespace");
// hashMap[_T("_GLIBCXX_END_NESTED_NAMESPACE2")] = _T("2}");
// hashMap[_T("_GLIBCXX_END_NAMESPACE2")] = _T("2}");
// hashMap[_T("_GLIBCXX_END_NAMESPACE_TR12")] = _T("2}");
// hashMap[_T("_GLIBCXX_BEGIN_NAMESPACE_TR12")] = _T("2-namespace tr1 {");
// hashMap[_T("_STD_BEGIN2")] = _T("2-namespace std {");
// hashMap[_T("_STD_END2")] = _T("2}");
int stdTotalTime = 0;
for (size_t i = 0; i < LOOPS; ++i)
{
wxStopWatch sw;
for (size_t j = 0; j < TIMES; ++j) stdMap.find(rs.at(i % RANDOM_NUM));
sw.Pause();
int time = sw.Time();
std::cout << "stdMap " << i + 1 << " : " << time << std::endl;
stdTotalTime += time;
}
std::cout << std::endl;
std::cout << "stdMap Total Time: " << stdTotalTime << std::endl;
double stdAverage = stdTotalTime / LOOPS;
std::cout << "stdMap Average Time: " << stdAverage << std::endl;
std::cout << "------------------------------\n" << std::endl;
int hashTotalTime = 0;
for (size_t i = 0; i < LOOPS; ++i)
{
wxStopWatch sw;
for (size_t j = 0; j < TIMES; ++j) hashMap.find(rs.at(i % RANDOM_NUM));
sw.Pause();
int time = sw.Time();
std::cout << "hashMap " << i + 1 << " : " << time << std::endl;
hashTotalTime += time;
}
std::cout << std::endl;
std::cout << "hashMap Total Time: " << hashTotalTime << std::endl;
double hashAverage = hashTotalTime / LOOPS;
std::cout << "hashMap Average Time: " << hashAverage << std::endl;
std::cout << "------------------------------\n" << std::endl;
std::cout << "(stdAverage - hashAverage) / stdAverage = " << (stdAverage - hashAverage) / stdAverage;
std::cout << std::endl;
return 0;
}
--- End code ---
[attachment deleted by admin]
koso:
@Loaden: you made the hash function quiet complicated, but i dont understand, what were you trying to do. Are you aware of sizeof(int)=sizeof(wxChar)=4 .. on 32 bit system with UNICODE wxWidgets? At this configuration, your hash function only takes last character of string.
Loaden:
--- Quote from: koso on March 22, 2010, 06:10:04 pm ---@Loaden: you made the hash function quiet complicated, but i dont understand, what were you trying to do. Are you aware of sizeof(int)=sizeof(wxChar)=4 .. on 32 bit system with UNICODE wxWidgets? At this configuration, your hash function only takes last character of string.
--- End quote ---
On 32 bit windows OS, sizeof(wxChar) == 2, but sizeof(int) = 4;
Yes, I only only judge the length and the last one (or two) character, Because has enough for a replacement rules.
You can look at the rules of these replacement：
--- Code: ---<TOKEN_REPLACEMENTS>
<ssmap>
<QT_BEGIN_HEADER>
<![CDATA[]]>
</QT_BEGIN_HEADER>
<QT_END_HEADER>
<![CDATA[]]>
</QT_END_HEADER>
<Q_GADGET>
<![CDATA[]]>
</Q_GADGET>
<Q_INLINE_TEMPLATE>
<![CDATA[]]>
</Q_INLINE_TEMPLATE>
<Q_OBJECT>
<![CDATA[]]>
</Q_OBJECT>
<Q_OUTOFLINE_TEMPLATE>
<![CDATA[]]>
</Q_OUTOFLINE_TEMPLATE>
<Q_PACKED>
<![CDATA[]]>
</Q_PACKED>
<Q_REQUIRED_RESULT>
<![CDATA[]]>
</Q_REQUIRED_RESULT>
<_GLIBCXX_BEGIN_NAMESPACE>
<![CDATA[+namespace]]>
</_GLIBCXX_BEGIN_NAMESPACE>
<_GLIBCXX_BEGIN_NAMESPACE_TR1>
<![CDATA[-namespace tr1 {]]>
</_GLIBCXX_BEGIN_NAMESPACE_TR1>
<_GLIBCXX_BEGIN_NESTED_NAMESPACE>
<![CDATA[+namespace]]>
</_GLIBCXX_BEGIN_NESTED_NAMESPACE>
<_GLIBCXX_END_NAMESPACE>
<![CDATA[}]]>
</_GLIBCXX_END_NAMESPACE>
<_GLIBCXX_END_NAMESPACE_TR1>
<![CDATA[}]]>
</_GLIBCXX_END_NAMESPACE_TR1>
<_GLIBCXX_END_NESTED_NAMESPACE>
<![CDATA[}]]>
</_GLIBCXX_END_NESTED_NAMESPACE>
<_GLIBCXX_STD>
<![CDATA[std]]>
</_GLIBCXX_STD>
<_STD_BEGIN>
<![CDATA[-namespace std {]]>
</_STD_BEGIN>
<_STD_END>
<![CDATA[}]]>
</_STD_END>
<emit>
<![CDATA[]]>
</emit>
</ssmap>
</TOKEN_REPLACEMENTS>
--- End code ---
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version