哈希映射和向量很慢

我有一個我想要處理的大型數據集（120萬條記錄）。我的程序目前使用Google密碼散列，但仍需要29個小時才能完成，並使用來自64個GiB服務器的8.5 GiB RAM。哈希映射和向量很慢

請問您有什麼建議嗎？我是C++新手。如果我想用更快的東西來替換矢量，那會是什麼？

#include <string> 
#include <algorithm> 
#include <tr1/unordered_map> 
#include <iterator> 
#include <sstream> 
#include <cstring> 
#include <iomanip> 
#include <fstream> 
#include <vector> 
#include <iterator> 
#include <time.h> 
#include <iostream> 
#include <iostream> 
#include <sparsehash/dense_hash_map> 
#include <stdio.h> 
#include <string.h> 
using google::dense_hash_map; 
using std::tr1::hash; 
using namespace std; 
using std::string; 

bool ProcessInput(const string& inChar, vector<string> *invector); 
void Processmax(dense_hash_map < string, int>* ins, vector<int> *inc, vector<string>  *outs, vector<int> *outc); 

int main() 
{ 
time_t start, stop; 
time(&start); 
ofstream finall; 
vector<int> usrsc,artc,tmusrc,tmart2c,atrsc,tmartc; 
vector<string> tmart,tmusr,tmart2; 
vector< vector<string> > usrlist,artlist; 
string x1,x2; 
ifstream ifTraceFile; 
bool f,f2; 
dense_hash_map < string, int > a; 
dense_hash_map < string, int > u; 
a.set_empty_key(string()); 
u.set_empty_key(string()); 

int kl=0; 
ifTraceFile.open ("data2.tr", std::ifstream::in); 
while (ifTraceFile.good()) 
{ 
    ifTraceFile>>x1>> x2; 


    if (kl==0) 
    { 
     a.insert(make_pair(x1,0)); 
     u.insert(make_pair(x2,0)); 
     usrlist.push_back((vector<string>())); 
     usrlist[0].push_back(x1); 
     artlist.push_back((vector<string>())); 
     artlist[0].push_back(x2); 
     usrsc.push_back(1); 
     artc.push_back(1); 
     atrsc.push_back(1); 

    } 
    else 
    { 

     dense_hash_map < string, int>::iterator itn; 
     itn=a.find(x1); 
     if (itn == a.end()) 
     { 
      a.insert(make_pair(x1,(artlist.size()))); 
      artlist.push_back((vector<string>())); 
      artlist[(artlist.size()-1)].push_back(x2); 
      artc.push_back(1); 
      atrsc.push_back(1); 
     } 
     else 
     { 
      f=ProcessInput(x2, &artlist[itn->second]); 
      if(f) 
      { 
       artlist[itn->second].push_back(x2); 
       atrsc[itn->second]+=1; 
       artc[itn->second]+=1; 
      } 
      else 
       atrsc[itn->second]+=1; 

     } 


     dense_hash_map < string, int>::iterator its; 
     its=u.find(x2); 
     if (its == u.end()) 
     { 
      u.insert(make_pair(x2,(usrlist.size()))); 
      usrlist.push_back((vector<string>())); 
      usrlist[(usrlist.size()-1)].push_back(x1); 
      usrsc.push_back(1); 

     } 
     else 
     { 
      f2=ProcessInput(x1, &usrlist[its->second]); 

      if(f2) 
      { 
       usrlist[its->second].push_back(x1); 
       usrsc[its->second]+=1; 

      } 

     } 

    } 

    kl++; 
} 
ifTraceFile.close(); 
Processmax(&a, &artc, &tmart, &tmartc); 
Processmax(&a, &atrsc, &tmart2 ,&tmart2c); 
Processmax(&u, &usrsc ,&tmusr, &tmusrc); 
int width=15; 
cout <<"article has Max. review by users Top 1: "<<tmart.at(0)<<'\t'<<tmartc.at(0)<<endl; 
cout <<"article has Max. review by users Top 2: "<<tmart.at(1)<<'\t'<<tmartc.at(1)<<endl; 
cout <<"article has Max. review by users Top 3: "<<tmart.at(2)<<'\t'<<tmartc.at(2)<<endl; 
cout <<endl; 
cout <<"article has Max. review Top 1: "<<tmart2.at(0)<<'\t'<<tmart2c.at(0)<<endl; 
cout <<"article has Max. review Top 2: "<<tmart2.at(1)<<'\t'<<tmart2c.at(1)<<endl; 
cout <<"article has Max. review Top 3: "<<tmart2.at(2)<<'\t'<<tmart2c.at(2)<<endl; 
cout <<endl; 
cout <<"user who edited most articles Top 1: "<<tmusr.at(0)<<'\t'<<tmusrc.at(0)<<endl; 
cout <<"user who edited most articles Top 2: "<<tmusr.at(1)<<'\t'<<tmusrc.at(1)<<endl; 
cout <<"user who edited most articles Top 3: "<<tmusr.at(2)<<'\t'<<tmusrc.at(2)<<endl; 

finall.open ("results"); 
finall << "Q1 results:"<<endl;; 
finall <<"article has Max. review Top 1: "<<setw(width)<<tmart2.at(0)<<setw(width)<<tmart2c.at(0)<<endl; 
finall <<"article has Max. review Top 2: "<<setw(width)<<tmart2.at(1)<<setw(width)<<tmart2c.at(1)<<endl; 
finall <<"article has Max. review Top 3: "<<setw(width)<<tmart2.at(2)<<setw(width)<<tmart2c.at(2)<<endl; 
finall<<endl; 

finall<<"article has Max. review by users Top 1: "<<setw(width)<<tmart.at(0)<<setw(width)<<tmartc.at(0)<<endl; 
finall <<"article has Max. review by users Top 2: "<<setw(width)<<tmart.at(1)<<setw(width)<<tmartc.at(1)<<endl; 
finall <<"article has Max. review by users Top 3: "<<setw(width)<<tmart.at(2)<<setw(width)<<tmartc.at(2)<<endl; 
finall<<endl; 
finall <<"user edited most articles Top 1: "<<setw(width)<<tmusr.at(0)<<setw(width-5)<<tmusrc.at(0)<<endl; 
finall <<"user edited most articles Top 2: "<<setw(width)<<tmusr.at(1)<<setw(width-5)<<tmusrc.at(1)<<endl; 
finall <<"user edited most articles Top 3: "<<setw(width)<<tmusr.at(2)<<setw(width-5)<<tmusrc.at(2)<<endl; 
finall.close(); 
time(&stop); 
cout<<"Finished in about "<< difftime(stop, start)<< " seconds"<<endl; 

return 0; 
} 

void Processmax( dense_hash_map< string,int >* ins, vector<int> *inc, vector<string> *outs, vector<int> *outc) 
{ 
int index=0; 
int l=0; 
dense_hash_map < string, int>:: iterator iti; 
string value; 
while(l!=4) 
{ 
    vector<int>::iterator it=max_element(inc->begin(), inc->end()); 
    index = distance(inc->begin(), it); 

    for (iti = ins->begin(); iti != ins->end(); ++iti) 
    { 
     if (iti->second == index) 
     { 
      value = iti->first; 
      break; 
     } 
    } 
    outs->push_back(value); 
    outc->push_back(inc->at(index)); 
    inc->at(index)=0; 
    l++; 
    } 
} 

bool ProcessInput(const string& inChar, vector<string> *invector) 
{ 
bool index=true; 
vector<string>::iterator it=find(invector->begin(), invector->end(), inChar); 
if (it!=invector->end()) 
    index=false; 

return index; 
}

來源

2012-09-24 user1683302

在應用程序中提高速度的可靠方法是找出哪一部分是瓶頸。我建議你分析一下這段代碼，找出最需要的部分。 – Borgleader

其次。並且，使用29小時的樣本集，您將擁有*更多*的數據，足以咀嚼所需的數據（並預計它需要超過29小時）。 – WhozCraig

每條記錄有多大？（輸入文件中每個記錄的平均字節數是多少？）8.5 GiB/120 M記錄表明每個記錄約70個字節，忽略了開銷;與開銷，數據的每個記錄相差很少。 –

謝謝你的幫助。我現在可以在10分鐘內得到結果。只要！！！！！！！！！

unordered_map < string, unordered_set <string> > a; 
    unordered_map < string, unordered_set <string> > u; 
    unordered_map < string, int > artc,usrc,artac; 
    ..... 
    .... 
    if (true) 
    { 
     a[x1].insert(x2); 
     u[x2].insert(x1); 
     artc[x1]=a[x1].size(); 
     usrc[x2]=u[x2].size(); 
     artac[x1]++; 
    }

unordered_map比google密集哈希快100％，它比RAM密度少30％的RAM。

來源

2012-09-26 01:06:36 user1683302

如果通過更改哈希仿函數，您的鑰匙具有相當大的尺寸，您仍然可以獲得更多的速度。看到[這個問題]（http://stackoverflow.com/q/8372579/500104）的原因。 – Xeo

+1很高興你找到答案。所以std :: unordered_set更適合您的需要，而不是Google密碼散列。注意= =） – Viet

您可能需要遵循幾個簡單的步驟：

數據

取子集（比如說1/100或1/1000）
通過樣本數據運行程序探查下
找到瓶頸並優化它

一些鏈接閱讀：

http://www.sgi.com/tech/stl/complexity.html

Quick and dirty way to profile your code

vector vs. list in STL

來源

2012-09-24 03:19:17 Viet

不要使示例數據太小，否則它不會反映緩存未命中。 – bitmask

對，不要太小:) – Viet

感謝您的鏈接，我測試我的程序50000記錄。我發現谷歌密度如果很快，並不會像矢量一樣影響尺寸。 – user1683302

由正在打印的數據來看，你想這裏僅列出前3個左右的用戶在每個多個類的。您不需要存儲所有數據，只需要將當前排名前三的用戶存儲在每個類別中。當新記錄到達時，您可以確定它是否替換任何類別中的前三項，如果是，則安排新數據替換適當的舊數據。如果新記錄「無趣」，則忽略它。將有趣的用戶數量作爲計算的一個參數;解決頂部N的一般情況，然後將N設置爲3.

這會將您的存儲空間限制爲幾個最大KiB。你還可以使用更小的數據結構進行操作，所以它們會更快。你的處理時間應該下降到讀取文件大小的時間，這不是29個小時。

來源

2012-09-24 05:42:38

+1這很好。基本上改變算法:) – Viet

謝謝你的建議，我知道我已經包括額外的頭我會修復它。我不能告訴哪個用戶做出了最大的貢獻，直到我讀取所有的數據。我的樣本只有1000條記錄，但我的實際數據是1.2億條記錄。我在29個小時後得到了結果。我只是收集兩個屬性，但在未來我必須收集其中五個屬性。我認爲瓶頸也是在整合中的矢量搜索。我想用更快的搜索替換矢量。像unorderd_set的地圖和像列表地圖一樣整合的東西。謝謝 – user1683302

如果你正在積累數據，那就更難了。你有沒有考慮過使用DBMS？考慮到一個明智的模式，他們應該從僅僅1.2億行中取出百分之一。基本上，我認爲你需要從根本上改變你的算法，如果你想讓你的答案更快。創造性思考;做非常不同的事情。 –

哈希映射和向量很慢

回答

相關問題