NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine数直線を表すクラスです。さまざまな範囲の数値をマークしたいと思います。このCheckRangeメソッドは、マークした部分10-25とマークしなかった部分を返す必要があります。この場合、10-20マークされていないものとマークされているものを返す必要20-25があります。
o(n)を実行しない、これを効果的に実装するにはどうすればよいですか?
ありがとうございました。
注:これは宿題ではありません。これは、カスタム データベースの実装トランザクションに必要です。プログラミングを独学で学んでいます。
解決策は簡単です。強調表示されたすべての値をAVLまたは赤黒ツリーに追加します。つまり、AddRange(1,3) を実行すると、整数値 1,2 および 3 がツリーに挿入されます。
範囲を確認するときは、エンドポイントの値を検索するだけです。O(n) よりもかなり高速なO(log n)が必要です。
注: 挿入と削除はすべてO(log n)を取ります。
OK、これでどこに行くのかわかります。
Luceneは、非常に大きなビットフィールドでこれを行います。
可能な数値の範囲が1から64であるとすると、これらの数値のそれぞれは、64ビット整数のその位置にあるビットに対応します。（No 1はビット0、No 2はビット1）。
範囲に数値を追加する場合は、そのビットをオンにします（この例では、ビット0から4および19から29をオンにします）。
ここで、数値の範囲を確認するために、そのビット範囲がオンになっている別の64ビットintを作成し、2つのビットフィールドでビット単位のAnd（＆）を実行します。結果の1ビットはオーバーラップ範囲です。
64を超える数の場合は、ビット数をスケールアップするだけです（配列または整数のリストを操作することによって）
お役に立てれば ：）
更新：スケーラビリティ
64ビットアーキテクチャに取り組んでいて、1回の操作で64ビット整数をANDできるとしましょう。理想的には、64ビットintを使用します。
ここで、可能な数値の範囲が1〜64,000であるとしましょう。これには、1000個の64ビットintが必要です。
次に、いくつかのユースケースを見てみましょう
70〜80の範囲をチェックしたいと思います。これを行うには、チェックにさらに1000 intは必要なく、1 intだけで、配列の2番目の要素に対してチェックしていることがわかります。
2000〜10,000の範囲を確認したいのですが、必要なintは1つだけで、配列31番目（私は思う）での位置を計算し、それに応じてビットを設定して比較します。次に、10,000（156位？）に達するまでリストを繰り返し処理し、途中で比較して、返す整数のリストを作成します。
アップデート2：それはO（1）ではありません
チェックする範囲のサイズに応じて、これをO（1）として実装できます。
ただし、このアルゴリズムを使用すると、一般的なケースは依然としてO（n）です。
HashSet<T> を使用します。
public class NumberLine : HashSet<int>
{
public void AddRange(int start, int end)
{
int count = (end-start)+1;
UnionWith(Enumerable.Range(start, count));
}
public IEnumerable<int> CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
other.IntersectWith(this); // marked
// other.ExceptWith(this); // not marked
return other;
}
}
CheckRange から何を返したいのか、または文字列を出力したいだけなのかわからない。指定した範囲のような単純なものの場合、次を使用できます。
public string CheckRange(int start, int end)
{
NumberLine other = new NumberLine();
other.AddRange(start, end);
IEnumerable<int> marked = other.Intersect(this);
IEnumerable<int> notMarked = other.Except(this);
int markedMin = marked.Min();
int markedMax = marked.Max();
int notMarkedMin = notMarked.Min();
int notMarkedMax = notMarked.Max();
string markedString = (markedMin == markedMax)
? markedMin.ToString()
: string.Format("{0} - {1}", markedMin, markedMax);
string notMarkedString = (notMarkedMin == notMarkedMax)
? notMarkedMin.ToString()
: string.Format("{0} - {1}", notMarkedMin, notMarkedMax);
return string.Format("Marked: {0}\r\nNot Marked: {1}", markedString, notMarkedString);
}
次のような分割範囲は処理されません。
Marked: 10-15, 20-25
Not Marked: 16-19
しかし、それはあなたを正しい軌道に乗せるはずです。
範囲自体を NumberLine 内に格納するとどうなりますか。重複する範囲が追加された場合、マージを行うことができます。CheckRange は、個々の要素ではなく、NumberLine 内に格納されている範囲を照会できます。これは、要素の数の O(N) ではなく、範囲の数の O(N) になります。可能であれば範囲をマージすると、範囲の数は AddRange の呼び出し数よりも少なくなります。
以下のコードサンプルを参照してください。私は .Net コレクションの専門家ではないため、より適切なコレクション タイプを選択することで、より効率的な実装が可能になる可能性があります。_NTは、値をツリー構造に格納することを提案しました。これを範囲にも適用して、開始番号で保存できます。これにより、追加時とチェック時の両方で、範囲の検索が高速になります。私の現在の実装では、最後に範囲を追加すると、最初に範囲を追加するよりも遅くなります。これを効率的なツリーに格納すると、複雑さは範囲の数で O(log N) になります。
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
namespace NumberLine
{
class Program
{
static void Main(string[] args)
{
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(10, 12);
line.AddRange(20, 30);
List<Range> ranges = line.CheckRange(10, 25);
foreach (Range r in ranges)
{
for (int i = r.Start; i <= r.End; i++)
{
Console.WriteLine(i);
}
}
}
}
class Range
{
public int Start;
public int End;
}
class NumberLine
{
private SortedList<int, Range> Ranges = new SortedList<int, Range>();
public void AddRange(int start, int end)
{
if (Ranges.Count == 0)
{
Ranges.Add(start, new Range() { Start = start, End = end });
}
else
{
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.Start)
{
if (end >= currentRange.End)
{
currentRange.Start = start;
currentRange.End = end;
}
else
{
currentRange.Start = start;
}
Ranges.RemoveAt(start);
Ranges.Add(start, currentRange);
break;
}
else
{
if (start <= currentRange.End)
{
currentRange.End = end;
break;
}
else
{
Ranges.Add(start, new Range(){ Start = start, End = end });
break;
}
}
}
}
}
public List<Range> CheckRange(int start, int end)
{
List<Range> result = new List<Range>();
foreach (Range currentRange in Ranges.Values)
{
if (start <= currentRange.End)
{
if (end <= currentRange.End)
{
result.Add(new Range() { Start = currentRange.Start, End = end });
break;
}
else
{
if (start <= currentRange.Start)
{
result.Add(new Range() { Start = currentRange.Start, End = currentRange.End });
}
else
{
result.Add(new Range() { Start = start, End = currentRange.End });
}
}
}
}
return result;
}
}
}
この問題に繰り返し取り組んでいれば、それが役立つかもしれません。たとえば、LineNumber クラスに範囲のリストをロードします。これらの範囲には、開始と終了の int があります。次に、'checkrange(a,b)' メソッドの代わりに、'hasNumber(a)' メソッドを実装します。Ranges のリストをループして、Range クラスのメソッド 'isInRange(a) を呼び出すだけで、これを行うことができます。したがって、データ モデルは次のようになります。
LineNumber {
List<Range> ranges;
aadRange(a,b);
// Loops through all ranges and calls isInRange on each method
isInRange(a);
//just iterates over isInRange from a to b
checkRange(a,b)
}
Range {
Range(a,b)
isInRange(a);
}
これにより、いくつかの実用的なコードとインターフェイスが得られます。十分な速さではないかもしれませんが、まだわかりません。lucene の実装は後回しにします。:)
これは完全な解決策ではありませんが、おそらく別のアプローチでより良い結果が得られる可能性があります。
O(n) は要素の数に応じて変化することを意味します O(1) は一定の時間を意味します
これを実装するO（1）の方法も考えられません。
アプリの詳細についてはよくわかりませんが、設定ベースの操作であるため、直感的にはデータベースで処理する方がはるかに適切であることがわかります。
IE
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range