2017-07-26 1 views
3

書くのは簡単なような機能を書かなければなりませんでしたが、私が実際にやったときに期待していたよりもぎこちなくなっていました。それは本当に私を悩ましている、私はよりよい解決策があるように感じるが、私の脳はそれを考えようと狂っているので、私はあなたに良い人に向いている。3つの数字の2つのセットには、少なくとも2つの数字が共通していますか?

基本的に2つの三角形があり、共通のエッジを共有しているかどうかを知りたい。三角形はその頂点によってインデックス付けされる(すなわち、その頂点は実際の座標を含む配列のインデックスに過ぎない)ので、3つの数字の2つのセットが2つの数字を共有するかどうかを見つけることになる。私。三角形(1,2,3)と(3,1,5)はエッジを共有します(1,3)。しかし、三角形(1,2,3)と(1,5,6)はエッジ(頂点のみ)を共有せず、(1,2,3)と(4,5,6)も共有しません。

「2つの数値を共通関数」と書くとどうでしょうか?各セット内のすべての値が異なると仮定することができます(つまり、(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#ですが、質問は多かれ少なかれ命令的な言語でも同じです。

EDIT:

私がこれまで提案して(ここで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ミリ秒よりも大きなオーバーヘッドを持つと思いました(ただし、ガーベジコレクターへの圧力が高まっています)、どちらも明らかに他の方法よりもはるかに遅れています。

ありがとうございました!

+2

あなたはどの言語を使用していますか? – xenteros

+0

あなたのセットをどのように表現するかによって多くのものが異なります。また、彼らは本当のセットですか? (要素が一意であることが保証されています) – RealSkeptic

+0

使用している言語に応じて、実際のセットに数値を格納し、ライブラリ関数を使用して交差のサイズを計算します。 –

答えて

4

あなたはこのような何かを行うことができます。

これは、各セットで(あなたが述べたように)数字は単純なロジックで、その結果、別個のものであるという事実に依存
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; 
+0

2番目のCの例では、||追加することで、短絡による分岐を回避できますか? – Oskar

+0

ところで、私たちはこの時点で微少な最適化について話していることを認識していますが、できるだけ早くコードを作成する必要があります。また、私は好奇心が強いです:) – Oskar

+2

それは私も好奇心が強いです - 私はベンチマークを行い、最初に[0,300]の数字を設定し、時代は非常に似ていました。 "バリアント。しかし、短絡はまれにしか発生しなかった。その後、私は[0,15]のxとyの値を使って実験を行い、 "+"変種はより速かった(ここでは短絡が頻繁に発生し、分岐を予測するのが難しいためかもしれない)。 – qwertyman

1

私が使用します。

... 
{ 
    //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の遅延評価を使うのは素晴らしいです(==には何もしていないと仮定します)。

関連する問題