数直線の C# 実装
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
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 または
範囲を確認するときは、単にエンドポイント値を検索します。それには O（log n）が必要です。これはO（n）よりもかなり高速です。
注：すべての挿入と削除は O（log n）を使用します。
他のヒント
HashSet <！> lt; T <！> gt;を使用：
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
ただし、正しい軌道に乗れるはずです。
OK、これでどこへ行くのかわかりました。
ルシーン これは非常に大きなビットフィールドで行われます。
可能な数値の範囲が 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 ビット整数が必要です。
次に、いくつかの使用例を見てみましょう
70～80の範囲を確認したい。これを行うには、チェックにさらに 1000 個の int は必要ありません。1 つの int だけで済みます。配列の 2 番目の要素に対してそれをチェックしていることがわかります。
2000〜10,000の範囲をもう一度確認したいのですが、1つのINTのみが必要であり、アレイ31の位置を計算して（私は思う）、それに応じてビットを設定して比較します。次に、10,000 (位置 156?) に達するまでリストを繰り返し、途中で比較し、返す整数のリストを作成します。
アップデート 2:それは O(1) ではありません
チェックする範囲のサイズに応じて、これを O(1) として実装できます。
ただし、このアルゴリズムを使用しても、一般的なケースは依然として O(n) です。
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;
}
}
}
O（n）は、要素の数によって変化することを意味します O（1）は一定の時間を意味します
これを実装するO（1）の方法も考えられません。
アプリの詳細についてはわかりませんが、私の直感では、これはセットベースの操作であるため、データベースで処理する方がはるかに優れているとわかります。
I.E。
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
この問題に繰り返し対処しようとした場合に役立つ場合があります。たとえば、LineNumberクラスにRangesのリストをロードします。これらの範囲にはstartおよびend intが含まれています。次に、「checkrange（a、b）」メソッドの代わりに、「hasNumber（a）」メソッドを実装します。範囲のリストをループするだけでこれを行い、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の実装は後で使用します。 ：）
これは完全なソリューションではありませんが、おそらく別のアプローチでより良い結果が得られる可能性があります。
