3

私は知識を増やすために少し実験をしていて、それを本当に最適化できると感じる部分に到達しましたが、これを行う方法がよくわかりません。

数字の配列がたくさんあります。（簡単にするために、各配列に1、2、3、および4の4つの数値があるとします）

  • 目標は、すべての番号を昇順（つまり、1-2-3-4）にすることですが、番号はすべて異なる配列でスクランブルされています。

  • 数値が大きいほど、重みが大きくなります。

  • これらの配列をすべて、ターゲットに近い順に並べ替える必要があります。

つまり、4-3-2-1が最悪のケースになります。

いくつかの例：

3-4-2-1 is better than 4-3-2-1
2-3-4-1 is better than 1-4-3-2 (even though two numbers match (1 and 3). 
                                the biggest number is closer to its spot.)

したがって、大きな数字は常に小さな数字よりも優先されます。これが私の試みです：

        var tmp = from m in moves
                  let mx = m.Max()
                  let ranking = m.IndexOf(s => s == mx)
                  orderby ranking descending
                  select m;

        return tmp.ToArray();

上記の例のPSIndexOfは、配列と式を取得し、式を満たす要素のインデックスを返すために作成した拡張機能です。状況は実際にはもう少し複雑なので、これが必要です。私の例で単純化しています。

ただし、ここでの私の試みの問題は、最大数でのみソートされ、他のすべての数を忘れてしまうことです。最初に最大数、次に2番目に大きい数、次に3番目にランク付けする必要があります。

また、この操作は数分間何度も繰り返されるので、可能な限り効率的にする必要があります。

4

2 に答える 2

1

バブルソートを実装して、データを移動する必要がある回数を数えることができます。ソートされた理想から遠く離れたアレイでは、データ移動の数が多くなります。

int GetUnorderedness<T>(T[] data) where T : IComparable<T>
{
    data = (T[])data.Clone(); // don't modify the input data, 
                              // we weren't asked to actually sort.
    int swapCount = 0;
    bool isSorted;
    do
    {
        isSorted = true;
        for(int i = 1; i < data.Length; i++)
        {
            if(data[i-1].CompareTo(data[i]) > 0)
            {
                T temp = data[i];
                data[i] = data[i-1];
                data[i-1] = temp;
                swapCount++;
                isSorted = false;
            }
        }
    } while(!isSorted);
}

サンプルデータから、これは指定したものとはわずかに異なる結果をもたらします。

いくつかの例：
3-4-2-1は4-3-2-1よりも
優れている2-3-4-1は1-4-3-2よりも優れている

3-4-2-1ソートには5回のスワップが4-3-2-1必要で、6回のスワップが必要です。
2-3-4-13を取ります、1-4-3-2また3を取ります、それでこれはあなたの期待される結果と一致しません。

このアルゴリズムは、最大数を最も重要なものとして扱いません。これはあなたが望むようです。すべての数値は同等に扱われます。あなたの説明から、最初のものは適切な場所に最大数と2番目に大きい数の両方を持っているので、あなたは2-1-3-4よりもはるかに良いと考えるでしょう。1-2-4-3このアルゴリズムでは、配列をソートするためにそれぞれ1つのスワップしか必要としないため、これら2つは等しいと見なされます。

このアルゴリズムには、単なる比較アルゴリズムではなく、各入力に個別の出力があるという利点があります。そのため、入力配列ごとに1回だけアルゴリズムを実行する必要があります。

于 2012-10-07T18:48:45.210 に答える
0

これがお役に立てば幸いです

var i = 0;
var temp = (from m in moves select m).ToArray();
do
{
  temp = (from m in temp
         orderby m[i] descending
         select m).ToArray();
}
while (++i < moves[0].Length);
于 2012-10-07T06:29:48.243 に答える