[問題] minheap/performance bottleneck/memory usage
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
VC++ 2012
問題(Question)：
Q1:
大家好, 我現在想要實作一個minheap
其中存放的資料是pair< vector<int>, double>
目前我是用std::priority_queue去做
但是問題是我存進去的pair, 在掃transaction時會改變它的double值
所以我目前的做法是, 先用map存放這些資料, 掃transaction時再從map改變它的值
掃完之後再將這些資料丟進minheap內
可是這樣的做法就必須每次都重新建立一個minheap
簡單來說,
有沒有struct可以直接存取改變minheap內node的值並且維持minheap的架構
Q2:
另外一個問題是關於程式的瓶頸,
http://ppt.cc/7w3b profiler作完的圖
目前寫的這個程式作完profiler後, 瓶頸是卡在map的operator[]
因為這個map儲存的資料有1m以上, 所以profiler是顯示在_Lbound
其中subset function的code貼在下面, 第21行顯示佔的比例最大
像這樣的情況如果改用unordered_map存
在operator[]的時間應該會比map來得短, 不過因為我map的key值是vector<int>
這樣hash function必須自己建, 不曉得怎麼建比較好
Q3:
最後想再加問一個問題, 在Windows底下執行程式,
有工具或是方法得知程式使用記憶體的最高值嗎?
我目前用的方法是在程式碼內加上
#include <Windows.h>
#include <Psapi.h>
#pragma comment(lib, "psapi.lib")
int main()
{
PROCESS_MEMORY_COUNTERS pmc;
// code here
GetProcessMemoryInfo( GetCurrentProcess(), &pmc, sizeof(pmc));
cout << "Memory Usage: " << pmc.PeakWorkingSetSize << endl; // 峰值
}
但是不曉得這樣的用法抓的記憶體最高值是否準確
問題是這三個, 謝謝!
程式碼(Code)：(請善用置底文網頁, 記得排版)
http://ideone.com/WsOe5Q
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.216
推
04/24 01:29, , 1F
04/24 01:29, 1F
→
04/24 01:30, , 2F
04/24 01:30, 2F
後來再看一次, L大的意思是 std::priority_queue 沒有直接改變內部key值的功能是嗎?
→
04/24 02:43, , 3F
04/24 02:43, 3F
→
04/24 02:44, , 4F
04/24 02:44, 4F
了解, 還是說也可以將
std::map<std::vector<T>, double> 利用 std::make_heap 建成 heap
如果有改過map內的value, 再用std::sort_heap
→
04/24 02:47, , 5F
04/24 02:47, 5F
→
04/24 02:49, , 6F
04/24 02:49, 6F
→
04/24 02:49, , 7F
04/24 02:49, 7F
→
04/24 02:50, , 8F
04/24 02:50, 8F
→
04/24 02:51, , 9F
04/24 02:51, 9F
這邊要用 std::vector<T> 當作 key 是因為它是一組物品ID的組合,
value 則是這組物品ID組合的價值, 那在過程中可能會一直改變某組合的 value 值
所以我才用 std::map< std::vector<T>, double> 來儲存, 方便direct access
這邊的意思是直接用key值的記憶體位址去做hash囉, 不太懂避免取到r-value的址的意思
謝謝回答!
※ 編輯: karaokstar 來自: 140.112.28.216 (04/24 16:32)
→
04/24 21:01, , 10F
04/24 21:01, 10F
→
04/24 21:02, , 11F
04/24 21:02, 11F
→
04/24 21:03, , 12F
04/24 21:03, 12F
謝謝版大的解釋, 不過我的困難點是
我資料成員每掃過一次 transaction 就有可能會變動,
那為了能夠 direct access, 所以我才用map去存
我想達到的效果可能是
container[member] += value; // 執行完後依然維持 heap 的特性
但是 map 本身並不能支援 push_heap 等操作(?)
所以我才每掃過一次 transaction, 就將 map 的 member 丟進 std::priority_queue 內
※ 編輯: karaokstar 來自: 140.112.28.216 (04/25 21:54)
→
04/26 02:27, , 13F
04/26 02:27, 13F
→
04/26 02:28, , 14F
04/26 02:28, 14F
了解, 謝謝版大, 實作再改成這樣試試看, 跟目前的方法比效率哪個較高!
※ 編輯: karaokstar 來自: 140.112.28.216 (04/29 12:33)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
