有什麼辦法可以使這個座標比較函數更有效嗎？

以下函數使用三個單詞對象，並檢查每個單詞的字母座標（在表格中）。這個想法是從一個沒有相交字母座標的列表中獲得三個單詞的組合。但是，當您有超過600000種可能的組合時，這會變得非常耗時。有什麼辦法可以使這個座標比較函數更有效嗎？

bool lettersIntersect(word one, word two, word three) 
{ 
    for(int i = 0; i < one.getLength(); i++) 
     for(int j = 0; j < two.getLength(); j++) 
      if(one.getLetterPosition(i).x == two.getLetterPosition(j).x && one.getLetterPosition(i).y == two.getLetterPosition(j).y) 
       return true; 
    for(int i = 0; i < two.getLength(); i++) 
     for(int j = 0; j < three.getLength(); j++) 
      if(two.getLetterPosition(i).x == three.getLetterPosition(j).x && two.getLetterPosition(i).y == three.getLetterPosition(j).y) 
       return true; 
    for(int i = 0; i < three.getLength(); i++) 
     for(int j = 0; j < one.getLength(); j++) 
      if(three.getLetterPosition(i).x == one.getLetterPosition(j).x && three.getLetterPosition(i).y == one.getLetterPosition(j).y) 
       return true; 
    return false; 
}

有沒有更有效的方法呢？

來源

2013-04-04 Kesarion

從它看起來像是參數（容器）的角度來看，以基本的基礎開始：通過const引用傳遞它們。除此之外，知道這個類的定義（'word'）在回答你的問題時可能會有很長的路要走。 – WhozCraig 2013-04-04 13:00:44

我可以給你一個提示，它立即擊中了我。不要怪我，如果它的誤導。你可以嘗試一次，看看你的表現。

創建每個字圖（使用STL）對象即map_one，map_two，和map_three

添加座標值作爲對於給定的字對象的每個字母到其相應的映射鍵。

然後檢查使用這些地圖是否有交集。 Check if map in C++ contains all the keys from another map

來源

2013-04-04 13:39:55

嗯，起初這似乎是個好主意，但我認爲地圖對於更大的表格會更好。對於我的小桌子，這種方法將執行時間增加到原來的兩倍。然而，你的想法給了我一個更好的想法。使用一個矢量，只有3個語句，我設法減少執行時間三次！現在通過將進程分解成線程，我應該在一秒之內完成它。謝謝！ – Kesarion 2013-04-04 19:41:04

我看到可能的唯一的事，以優化被避免雙重檢查：

for(int i = 0; i < one.getLength(); i++) 
     for(int j = i+1; j < two.getLength(); j++) 
      if(one.getLetterPosition(i).x == two.getLetterPosition(j).x && one.getLetterPosition(i).y == two.getLetterPosition(j).y) 
      return true;

for循環第二次是從j = 0改變，至j = i + 1的，它讓你做一半的檢查時間。

在兩個座標點之間檢查是一個n^2（n-square）問題，這意味着執行檢查所需的時間與可以檢查的元素數量的平方成正比。我希望除了避免雙重檢查之外，沒有其他方法可以優化這一點，就像我解釋的那樣。

當然，除了通過引用傳遞之外，像已經提示給你。

來源

2013-04-04 13:13:16

在這個家庭作業問題或其他學習練習中，您打算使用之前教過的重新排列數據的方法，以加快搜索速度。重新排列數據後，您應該能夠找到一種有效地掃描它以查找重複項的方法。

來源

2013-04-04 13:27:19

有什麼辦法可以使這個座標比較函數更有效嗎？

回答

相關問題