外部ストレージなしで整備します

StackOverflow https://stackoverflow.com/questions/9359840

  •  28-10-2019
  •  | 
  •  

質問

ソートされた値を持つ2つの配列を1つにマージしたいと思います。両方のソースアレイは、大きな配列の後続の部分として保存されているため、それらを大きなストレージにマージする方法を知っているかどうか疑問に思います。意味のあるマージ。

私が見つけたすべての方法では、外部ストレージが必要です。多くの場合、SQRT（N）温度アレイが必要です。それなしで効率的な方法はありますか？

C＃を使用しています。他の言語も歓迎します。前もって感謝します！

役に立ちましたか？

解決

AFAIKは、2つの（並べ替えられた）配列をマージすると、必要な数の比較と要素の動きを大幅に増やすことなく、その場で機能しません。見る： ソートをマージします. 。ただし、ブロックされたバリエーションが存在します。これは、lenght sqrt（n）の一時的な配列を使用することにより、長さnのリストを並べ替えることができます - あなたが書いたように - 操作の数をかなり低く保つことによって..それは悪くありません - しかし、それはまた「何も」ではなく、明らかにあなたが得ることができる最高のものです。

実際の状況と、余裕があれば、一時的な配列を使用してリストをマージすることをお勧めします。

他のヒント

値が大きな配列の後続の部分として保存されている場合、配列をソートするだけで、等しい連続した値を削除します。 

void  SortAndDedupe(Array<T> a)
{
    // Do an efficient in-place sort
    a.Sort();
    // Now deduplicate
    int lwm = 0; // low water mark
    int hwm = 1; // High water mark
    while(hwm < a.length)
    {
        // If the lwm and hwm elements are the same, it is a duplicate entry.
        if(a[lwm] == a[hwm])
        {
            hwm++;
        }else{
            // Not a duplicate entry - move the lwm up
            // and copy down the hwm element over the gap.
            lwm++;
            if(lwm < hwm){
                a[lwm] = a[hwm];
            }
            hwm++;
        }
    }
    // New length is lwm
    // number of elements removed is (hwm-lwm-1)
}

これが遅すぎると結論付ける前に、実装してプロファイルします。それには約10分かかります。

編集： もちろん、これは、実際にパフォーマンスが向上することに応じて、組み込みのソート、EたとえばQuickSort、Heapsort、またはSmoothSortなどではなく、異なる種類を使用することで改善できます。ハードウェアアーキテクチャの問題は、実際のパフォーマンスの比較が大きなO分析の結果とは大きく異なる可能性があることに注意してください。

実際、実際のハードウェア/OSプラットフォームで異なるソートアルゴリズムでプロファイルする必要があります。

ノート： 私はこの答えで学術的な答えを与えることを試みていません。あなたが本当の問題を解決しようとしている仮定について、私は実用的な答えを与えようとしています。

外部ストレージを気にしないでください。 SQRT（n）またはそれ以上のパフォーマンスに害を及ぼさないでください。ストレージがプールされていることを確認する必要があります。特に大きなデータの場合。特にループでそれらをマージするため。それ以外の場合、GCはストレスを感じ、CPU時間 /メモリ帯域幅のかなりの部分を食べます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top