与えられたのは 3 つの数値の配列で、3 つの数値の中間値を知りたいです。
問題は、3 つの中間を見つける最速の方法は何かということです。
私のアプローチはこの種のパターンです.3つの数字があるため、6つの順列があります:
if (array[randomIndexA] >= array[randomIndexB] &&
array[randomIndexB] >= array[randomIndexC])
誰かがこれを行うためのよりエレガントで高速な方法を見つけるのを手伝ってくれれば、それは本当に素晴らしいことです.
ここには、最小/最大でブランチを使用しない回答があります( https://stackoverflow.com/a/14676309/2233603 )。実際には、中央値を見つけるには 4 回の最小/最大操作で十分です。xor は必要ありません。
median = max(min(a,b), min(max(a,b),c));
ただし、中央値のインデックスは得られません...
すべてのケースの内訳:
a b c
1 2 3 max(min(1,2), min(max(1,2),3)) = max(1, min(2,3)) = max(1, 2) = 2
1 3 2 max(min(1,3), min(max(1,3),2)) = max(1, min(3,2)) = max(1, 2) = 2
2 1 3 max(min(2,1), min(max(2,1),3)) = max(1, min(2,3)) = max(1, 2) = 2
2 3 1 max(min(2,3), min(max(2,3),1)) = max(2, min(3,1)) = max(2, 1) = 2
3 1 2 max(min(3,1), min(max(3,1),2)) = max(1, min(3,2)) = max(1, 2) = 2
3 2 1 max(min(3,2), min(max(3,2),1)) = max(2, min(3,1)) = max(2, 1) = 2
ハードウェアが分岐なしで最小および最大クエリに応答できる場合、分岐なしでクエリに応答することが可能です (現在のほとんどの CPU はこれを実行できます)。
演算子 ^ は、ビットごとの xor を示します。
Input: triple (a,b,c)
1. mx=max(max(a,b),c)
2. mn=min(min(a,b),c)
3. md=a^b^c^mx^mn
4. return md
これは次の理由で正しいです。
int/float には、適切な最小/最大関数を選択する必要があります。正の浮動小数点のみが存在する場合は、整数の最小値/最大値を浮動小数点表現で直接使用することができます (整数演算は一般に高速であるため、これは望ましいことです)。
ハードウェアが最小/最大をサポートしていないというまれなシナリオでは、次のようなことを行うことができます。
max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2
ただし、正確な最小/最大が必要であり、それに近いものではないため、フロート操作を使用する場合、これは正しくありません。幸いなことに、float min/max はハードウェアで長い間サポートされてきました (x86 では Pentium III 以降)。
あなたが最も効率的な解決策を探しているなら、それは次のようなものだと思います：
if (array[randomIndexA] > array[randomIndexB]) {
if (array[randomIndexB] > array[randomIndexC]) {
return "b is the middle value";
} else if (array[randomIndexA] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "a is the middle value";
}
} else {
if (array[randomIndexA] > array[randomIndexC]) {
return "a is the middle value";
} else if (array[randomIndexB] > array[randomIndexC]) {
return "c is the middle value";
} else {
return "b is the middle value";
}
}
このアプローチでは、少なくとも 2 つ、多くても 3 つの比較が必要です。2つの値が等しい可能性を意図的に無視します（質問のように）。これが重要な場合は、アプローチを拡張してこれもチェックできます。
これは、最大2つの比較で実行できます。
int median(int a, int b, int c) {
if ( (a - b) * (c - a) >= 0 ) // a >= b and a <= c OR a <= b and a >= c
return a;
else if ( (b - a) * (c - b) >= 0 ) // b >= a and b <= c OR b <= a and b >= c
return b;
else
return c;
}
そして、もう1つのアイデア。3 つの数字があります{a,b,c}。それで：
middle = (a + b + c) - min(a,b,c) - max(a,b,c);
もちろん、数値制限について覚えておく必要があります...
条件のみを使用してこれを表現する方法は次のとおりです。
int a, b, c = ...
int middle = (a <= b)
? ((b <= c) ? b : ((a < c) ? c : a))
: ((a <= c) ? a : ((b < c) ? c : b));
編集:
スワップを実装するソリューションは見当たりませんでした:
int middle(int a, int b, int c) {
// effectively sort the values a, b & c
// putting smallest in a, median in b, largest in c
int t;
if (a > b) {
// swap a & b
t = a;
a = b;
b = t;
}
if (b > c) {
// swap b & c
t = b;
b = c;
c = t;
if (a > b) {
// swap a & b
t = a;
a = b;
b = t;
}
}
// b always contains the median value
return b;
}
median = (a+b+c) - Math.min(Math.min(a,b),c) - Math.max(Math.max(a,b),c)
これは基本的なものです。これがどれほど効率的に機能するかはわかりませんが、これらの関数は if 条件を使用します。必要に応じて、このステートメントを if-else ステートメントに変換できますが、時間がかかります。なぜそんなに怠惰なのですか？
これを最も簡単な方法で書くこともできます。あなたが言ったように、6つの可能性しかありません。合理的なアプローチで速くも遅くもならないので、読みやすいものを選んでください。
簡潔にするために min() と max() を使用しますが、ネストされた 3 つの if/then も同じくらい良いと思います。
いくつかの基準を満たす X 値の 1 つを見つける必要がある場合は、少なくともその値を X-1 個の他の値と比較する必要があります。値が 3 つの場合、これは少なくとも 2 回の比較を意味します。これは「最小でも最大でもない値を見つける」ため、2 回の比較だけで済みます。
次に、コードの記述に集中して、何が起こっているのかを非常に明確に理解し、シンプルに保つ必要があります。ここでは、ネストされた if を意味します。これにより、JVM は実行時にこの比較を可能な限り最適化できます。
この例については、Tim が提供するソリューション (トリプルの中間値を見つける最速の方法? ) を参照してください。多くのコード行は、ネストされた疑問符コロンよりも大きなコードになるとは限りません。
Gyorgy からの優れた回答に基づいて、最小/最大を条件付きの動きに置き換えることで、分岐なしで中央値のインデックスを取得できます。
int i = (array[A] >= array[B]) ? A : B;
int j = (array[A] <= array[B]) ? A : B;
int k = (array[i] <= array[C]) ? i : C;
int median_idx = (array[j] >= array[k]) ? j : k;
javac は、これらの 3 項割り当てごとに ConditionalNode を生成する必要があります。これcmp/cmovは、アセンブリ内のペアに変換されます。また、等しい場合はアルファベット順の最初のインデックスが返されるように比較が選択されていることにも注意してください。
方法 1
int a,b,c,result;
printf("enter three number");
scanf("%d%d%d",&a,&b,&c);
result=a>b?(c>a?a:(b>c?b:c)):(c>b?b:(a>c?a:c));
printf("middle %d",result);
方法 2
int a=10,b=11,c=12;
//Checking for a is middle number or not
if( b>a && a>c || c>a && a>b )
{
printf("a is middle number");
}
//Checking for b is middle number or not
if( a>b && b>c || c>b && b>a )
{
printf("b is middle number");
}
//Checking for c is middle number or not
if( a>c && c>b || b>c && c>a )
{
printf("c is middle number");
}
方法 3
if(a>b)
{
if(b>c)
{
printf("b is middle one");
}
else if(c>a)
{
printf("a is middle one");
}
else
{
printf("c is middle one");
}
}
else
{
if(b<c)
{
printf("b is middle one");
}
else if(c<a)
{
printf("a is middle one");
}
else
{
printf("c is middle one");
}
}
トリプルの中間値を見つける適切な答えを得ました
largest=(a>b)&&(a>c)?a:(b>c?b:c);
smallest=(a<b)&&(a<c)?a:(b<c?b:c);
median=a+b+c-largest-smallest;
これは機能します：
template<typename T> T median3_1_gt_2(const T& t1, const T& t2, const T& t3) {
if (t3>t1) {
return t1;
} else {
return std::max(t2, t3);
}
}
template<typename T> T median3(const T& t1, const T& t2, const T& t3) {
if (t1>t2) {
return median3_1_gt_2(t1, t2, t3);
} else {
return median3_1_gt_2(t2, t1, t3);
}
}
ary で idxA から idxC を使用すると、
int ab = ary[idxA] < ary[idxB] ? idxA : idxB;
int bc = ary[idxB] < ary[idxC] ? idxB : idxC;
int ac = ary[idxA] < ary[idxC] ? idxA : idxC;
int idxMid = ab == bc ? ac : ab == ac ? bc : ab;
indexMiddle は中間値を指します。
説明: 3 つの最小値から 2 が全体の最小値であり、他の値は中間でなければなりません。等しいかどうかをチェックするため、配列の値を比較する代わりに、最後の行のインデックスを比較できます。
これはPythonでの答えですが、同じロジックがJavaプログラムにも当てはまります。
def middleOfThree(a,b,c):
middle = a
if (a < b and b < c) or (c < b and b < a):
middle = b
elif (a < c and c < b) or (b < c and c < a):
middle = c
print 'Middle of a=%d, b=%d, c=%d is %d' % (a,b,c,middle)
middleOfThree(1,2,3)
middleOfThree(1,3,2)
middleOfThree(2,1,3)
middleOfThree(2,3,1)
middleOfThree(3,2,1)
middleOfThree(3,1,2)
または、中間値を含む配列内のインデックスを見つけるためのワンライナー:
int middleIndex = (a[0]<a[1]) ? ((a[0]<a[2) ? a[2] : a[0]) : ((a[1]<a[2) ? a[2] : a[1]);
これらの多くは、かなり複雑な if ステートメントを使用しているようです。Math ライブラリを使用して、非常に簡単な回避策を見つけました。
Math.max(Math.min(array[start], array[mid]), Math.min(array[start], array[mid], array[end]))
かなりうまくいきます。