優化算法

-3

我需要優化這個功能，但即時通訊難倒的想法，以改善它的速度......優化算法

bool generateShortestpathLink (const string& start, const string& finish, const book& db) { 
    vector <lib> bks; 
    vector <string> authors; 
    set <lib> storeBKS; 
    set <string> storeAuthor; 
    queue <pathLink> q; 

    pathLink p(start); 
    q.push(p); 

    while (!q.empty()) { 

     p = q.front(); 

     if (p.getLength() > 6) return false; 
     db.getTitles(p.getLastPlayer(), bks); 

     for (int x = 0; x < (int) bks.size(); x++) { 

      const film& newBook = bks[x]; 
      if (storeBKS.find(newBook) != storeBKS.end()) continue; 
      db.getAuthors(newBook, authors); 
      storeBKS.insert(newBook); 

      for (int i = 0; i < (int) authors.size(); i++) { 

       if (storeAuthor.find(authors[i]) != storeAuthor.end()) continue; 
       pathLink newpathLink(p); 
       newpathLink.addConnection(newBook, authors[i]); 
       if (authors[i] == finish) return true; 
       storeAuthor.insert(authors[i]); 
       q.push(newpathLink); 
      } 
     } 
     q.pop(); 
    } 

    return false; 
}

它的假設是對BFS，一個算法中它創建用於連接不同的路徑作者的書名。 getTitles()和getAuthors都是無法更改的二進制搜索功能。任何人都可以幫助我嗎？

來源

2011-08-11 SNpn

我看到的第一件事就是你沒有預先分配任何內存。這是優化不能更改算法的算法時要做的第一件事。您應該知道這些結構需要多少內存，並立即將其全部分配，以防止它們重複分配。

另外，考慮使用排序的向量而不是set。這會相當大地提高查找時間 - 只是不要太頻繁地插入，否則會受到傷害。

來源

2011-08-11 12:53:56 Puppy

我不能預先分配任何內存給它，因爲我每次都會從頭創建一個不同大小的路徑（取決於每個lvl有多少個連接器分支） – SNpn

然後假設合理的最大路徑大小，預先分配內存，如果事實證明你需要更大的路徑，請擴展緩衝區。 –

你已經特別排除了最大的優化，說getTitles()不能被觸及。循環內有一個循環。中環似乎是罪魁禍首。如此，getTitles()要求線性搜索算法。如果問題的根源在別處，則無法優化。

來源

2011-08-11 13:02:04

有沒有其他方法可以用來改進getTitles（），如果需要可以更改它，但規格確實說我不應該碰它 – SNpn

讓它返回一些東西，例如'std :: set'不要求線性搜索。一本書的作者也是如此。這也強制線性搜索，因爲它也被實現爲返回'std :: vector'。 –

我不能改變返回類型（卡住向量）使用指針添加路徑的perphaps一起增加速度？ – SNpn

回答

相關問題