1

これが私がやろうとしていることです。定期的に呼び出されるmerge（）というルーチンがあります。そのタスクは、「ブロック」と呼ばれるデータ構造をマージすることです。このデータ構造の内容は、「s_idx」と「e_idx」で表される整数の範囲であり、それぞれ開始インデックスと終了インデックスを示します。隣接するブロックは、その範囲を新しい連続した範囲に組み合わせることができるブロックです。たとえば、範囲（25,32）のブロック3と範囲（33,40）のブロック4は隣接しているため、それらの範囲を組み合わせて、新しい連続した範囲（25,40）を生成できます。したがって、最後に、残りのブロックは1つだけになり、個々のブロックをすべて組み合わせて範囲（0、N-1）を生成します。ここで、Nはブロックの総数です。

私の質問は：そのような操作を実行するための効率的なアルゴリズムはありますか？

現在の実装では、O（N ^ 2）アルゴリズムを使用しています。これは、ブロック数が増えるにつれて劇的に遅くなります。

for( int i=0 ; i<_merge_list.max()-1 ; i++ )
    {
        for( int j=i+1 ; j<_merge_list.max() ; j++ )
        {
            if( _merge_list.exist(i) && _merge_list.exist(j) )
            {
                if( _merge_list[i]->get_end_idx() + 1 ==    _merge_list[j]->get_start_idx() )
                {
                    _merge_list[i]->set_end_idx( _merge_list[j]->get_end_idx() );
                    _merge_list[i]->set_link( _merge_list[j]->get_block_idx() );


                                    perform(_merge_list[i]);

                    _merge_list.remove(j);          
                }
            }
        }

    }
4

1 に答える 1

1

すべてのブロックが隣接していることが保証されていますか？その場合、O（N）時間で最小、最大インデックスを見つけて、最後のブロックを1つ作成するのは簡単です。そうでない場合は、最初にブロックを並べ替えてから、O（NlogN）+ O（N）= O（NlogN）をマージできます。

ソートされた方法でブロックを維持する場合、ブロックをマージするのにO（N）時間しかかかりません。それらをすべて一度に持っている場合は、最初にブロックの配列を並べ替えてから、マージします。それらを断片的に取得した場合は、並べ替えられた順序を維持する方法でブロックの配列にマージします。

于 2012-05-11T12:29:34.957 に答える