c# - C＃で「5の中央値」を計算するにはどうすればよいですか？

Question

中央値5は、アルゴリズム設計の演習として使用されることがあり、 6つの比較のみを使用して計算できることが知られています。

この「6つの比較を使用した5つの中央値」をC＃で実装するための最良の方法は何ですか？私のすべての試みは厄介なコードをもたらすようです:(まだ6つの比較だけを使用しながら、私は素晴らしくて読みやすいコードが必要です。

public double medianOfFive(double a, double b, double c, double d, double e){
    //
    // return median
    //
    return c;
}

注：ここでも「アルゴリズム」を提供する必要があると思います。

Azerealがフォーラムの投稿で行ったように、アルゴリズムを明確に説明できないことに気づきました。そこで、ここで彼の投稿を参照します。http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085から

さて、私は自分の課題の1つでこの問題を提起され、このフォーラムに助けを求めましたが、ここには助けがありませんでした。私は最終的にそれを行う方法を見つけました。

1. 最初の4つの要素でマージソートを開始し、各ペアを並べ替えます（2つの比較）

2. 各ペアの下の2つを比較し、可能性から最も低いものを除外します（3つの比較）

3. ペアのない数に取っておいた5番目の数を追加し、2つを比較します（4つの比較）

4. 2つの新しいペアのうち最も低い2つのペアを比較し、下のペアを削除します（5つの比較）

5. 1つだけを比較し、最後のペアの小さい方を比較します。小さい方の数値が中央値です。

   可能な中央値は括弧内にあります

（54321）

5：4 3：22比較

（4 <5 2 <3 1）

4：23比較

2（4 <5 3 1）

1：34比較

2（4 <5 1 <3）

4：15比較

1,2（4 <5 3）

4：36比較

1,2（3）4,5

3つは中央値です

これは、中央値5を見つけるために私が書いたC++コードです。その厄介さを気にしないでください：

double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
    double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
    double *tmp;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    if(*d < *c){
        tmp = c; c = d; d = tmp;
    }

    // eleminate the lowest
    if(*c < *a){
        tmp = b; b = d; d = tmp; 
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b and b < d
    if(*b < *a){
        tmp = a; a = b; b = tmp;
    }

    // eliminate another lowest
    // remaing: a,b,d
    if(*a < *c){
        tmp = b; b = d; d = tmp; 
        a = c;
    }

    if(*d < *a)
        return *d;
    else
        return *a;

} 

もっとコンパクトなはずですね。

---

@pablitoが彼の回答で指摘したように、ビルトインList.Sort()は最大13の比較を使用するため、この要件を満たすことはできません：]

Answer 1

私はこの投稿が面白いと感じました。演習として、6つの比較のみを行い、他には何も行わないこれを作成しました。

static double MedianOfFive(double a, double b, double c, double d, double e)
{
    return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d
                                                 : c < a ? c : a
                                         : e < d ? a < d ? a : d
                                                 : c < e ? c : e
                                 : c < e ? b < c ? a < c ? a : c
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : c < b ? c : b
                         : b < c ? a < e ? a < c ? e < c ? e : c
                                                 : d < a ? d : a
                                         : e < c ? a < c ? a : c
                                                 : d < e ? d : e
                                 : d < e ? b < d ? a < d ? a : d
                                                 : e < b ? e : b
                                         : b < e ? a < e ? a : e
                                                 : d < b ? d : b
                 : d < c ? a < d ? b < e ? b < d ? e < d ? e : d
                                                 : c < b ? c : b
                                         : e < d ? b < d ? b : d
                                                 : c < e ? c : e
                                 : c < e ? a < c ? b < c ? b : c
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : c < a ? c : a
                         : a < c ? b < e ? b < c ? e < c ? e : c
                                                 : d < b ? d : b
                                         : e < c ? b < c ? b : c
                                                 : d < e ? d : e
                                 : d < e ? a < d ? b < d ? b : d
                                                 : e < a ? e : a
                                         : a < e ? b < e ? b : e
                                                 : d < a ? d : a;
}

Answer 2

これは基本的に、C++の例からスワッピングとソートのコードを除外しているだけです。

private static void Swap(ref double a, ref double b) {
    double t = a;
    a = b;
    b = t;
}

private static void Sort(ref double a, ref double b) {
    if (a > b) {
        double t = a;
        a = b;
        b = t;
    }
}

private static double MedianOfFive(double a, double b, double c, double d, double e){
    // makes a < b and c < d
    Sort(ref a, ref b);
    Sort(ref c, ref d);

    // eleminate the lowest
    if (c < a) {
        Swap(ref b, ref d);
        c = a;
    }

    // gets e in
    a = e;

    // makes a < b
    Sort(ref a, ref b);

    // eliminate another lowest
    // remaing: a,b,d
    if (a < c) {
        Swap(ref b, ref d);
        a = c;
    }

    return Math.Min(d, a);
}

Answer 3

ありがとう。あなたの投稿がかなり古いことは知っていますが、私の問題には役立ちました。

5 つの SSE/AVX レジスタ (一度に 4 つの float / 8 つの float、または一度に 2 つの double / 4 つの double) の中央値を計算する方法が必要でした。

• 条件付きジャンプなし

• 最小/最大命令のみ

最小/最大関数が条件付きジャンプのあるスカラー レジスタ用にプログラムされている場合、私のコードは比較に関して最適ではありません。しかし、最小/最大関数が対応する CPU 命令でコーディングされている場合、実行時に CPU によって条件付きジャンプが行われないため、私のコードは非常に効果的です。

    template<class V> 
    inline V median(const V &a, const V &b, const V &c)
    {
      return max(min(a,b),min(c,max(a,b))); 
    } 

    template<class V> 
    inline V median(const V &a, const V &b, const V &c, const V &d, const V &e)
    {
      V f=max(min(a,b),min(c,d)); // discards lowest from first 4
      V g=min(max(a,b),max(c,d)); // discards biggest from first 4
      return median(e,f,g);
    } 

Answer 4

ここに興味深いスレッドがあります：

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

スレッドからの引用:

1. 数値を配列に入れます。

2. 3 つの比較を使用し、a[1] < a[2]、a[4] < a[5]、および a[1] < a[4] となるように数値をシャッフルします。

3. a[3] > a[2] の場合、問題はかなり簡単です。a[2] < a[4] の場合、中央値は a[3] と a[4] の小さい方です。そうでない場合、中央値は a[2] と a[5] の小さい方になります。

4. つまり、a[3] < a[2] です。a[3] > a[4] の場合、解は a[3] と a[5] の小さい方になります。それ以外の場合、解は a[2] と a[4] の小さい方になります。

Answer 5

これはかなり醜いので、リファクタリングを使用することもできますが、すべての比較とスワップを明示的に処理するため、何が起こっているかを確認できます。

public double medianOfFive(double a, double b, double c, double d, double e){
    double median;
    // sort a and b
    if(a > b) // comparison # 1
    {
        double temp = a;
        a = b;
        b = temp;
    }

    // sort c and d
    if(c > d)  // comparison # 2
    {
        double temp = c;
        c = d;
        d = temp;
    }

    // replace the lower of a and c with e
    // because the lowest of the first four cannot be the median
    if(a < c) // comparison # 3
    {
        a = e;
        // re-sort a and b
        if(a > b) // comparison # 4
        {
            double temp = a;
            a = b;
            b = temp;
        }
    }
    else
    {
        c = e;
        // re-sort c and d
        if(c > d)  // comparison # 4
        {
            double temp = c;
            c = d;
            d = temp;
        }
    }

    // eliminate a or c, because the lowest
    // of the remaining four can't be the median either
    if(a < c) // comparison #5
    {
         if(b < c) // comparison #6
         {
              median = c;
         }
         else
         {
              median = b;
         }
    }
    else
    {
         if(d < a) // comparison #6
         {
              median = a;
         }
         else
         {
              median = d;
         }
    }
    return median;
}

Answer 6

比較の数を確認するだけです：

    class MyComparable : IComparable
{

    public static int NumberOfComparisons = 0;

    public int NumPart { get; set; }

    #region IComparable Members

    public int CompareTo(object obj)
    {
        NumberOfComparisons++; //I know, not thread safe but just for the sample
        MyComparable mc = obj as MyComparable;
        if (mc == null)
            return -1;
        else
            return NumPart.CompareTo(mc.NumPart);
    }

    #endregion
}

class Program
{
    static void Main(string[] args)
    {
        List<MyComparable> list = new List<MyComparable>();
        list.Add(new MyComparable() { NumPart = 5 });
        list.Add(new MyComparable() { NumPart = 4 });
        list.Add(new MyComparable() { NumPart = 3 });
        list.Add(new MyComparable() { NumPart = 2 });
        list.Add(new MyComparable() { NumPart = 1 });
        list.Sort();


        Console.WriteLine(MyComparable.NumberOfComparisons);
    }
}

結果は 13 です。

Answer 7

これはそれを行う必要があります

private Double medianofFive(double[] input)
{
    Double temp;
if (input[0] > input[1])//#1 - sort First and Second
{
    temp = input[0];
    input[0] = input[1];
    input[1] = temp;
}
if (input[2] > input[3])//#2 sort Third and Fourth
{
    temp = input[2];
    input[2] = input[3];
    input[3] = temp;
}

// replace the smaller of first and third with 5th, then sort
int smallerIndex = input[0] < input[2] ? 0 : 2;//#3
input[smallerIndex] = input[4];

//sort the new pair
if(input[smallerIndex]>input[smallerIndex+1])//#4
{
    temp = input[smallerIndex];
    input[smallerIndex] = input[smallerIndex+1];
    input[smallerIndex+1] = temp;
}

//compare the two smaller numbers
// then compare the smaller of the two's partner with larger of the two
// the smaller of THOSE two is the median
if (input[2] > input[0])
//#5
{
    temp = input[2] > input[1] ? input[1] : input[2];//#6
}
else
{
    temp = input[0] > input[3] ? input[3] : input[0];//#6
}
    return temp;
}

Answer 8

MSDNサンプルでの比較の数は興味深い...

public static double Median(this IEnumerable<double> source) {
        if (source.Count() == 0)  throw new InvalidOperationException("Cannot compute median for an empty set.");

        var sortedList = from number in source
                         orderby number
                         select number;

        int itemIndex = (int)sortedList.Count() / 2;

        if (sortedList.Count() % 2 == 0) {
            // Even number of items.
            return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else {
            // Odd number of items.
            return sortedList.ElementAt(itemIndex); }
    }