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