9

2つの数値範囲が交差するかどうかを確認するための最良の方法は何ですか？

私の番号範囲は3023-7430ですが、次の番号範囲のどれがそれと交差するかをテストしたいと思います：<3000、3000-6000、6000-8000、8000-10000、>10000。答えは3000-6000と6000-8000でなければなりません。

プログラミング言語でこれを行うための優れた効率的な数学的方法は何ですか？

4

5 に答える 5

21

疑似コードの推測：

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest)
{
  Set<Range> results;
  foreach (rangeToTest in setofRangesToTest)
  do
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range
    results.add(rangeToTest);
  done
  return results;
}
于 2008-10-22T08:37:21.523 に答える
6

Range クラスを作成し、メソッド boolean intersects(Range) を与えます。それからあなたはすることができます

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) }

または、わかりやすくするためにJava 8スタイルの関数型プログラミングを使用する場合:

rangeset.stream().filter(range::intersects).collect(Collectors.toSet())

交差点自体は次のようなものです

this.start <= other.end && this.end >= other.start
于 2008-10-22T08:42:05.693 に答える
3

これは範囲に大きく依存します。範囲は大きくても小さくてもよく、クラスター化されていてもされていなくてもかまいません。クラスター化された範囲が大きい場合（「2で除算できるすべての正の32ビット整数」と考えてください）、Range（lower、upper）を使用した単純なアプローチは成功しません。

私は次のように言うことができると思います：範囲が少ない場合（ここではクラスタリングかどうかは関係ありません）、ビットベクトルを検討してください。サイズによっては、すべての要素の反復に時間がかかる場合がありますが、これらの小さな生き物は、和集合、交差、およびメンバーシップのテストに関して非常に高速です。さらに、要素ごとに1ビットを使用するだけなので、大きな範囲をスローしない限り、かなり小さいです。

範囲が少なく、大きい場合は、他の人が説明しているクラス範囲で十分です。このクラスには、lowerとupperの属性があり、intersection（a、b）は基本的にb.upper<a.lowerまたはa.upper>b.lowerです。和集合と交差は、単一の範囲では一定の時間で実装でき、複雑な範囲では、サブ範囲の数に応じて時間が長くなります（したがって、小さな範囲が多すぎないようにする必要があります）

数字を入れることができる巨大なスペースがあり、範囲が厄介な形で分散している場合は、二分決定図（BDD）を確認する必要があります。これらの気の利いた図には、入力の各ビットにTrueとFalseの2つのターミナルノードと決定ノードがあります。決定ノードには、それが調べるビットと、それに続く2つのグラフノードがあります。1つは「ビットが1」用で、もう1つは「ビットがゼロ」用です。これらの条件が与えられると、小さなスペースで広い範囲をエンコードできます。任意に大きい数のすべての正の整数は、グラフの3つのノードにエンコードできます。基本的に、最下位ビットの単一の決定ノードは、1でFalseになり、0でTrueになります。

IntersectionとUnionは非常に洗練された再帰アルゴリズムです。たとえば、交差点は基本的に各BDDで2つの対応するノードを取り、結果がポップアップしてチェックするまで1エッジをトラバースします。結果の1つがFalse-Terminalの場合、1を作成します。 -結果BDDのFalse-terminalに分岐します。両方がTrue-Terminalの場合、結果のBDDにTrue-terminalへの1ブランチを作成します。それが別のものである場合は、この何かに1つのブランチを作成します-それ以外の場合は、結果のBDDになります。その後、いくつかの最小化が開始され（ノードの0分岐と1分岐が同じ次のBDD /ターミナルに移動する場合は、それを削除して、着信遷移をターゲットにプルします）、あなたは金色になります。それ以上に、条件を最適化するために値の予測を強化するために、BDDに整数のセットを追加するシミュレーションに取り組みました。

これらの考慮事項は、操作が数値範囲のビット数、つまりlog_2（MAX_NUMBER）によって制限されることを意味します。考えてみれば、64ビット整数の任意のセットをほぼ一定の時間で交差させることができます。

詳細については、たとえばウィキペディア や参照されている論文を参照してください。

さらに、誤検知が許容可能であり、存在チェックのみが必要な場合は、ブルームフィルターを確認できます。ブルームフィルターは、表現されたセットに要素が含まれているかどうかを確認するために、ハッシュのベクトルを使用します。交差と和集合は一定時間です。ここでの主な問題は、ブルームフィルターをいっぱいにしすぎると、偽陽性率が高くなることです。繰り返しになりますが、たとえばウィキペディアの情報です。

ハッチ、セット表現は楽しいフィールドです。:)

于 2008-10-22T09:49:53.730 に答える
1

Pythonで

class nrange(object):
    def __init__(self, lower = None, upper = None):
        self.lower = lower
        self.upper = upper
    def intersection(self, aRange):
        if self.upper < aRange.lower or aRange.upper < self.lower:
            return None
        else:
            return nrange(max(self.lower,aRange.lower), \
                          min(self.upper,aRange.upper))
于 2008-10-22T09:55:27.823 に答える