兩組三個數字是否有至少兩個共同的數字？

我只是寫了一個看起來很簡單的函數，但是當我真的做到了時，結果比我預期的要更高。這真的讓我感到困擾，我覺得有一個更好的解決方案，但是我的大腦瘋狂地想着想，所以我正在轉向你。兩組三個數字是否有至少兩個共同的數字？

基本上，我有2個三角形，我想知道他們是否有共同的邊緣。三角形由它們的頂點索引（即它們的頂點只是包含實際座標的數組的索引），所以它歸結爲查找兩個三個數字集合是否有兩個共同的數字。即三角形（1,2,3）和（3,1,5）確實共享邊緣，即（1,3）邊緣。但是，三角形（1,2,3）和（1,5,6）不共享邊（僅頂點），也不共享（1,2,3）和（4,5,6）。

你會如何寫這個「兩個數字在共同的功能」？你可以假設每個集合中的所有值是不同的（即（1,1,2）不會是一個輸入），你也可以假設兩個集合不相等（即，我不打算比較（1,2,3）和（1,3,2），因爲那兩個是相同的三角形）。然而，沒有關於秩序的假設，他們沒有排序或類似的東西。

這基本上就是我想出了（假設集是（X0，X1，X2）和（Y0，Y1，Y2））：

// If the x0 is equal to any of (y0, y1, y2), make sure at least one of (x1, x2) 
// is equal to one of the y numbers 
if (x0 == y0) { 
    return x1 == y1 || x1 == y2 || x2 == y1 || x2 == y2; 
} else if (x0 == y1) { 
    return x1 == y0 || x1 == y2 || x2 == y0 || x2 == y2; 
} else if (x0 == y2) { 
    return x1 == y0 || x1 == y1 || x2 == y0 || x2 == y1; 
} else { 

    // if x0 is not equal to any of (y0, y1, y2), then x1 and x2 both have 
    // to be equal to two of the y numbers. 
    return (x1 == y0 && x2 == y1) 
     || (x1 == y0 && x2 == y2) 
     || (x1 == y1 && x2 == y0) 
     || (x1 == y1 && x2 == y2) 
     || (x1 == y2 && x2 == y0) 
     || (x1 == y2 && x2 == y1); 
}

但感覺如此血腥的我！如此多的分支和如此長的布爾語句！我覺得我錯過了一個明顯簡單的解決方案，而且這讓我瘋狂。另外，這種情況發生在對性能敏感的應用程序的內部循環中，因此性能（分支，算術等等）很重要。

順便說一句，我正在編寫的代碼是C＃，但問題是或多或少任何命令式語言相同。

編輯：

我把一個快速基準（這裏的code）與到目前爲止建議。下面是結果（以百萬隨機對三角形的運行它）：

Original method result:   7035, time elapsed in ms: 8.6252 
qwertyman method result:  7035, time elapsed in ms: 8.2537 
midjji method result:   7035, time elapsed in ms: 8.7984 
Single HashSet method result: 7035, time elapsed in ms: 184.4984 
Many HashSets method result: 7035, time elapsed in ms: 190.5785

的數字相當穩定運行之間，用@ qwertyman的方法始終是一個有點比我原來的版本或@ midjii的速度更快。它還具有成爲所有人中最乾淨和最好的優點，所以我打算繼續這樣做。

我實際上對「許多HashSet」如此接近「Single HashSet」感到有點驚訝，我想構建一百萬個HashSet的開銷會比16毫秒大（儘管這顯然不計算在內垃圾收集器的壓力增加），儘管它們顯然遠遠落後於其他方法。

感謝您的幫助！

來源

2017-07-26 Oskar

你在用什麼語言？ – xenteros

很大程度上取決於你如何表示你的設置。另外，它們是否是真集？（保證元素是唯一的） – RealSkeptic

根據您使用的語言，只需將數字存儲在實際集合中，並使用庫函數計算交集的大小。 –

你可以做這樣的事情：

int n = 0; 

// check if x0 is among the values in the second set 
if (x0 == y0 || x0 == y1 || x0 == y2) { 
    n++; 
} 

// check if x1 is among the values in the second set 
if (x1 == y0 || x1 == y1 || x1 == y2) { 
    n++; 
} 

// check if x2 is among the values in the second set 
if (x2 == y0 || x2 == y1 || x2 == y2) { 
    n++; 
} 

return n >= 2;

這依賴於一個事實，即（如你所提到的）每一組數字是不同的，導致一個簡單的邏輯。

如果您使用的是C，你可以把它寫短：

int n = 0; 

n += x0 == y0 || x0 == y1 || x0 == y2; 
n += x1 == y0 || x1 == y1 || x1 == y2; 
n += x2 == y0 || x2 == y1 || x2 == y2; 

return n >= 2;

來源

2017-07-26 13:59:08 qwertyman

在第二個C示例中，轉換||會更快嗎？另外，爲了避免短路造成的分支？ – Oskar

順便說一下，我意識到我們現在談論的是微小的優化，但我真的需要儘可能快的代碼。另外，我很好奇:) – Oskar

它讓我很好奇 - 我做了一個基準測試，並且首先設置了[0,300]中的數字，而且時間非常相似，而對於「「變種。但是，短路發生的情況很少。之後，我還對[0,15]中的x和y值進行了實驗，「+」變量更快（可能是因爲此處短路發生更頻繁，難以預測分支）。 – qwertyman

我會用：

... 
{ 
    //ti= xi in y 
    bool t0= (x0==y0) ||(x0==y1)|| (x0==y2); 
    bool t1= (x1==y0) ||(x1==y1)|| (x1==y2); 
    bool t2= (x2==y0) ||(x2==y1)|| (x2==y2); 

    return (t0 && t1) || (t0 && t2) || (t1 && t2); 
}

主要是因爲我覺得它更容易閱讀。

從性能角度看，使用正確的設置應該儘可能快。編譯器在優化自我封閉，無副作用，邏輯語句和對bool使用惰性評估方面非常出色（假設==沒有做任何愚蠢的事情）。

來源

2017-07-26 14:57:33 midjji

兩組三個數字是否有至少兩個共同的數字？

回答

相關問題