我知道代码会变慢,但为什么会这么慢?我该如何编写代码以避免这种减速?
std::unordered_map在内部使用其他容器,并且这些容器使用迭代器。在构建调试时,默认情况下_ITERATOR_DEBUG_LEVEL=2。这会打开迭代器调试。有时我的代码受影响不大,有时它运行得非常慢。
我可以通过在项目属性>> C++ >> 预处理器 >> 预处理器定义中设置_ITERATOR_DEBUG_LEVEL=0来加快示例的速度。但是,正如此链接所建议的那样,我不能在我的真实项目中这样做。在我的情况下,我与包含_ITERATOR_DEBUG_LEVEL=2的std::basic_string的MSVCMRTD.lib发生冲突。我知道我可以通过静态链接到CRT来解决问题。但如果我能修复代码以避免出现问题,我更愿意这样做。
我可以做出改进情况的更改。但我只是尝试着做事而不了解为什么它们有效。例如,目前为止,前1000次插入以全速运行。但如果我将O_BYTE_SIZE更改为1,则第一次插入与其他所有操作一样慢。这看起来是一个小变化(不一定是好的变化)。 这里, 这里, 和 这里 也有所启示,但没有回答我的问题。
我正在使用 Visual Studio 2010 (这是传统代码)。我创建了一个 Win32 控制台应用程序并添加了这段代码。
std::unordered_map在内部使用其他容器,并且这些容器使用迭代器。在构建调试时,默认情况下_ITERATOR_DEBUG_LEVEL=2。这会打开迭代器调试。有时我的代码受影响不大,有时它运行得非常慢。
我可以通过在项目属性>> C++ >> 预处理器 >> 预处理器定义中设置_ITERATOR_DEBUG_LEVEL=0来加快示例的速度。但是,正如此链接所建议的那样,我不能在我的真实项目中这样做。在我的情况下,我与包含_ITERATOR_DEBUG_LEVEL=2的std::basic_string的MSVCMRTD.lib发生冲突。我知道我可以通过静态链接到CRT来解决问题。但如果我能修复代码以避免出现问题,我更愿意这样做。
我可以做出改进情况的更改。但我只是尝试着做事而不了解为什么它们有效。例如,目前为止,前1000次插入以全速运行。但如果我将O_BYTE_SIZE更改为1,则第一次插入与其他所有操作一样慢。这看起来是一个小变化(不一定是好的变化)。 这里, 这里, 和 这里 也有所启示,但没有回答我的问题。
我正在使用 Visual Studio 2010 (这是传统代码)。我创建了一个 Win32 控制台应用程序并添加了这段代码。
Main.cpp
#include "stdafx.h"
#include "OString.h"
#include "OTHashMap.h"
#include <cstdio>
#include <ctime>
#include <iostream>
// Hash and equal operators for map
class CRhashKey {
public:
inline unsigned long operator() (const OString* a) const { return a->hash(); }
};
class CReqKey {
public:
inline bool operator() (const OString& x, const OString& y) const { return strcmp(x.data(),y.data()) != 0; }
inline bool operator() (const OString* x, const OString& y) const { return operator()(*x,y); }
inline bool operator() (const OString& x, const OString* y) const { return operator()(x,*y); }
inline bool operator() (const OString* x, const OString* y) const { return operator()(*x,*y); }
};
int _tmain(int argc, _TCHAR* argv[])
{
const int CR_SIZE = 1020007;
CRhashKey h;
OTPtrHashMap2<OString, int, CRhashKey, CReqKey> *code_map =
new OTPtrHashMap2 <OString, int, CRhashKey, CReqKey>(h, CR_SIZE);
const clock_t begin_time = clock();
for (int i=1; i<=1000000; ++i)
{
char key[10];
sprintf(key, "%d", i);
code_map->insert(new OString(key), new int(i));
//// Check hash values
//OString key2(key);
//std::cout << i << "\t" << key2.hash() << std::endl;
// Check timing
if ((i % 100) == 0)
{
std::cout << i << "\t" << float(clock() - begin_time) / CLOCKS_PER_SEC << std::endl;
}
}
std::cout << "Press enter to exit" << std::endl;
char buf[256];
std::cin.getline(buf, 256);
return 0;
}
OTHashMap.h
#pragma once
#include <fstream>
#include <unordered_map>
template <class K, class T, class H, class EQ>
class OTPtrHashMap2
{
typedef typename std::unordered_map<K*,T*,H,EQ> OTPTRHASHMAP_INTERNAL_CONTAINER;
typedef typename OTPTRHASHMAP_INTERNAL_CONTAINER::iterator OTPTRHASHMAP_INTERNAL_ITERATOR;
public:
OTPtrHashMap2(const H& h, size_t defaultCapacity) : _hashMap(defaultCapacity, h) {}
bool insert(K* key, T* val)
{
std::pair<OTPTRHASHMAP_INTERNAL_ITERATOR,T> retVal = _hashMap.insert(std::make_pair<K*,T*>(key, val));
return retVal.second != NULL;
}
OTPTRHASHMAP_INTERNAL_CONTAINER _hashMap;
private:
};
OString.h
#pragma once
#include <string>
class OString
{
public:
OString(const std::string& s) : _string (s) { }
~OString(void) {}
static unsigned hash(const OString& s) { return unsigned (s.hash()); }
unsigned long hash() const
{
unsigned hv = static_cast<unsigned>(length());
size_t i = length() * sizeof(char) / sizeof(unsigned);
const char * p = data();
while (i--) {
unsigned tmp;
memcpy(&tmp, p, sizeof(unsigned));
hashmash(hv, tmp);
p = p + sizeof(unsigned);
}
if ((i = length() * sizeof(char) % sizeof(unsigned)) != 0) {
unsigned h = 0;
const char* c = reinterpret_cast<const char*>(p);
while (i--)
{
h = ((h << O_BYTE_SIZE*sizeof(char)) | *c++);
}
hashmash(hv, h);
}
return hv;
}
const char* data() const { return _string.c_str(); }
size_t length() const { return _string.length(); }
private:
std::string _string;
//static const unsigned O_BYTE_SIZE = 1;
static const unsigned O_BYTE_SIZE = 8;
static const unsigned O_CHASH_SHIFT = 5;
inline void hashmash(unsigned& hash, unsigned chars) const
{
hash = (chars ^
((hash << O_CHASH_SHIFT) |
(hash >> (O_BYTE_SIZE*sizeof(unsigned) - O_CHASH_SHIFT))));
}
};