CMap InitHashTable 大小
CMap InitHashTable size
在我的程序中,CMap
的大小是 1.2 IIRC 6230 的倍数,优于我使用的大小 InitHashTable
(即 6203)。
我输入另一个 InitHashTable
值,它是一个质数:9973
所以这是正确的吗?或者我应该选择一个更接近 6203 的质数。或者我可以选择一个更大的质数吗?
std::map
使用 红黑树 并且 CMap
实现为 hash-table.所以这是两个完全不同的容器。根据 MSDN 的最佳性能,散列 table 大小应该是质数。为了尽量减少冲突,大小应比最大的预期数据集大大约 20%。
这是 CMap
使用 VS2015 的测试结果。它表明使用素数并没有太大的区别,并且初始化是否比预期值高或低 20% 也无关紧要。
有无质数或初始化都没有错误。我假设 CMap
文档中对 "collision" 的引用与性能有关。
对于较大的数据集,您可以使用预期的数据大小。例如,如果预期大小为 6,000,则只需使用 map.InitHashTable(6000)
。默认值为 17,较低的值会降低性能。
还有std::map
的测试结果,不需要初始化,速度非常快。
void test()
{
CString msg;
//build test vector
int size = 100000;
std::vector<CString> vs;
for (int i = 0; i < size; i++)
{
CString s;
s.Format(L"str%d", i);
vs.push_back(s);
}
{//using prime number, 20% larger than expected size
int t = GetTickCount();
int init_size = 120011;
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
}
{//using non-prime number and 20% less than expected size
int t = GetTickCount();
int init_size = 80000;
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
}
{//using non-prime number and default initialization (m_nHashTableSize=17)
int t = GetTickCount();
CMap<LPCTSTR, LPCTSTR, int, int> map;
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", 17, GetTickCount() - t);
}
{//std::map test
int t = GetTickCount();
std::map<CString, int> mp;
for (int i = 0; i < size; i++)
mp[vs[i]] = i;
msg.AppendFormat(L"std::map time:%d\n", GetTickCount() - t);
}
//error test:
int init_size = 1000; //only a fraction of expected size!
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
for (int i = 0; i < size; i++)
{
if (map[vs[i]] != i)
{
AfxMessageBox(L"errorTest - fail");
return;
}
}
msg.AppendFormat(L"no error");
AfxMessageBox(msg);
}
测试结果:(开启优化发布模式)
CMap Initialized: 120011, time:31
CMap Initialized: 80000, time:47
CMap Initialized: 17, time:5110
std::map time:78
no error
结果只是粗略估计
在我的程序中,CMap
的大小是 1.2 IIRC 6230 的倍数,优于我使用的大小 InitHashTable
(即 6203)。
我输入另一个 InitHashTable
值,它是一个质数:9973
所以这是正确的吗?或者我应该选择一个更接近 6203 的质数。或者我可以选择一个更大的质数吗?
std::map
使用 红黑树 并且 CMap
实现为 hash-table.所以这是两个完全不同的容器。根据 MSDN 的最佳性能,散列 table 大小应该是质数。为了尽量减少冲突,大小应比最大的预期数据集大大约 20%。
这是 CMap
使用 VS2015 的测试结果。它表明使用素数并没有太大的区别,并且初始化是否比预期值高或低 20% 也无关紧要。
有无质数或初始化都没有错误。我假设 CMap
文档中对 "collision" 的引用与性能有关。
对于较大的数据集,您可以使用预期的数据大小。例如,如果预期大小为 6,000,则只需使用 map.InitHashTable(6000)
。默认值为 17,较低的值会降低性能。
还有std::map
的测试结果,不需要初始化,速度非常快。
void test()
{
CString msg;
//build test vector
int size = 100000;
std::vector<CString> vs;
for (int i = 0; i < size; i++)
{
CString s;
s.Format(L"str%d", i);
vs.push_back(s);
}
{//using prime number, 20% larger than expected size
int t = GetTickCount();
int init_size = 120011;
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
}
{//using non-prime number and 20% less than expected size
int t = GetTickCount();
int init_size = 80000;
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", init_size, GetTickCount() - t);
}
{//using non-prime number and default initialization (m_nHashTableSize=17)
int t = GetTickCount();
CMap<LPCTSTR, LPCTSTR, int, int> map;
for (int i = 0; i < size; i++)
map[vs[i]] = i;
msg.AppendFormat(L"CMap Initialized: %d, time:%d\n", 17, GetTickCount() - t);
}
{//std::map test
int t = GetTickCount();
std::map<CString, int> mp;
for (int i = 0; i < size; i++)
mp[vs[i]] = i;
msg.AppendFormat(L"std::map time:%d\n", GetTickCount() - t);
}
//error test:
int init_size = 1000; //only a fraction of expected size!
CMap<LPCTSTR, LPCTSTR, int, int> map;
map.InitHashTable(init_size);
for (int i = 0; i < size; i++)
map[vs[i]] = i;
for (int i = 0; i < size; i++)
{
if (map[vs[i]] != i)
{
AfxMessageBox(L"errorTest - fail");
return;
}
}
msg.AppendFormat(L"no error");
AfxMessageBox(msg);
}
测试结果:(开启优化发布模式)
CMap Initialized: 120011, time:31
CMap Initialized: 80000, time:47
CMap Initialized: 17, time:5110
std::map time:78
no error
结果只是粗略估计