优化算法

-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

回答

相关问题