作者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
推 kkdlin:hash? 05/03 16:03
→ DRLai:我前面文章有提到過..不知道為什麼我的hash_map沒辦法用orz 05/03 16:08
→ DRLai:路徑對了，也有hash_map.h，compile卻有錯 05/03 16:09
推 chrisdar:A~F 的值域是多少 05/03 17:05
→ DRLai:從0到某一個值，A-F皆不相同 05/03 17:16
推 TroyLee:#include "hash_map" 然後 namespace 有用對嗎?不一定在 05/03 17:32
→ TroyLee:std裡面喔 05/03 17:32
推 chrisdar:map<hash_value_int,int>; 選一個合適的HASH函數 05/03 17:40
→ chrisdar:從0到某一個值，A-F皆不相同 < 32bit ? 05/03 17:42
→ DRLai:回c大，您說的方式依舊屬於map的範疇嗎？ 系統是64bit 05/03 17:43
→ DRLai:回T大，我知道不見得是std..我的是__gnu_cxx，但一樣會錯 05/03 17:43
→ DRLai:嗯...感謝各位，我大概知道為什麼hash_map會發生錯誤了 05/03 17:49
→ DRLai:現在使用g++的hash_map正常了，謝過各位^^~ 05/03 17:49