幫助，地圖通過C++

的效率，我有一張地圖，定義爲幫助，地圖通過C++

map<string,map<string,int> > subjectCodes;

每個主題串都有自己的課程

地圖我也有2個迭代器定義

map<string,map<string,int> >::iterator it; 
map<string,int>::iterator jt;

一個迭代通過每個主題和一個迭代通過每個課程每個主題

我需要使我的程序讀取了50,000行信息，將它們排列到地圖中，並在1秒內打印出全部信息。我想我已經想出了將所有內容添加到地圖中的最快方法，但是我正在努力加快打印速度，目前爲0（n平方），並導致我的程序花費大約3秒鐘時間運行。

這裏是我的打印代碼：

//print out sorted list 
for(it=subjectCodes.begin();it!=subjectCodes.end();it++) 
{ 
    cout<<it->first<<": "<<(it->second).size()<<" courses"<<endl; 
    for(jt=(it->second).begin();jt!=(it->second).end();jt++) 
    { 
     cout<<" "<<jt->first<<": "<<jt->second<<" classes"<<endl; 
    } 
}

有打印地圖在地圖中，有人能告訴我的更有效的方法？謝謝

來源

2011-05-11 Patrick Ayers

你是否檢查過輸入3s後花了多少時間？我知道你說過你已經有了「最快的方式」來填充地圖，但是你是否儘可能快地閱讀輸入文件？你使用什麼緩衝區大小？ – 2011-05-11 22:18:47

爲什麼這個「1秒」是一個限制？你真的把這個輸出做到物理設備（例如終端或打印機）嗎？顯然，你不能在1秒內寫出很多這樣的文字，也不應該嘗試。 – 2011-05-11 22:37:18

一個簡單的效率節約：

cout<<" "<<jt->first<<": "<<jt->second<<" classes"<<endl;

應該是：

cout<<" "<<jt->first<<": "<<jt->second<<" classes"<< '\n';

的endl操縱刷新流，它可以是一個非常昂貴的操作，如果你不需要齊平。您應該可以輕鬆地在一分鐘內將50K行寫入流中，但可能不會將其連接到某種類型的終端（即xterm或Windows cmd提示符窗口）。

來源

2011-05-11 21:38:18

問題（現在？）說1秒，而不是1分鐘。我認爲*完全不適合終端。 – 2011-05-11 21:59:56

@Steve True，但不適用於輸出到文件。我很確定它確實說了1分鐘，但也許這款酒正在持續:-) – 2011-05-11 22:01:21

我正在閱讀的每條50k線都有關於課程主題和課程名稱的信息。我解析這個並將其分類到地圖中。然後我使用cout將其打印到命令提示符窗口。項目說明聲明程序應該讀取其輸入文件並執行，所有操作都在不到一秒的時間內完成。這是否意味着它應該在一秒之內完成所有事情？如果是這樣，我該如何達到這個速度？ – 2011-05-12 01:47:27

您是否想過並行化您的應用程序，例如線程或OpenMP？

另一個提示：printf()函數可能比流選項更快。

另外，你是否完全優化編譯？這也可能會顯着提升性能。

來源

2011-05-11 21:42:26 Constantinius

只有一個可用的流寫入，所以並行化只會增加額外的開銷。用戶使用的是字符串，所以printf不是一個選項（或者會讓速度更慢），優化通常對I/O大量操作沒有影響。 – 2011-05-11 21:53:33

當你遇到性能問題時，重要的是追求低垂的果實。要做到這一點，你需要弄清楚算法的瓶頸在哪裏。什麼花了太久？

一旦你找出需要花費的時間，你可以開始提出更具體的問題。通常追求低懸的成果意味着你應該去解決那些對算法速度有很大影響的簡單問題。在這個線程中已經指出了兩個例子（用'\ n'替換std :: endl以減少刷新量，並使用printf over std :: cout來減少函數調用量/不同算法）。

一些更多的可能性：

使用字符串流，並寫在一個單一的操作
重新設計您的結構，所以它是快於通常使用的方式來使用（可以載體中使用而不是第二級的地圖？）
一些完全無關的你寫的代碼塊;「組合鍵」）

來源

2011-05-11 21:50:53 Jerome

爲什麼你認爲stringstream會更快？地圖遍歷速度非常快（這只是指針跟隨）。 – 2011-05-11 21:56:42

@unapersson：使用字符串流（非常近似）就像在底層IO上設置一個巨大的緩衝區，我不認爲這是嘗試優化的*不良*候選者。當然可能沒有幫助。 – 2011-05-11 22:02:39

@unapersson通常情況下，映射將散列鍵映射到一個整數。一個完美的散列函數可以將密鑰分配給一個隨機整數。在指針快速之後，該值可以在RAM中或CPU的數據高速緩存中。訪問CPU的數據高速緩存然後訪問RAM要快得多。如果您的數據具有良好的空間局部性，那麼遍歷鍵/值不太可能遇到緩存未命中（這很昂貴）。一個向量具有連續的約束，所以緩存命中更有可能。再次，低掛水果第一！並不總是沖洗流更重要！ – Jerome 2011-05-11 22:25:32

我不能告訴你的數據是什麼樣子，但你可能有更好的運氣也就是說，不是使用包含地圖的地圖，而是將兩個鍵連接在一起，並將結果用作單個地圖中的鍵。另外，如果在創建地圖後未修改地圖，請考慮使用排序向量（使用std::sort和std::binary_search）。當你迭代數據時，它在內存中都是連續的，你會得到更好的緩存性能。

來源

2011-05-11 22:04:41

他的問題幾乎可以肯定的是I/O - 與他在存儲東西的容器無關。 – 2011-05-11 22:05:44

@unapersson我同意你關於I/O的想法，但這可能對下一個Google Googles map人有用效率「，所以我給了它+1。 – 2011-05-11 22:14:18

幫助，地圖通過C++

回答

相關問題