1

一意の整数のリストがあり、それらを並べ替えて、次の整数が常に残りの整数からできるだけ離れているようにしたいと考えています。

たとえば、{1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

そして、私はそれを本当に速くする必要があります。

現在、私は次のようにしています：

    static double GetDistanceIndex(int value, List<int> others)
    {
        double result=0;
        foreach (var other in others)
        {
            result += Math.Sqrt(Math.Abs(other - value));
        }

        return result;
    }

    static List<int> Sort(List<int> items, int initialValue)
    {
        items = items.ToList();
        List<int> result=new List<int>();


        lock (rnd)
        {
            while (true)
            {
                result.Add(initialValue);
                items.Remove(initialValue);
                if (items.Count == 0)
                {
                    break;
                }
                Dictionary<double, List<int>> distances = new Dictionary<double, List<int>>();
                foreach (var item in items)
                {
                    var d = GetDistanceIndex(item, result);
                    if (!distances.ContainsKey(d))
                    {
                        distances[d] = new List<int>();
                    }
                    distances[d].Add(item);
                }

                var max = distances.Keys.Max();
                var l = distances[max];
                //if (l.Count == 1)
                //{
                //    initialValue = l[0];
                //}
                //else
                //{
                initialValue = l[rnd.Next(l.Count)];
                //} 
            } 
        }

        return result;
    }

しかし問題は、このように実装されたアルゴリズムは、大きな配列に対して非常に遅く動作することです。

誰かが私にそれを行うためのより良い方法を提案できますか?

アップデート

何が行われたかについてのより良い説明は次のとおりです。

{1,2,3,4,5,6,7,8,9}=>

  1. 初期シード : 1. 実際には、任意の数にすることができます。5 を選択して、{5,9,1,2,8,3,7,6,4} のようなものを取得できます。
  2. 提供された配列から、9 は距離によって 1 から最も離れています
  3. リストでは、すべての数字が 1 と 9 から等距離にあるため、任意の数字を選択できます。rand を使用して 6 を選択しました。
  4. ここで、{1,9,6} から最も離れた数を探しています。and がor or or or orより大きいabs(2-1)+abs(2-9)+abs(2-6)=12ため、2 が選択されます。abs(3-1)+abs(3-9)+abs(3-6)=11abs(4-1)+abs(4-9)+abs(4-6)=10abs(8-1)+abs(8-9)+abs(8-6)=10abs(7-1)+abs(7-9)+abs(7-6)=9abs(5-1)+abs(5-9)+abs(5-6)=9
  5. 等

更新 1

このアルゴリズムを使用して、固定数の選択肢から可能な限り互いに異なる数を選択しています

更新 2

Dukeling は答えの中で、{1,9,2,8,3,7,4,6​​,5} も私の要件に準拠していると指摘しました。これは本当でした、そしてそれは私の間違いです。数字をできるだけ離したいのですが、最初の数字に非常に近い3次元の数字は意図したものではありません。だから私はこれを反映するために距離関数を更新しています

4

2 に答える 2

1

{1,9,2,8,3,7,4,6,5}あなたの要件に適合しているようで、生成するのはかなり簡単です。

数値を昇順/降順で並べ替えるだけです (まだ行っていない場合)。

次に、中央に到達するまで、背面と前面の両方から交互に繰り返します。このステップは線形時間で実行されます。

于 2013-10-06T12:28:26.483 に答える
1

【新距離機能に合わせて編集】

GetDistanceIndex() を繰り返し呼び出して、不要な作業を行っています。毎回最初からすべてを合計する必要はないことに注意してください。次のような配列がある場合:

[a、b、c、d、…………、x]

a、b、c、および d が既に並べ替えられている場合、新しい要素「e」を挿入すると、並べ替えられていないセット内の任意の位置「x」の距離関数の合計が、並べ替えられたセット内の他のすべての数値に加算されます。 sqrt(abs(xe)) だけ増加します。全体の合計をゼロから再計算する必要はありません。

したがって、これを最適化する方法は次のとおりです。何らかの方法を使用して、ペア (数値、距離) を格納します。C を使用している場合、たとえば、2 つの整数、値自体、および並べ替えられたセットまでの距離を持つ構造体の配列を作成できます。各ステップで、ソートされたセットにないすべてのペア (数値、距離) を調べ、その距離属性を更新します。同時に最大値を追跡できます。いくつかの擬似コード:

  • (数値、距離) のペアを保持するための補助バッファー S を作成します。

  • 距離 = sqrt(abs(initialValue - x)) で、S の initialValue と異なるすべての数値 x を挿入します。同時に最大値 m を追跡します。

  • 各ステップで、m を選択し、配列の並べ替えられた部分に移動します。S からそれを削除します。次に、S のすべての要素 y に移動し、y の距離に sqrt(abs(y.number-m.number)) を追加します。繰り返しますが、これを行う際には最大値を追跡する必要があります。すべての要素がソートされるまで、それを繰り返します。

これは優れたソリューションではありません。O(n^2) で実行されますが、GetDistanceIndex() は常に最初から開始されるため、現在のアルゴリズムは O(n^3) で実行されます。また、リストや辞書は使用せず、単純な配列を使用して、一定時間内に要素にアクセスして削除できるようにします。リストからの削除は非効率的である可能性があり、O(log(n)) よりも良くなることはありません。

現時点では、それが私が考えることができる唯一の最適化です。誰かがより良いアイデアを持っているかもしれません。

于 2013-10-06T12:42:07.890 に答える