10

連続するinteger値の範囲を記述する次のインターフェイスを考えてみましょう。

public interface IRange {
    int Minimum { get;}
    int Maximum { get;}

    IRange LargestOverlapRange(IEnumerable<IRange> ranges);
} 

オブジェクトのリストを指定して、最大のオーバーラップ範囲を見つけるための効率的なアルゴリズムを探していIRangeます。この考え方は、次の図で簡単に説明されています。上の数字はinteger値を表し、最小値と最大値を持つオブジェクトを|-----|表します。ソリューションを視覚化しやすいようにIRange、オブジェクトを積み重ねました。IRange

0123456789  ...                            N
|-------|   |------------|        |-----|
   |---------|    |---|
       |---|             |------------|
               |--------|  |---------------|
                              |----------|

ここで、LargestOverlapRangeメソッドは次を返します。

                                  |---|

その範囲には合計 4 つの「重複」があるためです。同じ数のオーバーラップを持つ2 つの別々のものがあればIRange、 を返したいと思いnullます。

ここに私が試したもののいくつかの簡単なコードがあります。

public class Range : IRange 
{

    public IRange LargestOverlapRange(IEnumerable<IRange> ranges) {           

        int maxInt = 20000;    

        // Create a histogram of the counts
        int[] histogram = new int[maxInt];
        foreach(IRange range in ranges) {
            for(int i=range.Minimum; i <= range.Maximum; i++) {
                histogram[i]++;
            }
        }

        // Find the mode of the histogram
        int mode = 0;
        int bin = 0;
        for(int i =0; i < maxInt; i++) {
            if(histogram[i] > mode) {
                mode = histogram[i];
                bin = i;
            }
        }

        // Construct a new range of the mode values, if they are continuous
        Range range;
        for(int i = bin; i < maxInt; i++) {
            if(histogram[i] == mode) {  
                if(range != null)
                    return null; // violates two ranges with the same mode   
                range = new Range();             
                range.Minimum = i;                     
                while(i < maxInt && histrogram[i] == mode)
                    i++;
                range.Maximum = i;                    
            }
        }

        return range;
    }

}

これには 4 つのループが含まれ、それ以上ではないにしても簡単に O(n^2) になります。他の範囲のリストから最大のオーバーラップ範囲を見つけるためのより効率的なアルゴリズム (速度に関して) はありますか?

編集

はい、O(n^2) は正しくありません。間違って考えていました。コメントで指摘されているように、それは O(N * M) でなければなりません。

編集2

いくつかのことを規定しましょう。値の絶対的な最小値と最大値はinteger(0, 20000) からとなります。次に、平均数はIRange100 程度になります。これによってアルゴリズムの設計方法が変わるかどうかはわかりません。

編集3

私は、このアルゴリズムを科学機器 (質量分析計) に実装しています。そこでは、データ処理の速度がデータの品質にとって最も重要です (より速い分析時間 = 時間 T でより多くのスペクトルが収集されます)。ファームウェア言語 (専有) には arrays[] しかなく、オブジェクト指向ではありません。私は C# を選択しました。なぜなら、私は 2 つの言語間で概念を移植するのが得意であり、SO コミュニティの利益のために、良い答えはより多くの聴衆を獲得できると考えたからです。

4

2 に答える 2

10

範囲のリストを開始点と終了点のリストに変換します。O(n log n) アルゴリズムでリストを並べ替えます。これで、リストを繰り返し処理し、開始点か終了点かに応じてカウンターをインクリメントまたはデクリメントできます。これにより、現在のオーバーラップ深度が得られます。

于 2013-03-06T17:16:02.613 に答える
1

OPの質問を理解したので、3つの範囲が与えられた解決策

A: 012
B:  123
C:    34

は範囲12(A と B の共通サブセット) であり、範囲123ではありません (ペアの共通サブセットではないため)。


コードを書く前に、紙の上でアルゴリズムについて考えてください。動的計画法のソリューションはどうですか? (動的計画法を知らない場合は、本で読む価値があります)。動的計画法の考え方は、より単純な部分問題の解を構築することです。

f_i(n, k)最初の i 個の指定された範囲の少なくとも k 個に共通する n から始まる最長間隔のサイズを とします。

f_0 から f_1、f_1 から f_2 などを計算できます。関数の更新は、考慮される 1 つの余分な範囲に依存します。

M 個の範囲があるとします。f_M の値は、問題の答えを教えてくれます。

あなたが話した最も深い深さは、 f_M(n, k) がいくつかの n に対してゼロではないような最大の k です。その最大深度を K と呼びましょう。次に、n に対する f_M(n, K) の最大値を探します。その最大値は、最大化 n から始まる最大範囲のサイズです。

最大化する n はある範囲の下限でなければならないので、これらの種類の n に対して f を計算するだけで済みます。M 個の範囲があるため、最大でも M 個の下限になります。したがって、このアルゴリズムの複雑さは O(MMK) になります。

i 番目の範囲を a から b とする

n が a から b の範囲外の場合、変化なし
f_i(n,k) = f_i-1(n,k)

n が a から b の範囲内にある場合、新しい間隔を古い k-1 深層ソリューションと組み合わせて作成した k 深層ソリューションをテストします。すでに持っているものよりも優れている場合にのみ使用します。 f_i(n,k) = max ( f_i-1(n,k) , min( f_i-1(n,k-1) , b-n+1))


例!範囲 0 ~ 5、2 ~ 6、4 ~ 8、および 6 ~ 9 の場合。

n           0123456789

            ......          range 0 to 5
f_1(n,1)    6543210000

              .....         range 2 to 6
f_2(n,1)    6554321000
f_2(n,2)    0043210000

                .....       range 4 to 8
f_3(n,1)    6554543210  
f_3(n,2)    0043321000
f_3(n,3)    0000210000

                  ....      range 6 to 9
f_4(n,1)    6554544321
f_4(n,2)    0043323210
f_4(n,3)    0000211000
f_4(n,4)    0000000000

したがって、最も深い深度 K は 3 で、最長の範囲は 4 から 5 です。また、最長の範囲の深度 2 のサイズは 4 で、3 から始まることがわかります。

于 2013-03-06T19:41:12.237 に答える