我实现了一个搜索缓存结果,它包含State类型的键(一个有7个短整数的类)和一个类型为Socre的类(一个3个双精度类.)使用unordered_map比map慢至少20倍.为什么？
编辑:Darn it!我的哈希函数是
namespace std {
size_t hash<State>::operator()(State const& s) const {
size_t retval = hash<short>()(s.s[0]);
for (int i = 1; i < R; i += 2) { // 1 3 5
int x = (static_cast<int>(s.s[i + 1]) << 16)
+ (static_cast<int>(s.s[i]));
hash_combine(retval, x);
}
}
}
我忘了return retval,所以一切都在碰撞!我希望unordered_map有一个hash_function_quality()函数来报告平均冲突数.
我想在VS2010 C++下的索引double处存储~3,000,000个值unsigned int.我用它std::tr1:unordered_map<unsigned int, double>来达到这个目的.不幸的是,当我尝试存储值2 ^ 21时,会抛出异常(就好像只有2 ^ 21-1的空间,即某些索引只能使用20位).我rehash在存储值之前尝试过,这也没有用.
最后,我最终得到了一些非常基本的测试程序(它表现出甚至有点不同的行为,但无论如何):
std::tr1::unordered_map<unsigned int, float> mapOut;
//mapOut.rehash(SOMESIZE);
for (unsigned int i=0; i<3000000; i++)
{
if (i%1000==0) std::cout << i << std::endl;
mapOut[i] = 0.0;
}
我查了一些案例:
1)如果我根本不重新进行,则程序在输出后根据i == 32000(最终2 ^ 15)进行长时间休息,然后继续i == 262000(2 ^ 18).它永远存在(100%CPU负载,内存不增加).
2)如果我做了rehash(1000),它来到i == 65000(2 ^ 16)并永远保持(CPU负载100%,内存不增加).
3)如果我这样做rehash(3000000),循环成功完成,但程序永远不会退出 - 即,显然析构函数存在一些问题.
那里发生了什么,更重要的是:我该怎么办呢？!
非常感谢您的帮助!
对于这两个std::map和std::tr1::unordered_map,我从标准看:
在所有情况下,对unordered_map容器中元素的引用仍然有效,即使在重新散列之后也是如此.
他们是如何做到的(以实施方式)？他们是否将所有条目都维护为一种链表,然后哈希表只存储指向元素的指针？
作为这个问题的前言,我不得不说我是一名Java程序员,因此更习惯于使用Java中的Maps而不是C++语义.在Java中,它很常见,并且null在Map中查找键时会返回.我正在将一些代码翻译成c ++,并尝试在与unordered_map交互时找到c ++的处理方式.
具体来说,我有一个包含unordered_map的类.我没有将映射直接暴露给客户端代码,而是有2个包装函数,一个用于将键/值对放入映射,另一个用于检索指定键的值,即:
void set_tag_value(string tag, string value);
string& get_tag_value(string tag);
如果我unordered_map.at()用来检索值,那么它将抛出我的代码需要捕获的异常,或者允许它传播到客户端代码.(尽管如此,传播例外似乎对我不友好).
也许另一种方法是将返回值更改为string*类型,如果未找到则返回NULL(这是Java的方式),但是用户需要检查NULL(这也不是那么友好).
所以我的问题有两个部分:
什么是开发人员友好的方式来处理失败的查找,什么返回值将是有用的(异常,NULL,空字符串,或其他)？
在我的代码中,当您期望它可能找不到键,at()和catch异常,或者查找并检查iterator == map.end()时,哪个map up up方法更常用？(这部分问题是我只是想学习c ++的做事方式).
谢谢你的建议!
我希望使用侵入式unordered_map.由于某种原因,库中只有一个unordered_set.还有一个侵入式散列表,但我不确定它是否具有相同的功能,也没有相同的接口.
我错了,我错过了unordered_map链接？
如果我不是,那么有一个教程可以帮助我实现一个吗？
我似乎无法找到任何关于此的信息,所以我转向stackoverflow.在C++中std :: tr1 :: unordered_map的迭代器效率如何？特别是与列表迭代器进行比较.创建一个包含类的包装类是否有意义,它还包含列表中的所有键以允许有效的迭代(我的代码在unordered_map中使用了大量的迭代).对于那些会推荐提升的人,我不能使用它(无论出于何种原因).
当我第一次使用operator []访问std :: unordered_map中的元素时,会自动创建它.什么(如果有的话)是关于它初始化的保证？(保证值是初始化的,还是只能构建)？
例:
std::unordered_map<void *, size_t> size;
char *test = new char[10];
size[test] += 10;
在此序列结束时,尺寸[测试]是否保证为10？
我想使用Haskell计算存储在文件中的唯一块.该块只是连续的字节,长度为512,目标文件的大小至少为1GB.
这是我最初的尝试.
import Control.Monad
import qualified Data.ByteString.Lazy as LB
import Data.Foldable
import Data.HashMap
import Data.Int
import qualified Data.List as DL
import System.Environment
type DummyDedupe = Map LB.ByteString Int64
toBlocks :: Int64 -> LB.ByteString -> [LB.ByteString]
toBlocks n bs | LB.null bs = []
| otherwise = let (block, rest) = LB.splitAt n bs
in block : toBlocks n rest
dedupeBlocks :: [LB.ByteString] -> DummyDedupe -> DummyDedupe
dedupeBlocks = flip $ DL.foldl' (\acc block -> insertWith (+) block 1 $! acc) …我在stackoverflow上已经阅读了很多关于unordered_map (c ++ 11) 时间复杂度的内容,但是我没有找到我的问题的答案.
我们假设按整数索引(仅举例):
插入/在函数不断工作(平均时间),所以这个例子需要O(1)
std::unordered_map<int, int> mymap = {
{ 1, 1},
{ 100, 2},
{ 100000, 3 }
};
我很好奇的是迭代存储在地图中的所有(未排序的)值需要多长时间 - 例如
for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }
我可以假设每个存储的值只被访问一次(或两次或恒定次数)吗？这意味着迭代所有值都在N值映射O(N)中.另一种可能性是我的密钥{1,10,100000}的示例可能需要多达1000000次迭代(如果由数组表示)
是否有任何其他容器,可以线性迭代并且不断地通过给定密钥访问值？
我真正需要的是(伪代码)
myStructure.add(key, value) // O(1)
value = myStructure.at(key) // O(1)
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values
std :: unordered_map是我需要的结构吗？
整数索引也足够,平均复杂度也很高.
我正在尝试优化需要很长时间的C++代码的某些部分(对于X数据量,代码的以下部分需要大约19秒,并且我试图在不到5秒的时间内完成整个过程相同数量的数据 - 基于我的一些基准测试.我有一个函数"add",我已经编写并复制了代码.我将尝试尽可能多地解释我认为需要理解代码.如果我错过了什么,请告诉我.
对于X数据条目,以下函数add被称为X次.
void HashTable::add(PointObject vector) // PointObject is a user-defined object
{
int combinedHash = hash(vector); // the function "hash" takes less than 1 second for X amount of data
// hashTableMap is an unordered_map<int, std::vector<PointObject>>
if (hashTableMap.count(combinedHash) == 0)
{
// if the hashmap does not contain the combinedHash key, then
// add the key and a new vector
std::vector<PointObject> pointVectorList;
pointVectorList.push_back(vector);
hashTableMap.insert(std::make_pair(combinedHash, pointVectorList));
}
else
{
// otherwise find the key and the corresponding vector of …