作者DRLai (苏打)
看板C_and_CPP
标题[问题] 快速找到table的方式?
时间Sun May 3 15:45:50 2009
我有很多笔纪录，要把他作成类似table的形式
接着依照table的组合来回传最後的value
表格有点像是这样
A B C D E F Value
0 0 0 0 0 1 (数字)
0 0 0 0 0 2 (数字)
这个表格相当庞大
资料量将会破兆
唯一的特点是A,B,....F表格中的数字组合将不会重复
而我要做的事情是
假设我传入
A=0,B=0,C=0,.......E=0,F=1时，他要回传给我Value值
目前想到的作法是这样
先将表格中的数字串接起来变成string
(例如第一笔资料改为0-0-0-0-0-1)
接着把他放进unordered_map (我不知道为什麽我的hash_map会失败，g++ 4.1.2..)
之後查询只要使用unordered_map查询即可
想请问各位的事情是
1.unordered_map的复杂度为O(1)吗？我翻了相关文件，看他的说法是
部份case下会有worst case O(n)...我不太懂为甚麽他会这样说@@ (boost.org提及)
2.除了我上述的结构外，有没有其他方法可以快速查询到Value值
时间复杂度希望为O(1)..因为资料多，O(logn)可能还是太慢
3.同2，其实我有测试过把int转为string去作查询，但是速度还是稍慢
主因是int->string也需要花时间，不知道有没有更好的办法
感谢各位^~^
--
▊ ◥ thePainter. ◤ ▎
▊ ◣◢
◣ ◤ ◣
◤ ▎
▊ ◥◤ ◣
◤ ◤ ▎ http://www.wretch.cc/blog/myelf
▊ ◥ ◢ ◤ ◤ ◤
▎ Wretch@BBS -> P_myelf
▊ ◢◤ thePainter. ◣ ▎ φthePainter.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.138.145.212
1F：推 kkdlin:hash? 05/03 16:03
2F：→ DRLai:我前面文章有提到过..不知道为什麽我的hash_map没办法用orz 05/03 16:08
3F：→ DRLai:路径对了，也有hash_map.h，compile却有错 05/03 16:09
4F：推 chrisdar:A~F 的值域是多少 05/03 17:05
5F：→ DRLai:从0到某一个值，A-F皆不相同 05/03 17:16
6F：推 TroyLee:#include "hash_map" 然後 namespace 有用对吗?不一定在 05/03 17:32
7F：→ TroyLee:std里面喔 05/03 17:32
8F：推 chrisdar:map<hash_value_int,int>; 选一个合适的HASH函数 05/03 17:40
9F：→ chrisdar:从0到某一个值，A-F皆不相同 < 32bit ? 05/03 17:42
10F：→ DRLai:回c大，您说的方式依旧属於map的范畴吗？ 系统是64bit 05/03 17:43
11F：→ DRLai:回T大，我知道不见得是std..我的是__gnu_cxx，但一样会错 05/03 17:43
12F：→ DRLai:嗯...感谢各位，我大概知道为什麽hash_map会发生错误了 05/03 17:49
13F：→ DRLai:现在使用g++的hash_map正常了，谢过各位^^~ 05/03 17:49