Eine C # Umsetzung der Nummern Linie
https://stackoverflow.com/questions/1614137
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);
line.CheckRange(10, 25);
NumberLine ist eine Klasse, die eine Anzahl Linie darstellt. Ich möchte auf sie verschiedene Bereiche von Zahlen markieren. Die CheckRange Methode sollte zurückkehren, welche Teile von 10-25 I markiert und die ich nicht. In diesem Fall sollte es zurückgeben, dass 10-20 nicht markiert ist, und dass 20-25 gekennzeichnet ist.
Wie kann ich eine wirksame Umsetzung dieser Umsetzung, die o nicht tun würde (n)?
Danke.
Hinweis: Dies ist nicht Hausaufgaben. Ich brauche das für meine benutzerdefinierte Datenbankimplementierung Transaktionen. Ich lerne Programmierung allein .
Lösung
Die Lösung ist einfach: Fügen Sie alle markierten Werte zu einem AVL oder Red-black Baum. Ich meine, wenn Sie tun AddRange (1,3), legen Sie die ganzzahligen Werte 1,2 und 3 im Baum.
Wenn Bereiche überprüft, Nachschlag einfach die Endpunktwerte. Das nimmt O (log n) , das ist deutlich schneller als O (n).
. Hinweis: Einfügen und löschen Sie alle nehmen O (log n)
Andere Tipps
Verwenden Sie ein HashSet
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;
}
}
Nicht sicher, was Sie von Checkrange zurückkehren wollte, oder wenn Sie nur eine Zeichenfolge drucken wollte. Für einfache etwas wie die Bereiche von Ihnen angegebenen, könnten Sie verwenden:
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);
}
Es wird nicht gespalten Griff reicht wie:
Marked: 10-15, 20-25
Not Marked: 16-19
Aber es soll man auf dem richtigen Weg bekommen.
OK, ich sehe, wo Sie mit dieser gehen.
Lucene tut dies mit sehr großen Bit-Felder.
Sagen Sie Ihr möglicher Zahlenbereich von 1 bis 64 geht, jede dieser Zahlen mit dem Bit entspricht in dieser Position auf einem 64-Bit-int. (No 1 Bit 0, No 2 Bit 1).
Wenn Sie eine Zahl in einen Bereich hinzuzufügen, schalten Sie auf diesem Bit (in Ihrem Beispiel Sie auf die Bits 0 bis 4 wechseln würde und 19 bis 29).
Jetzt eine Reihe von Zahlen zu überprüfen, können Sie mit diesem Bereich von Bits einen anderen 64-Bit-int erstellen schaltet, und führen Sie eine bitweise Und (&) auf die beiden Bit-Felder. Die 1-Bits im Ergebnis ist der Überlappungsbereich.
Für mehr Zahlen als 64, nur die Anzahl der Bits vergrößern (möglicherweise durch mit Arrays oder Listen von ganzen Zahlen arbeiten)
Hope, das hilft:)
Aktualisieren : Skalierbarkeit
Lassen Sie uns sagen Sie auf 64-Bit-Architektur arbeiten und Sie können und 64-Bit-Integer in einem einzigen Vorgang. Im Idealfall würde man 64 Bit ints verwenden.
sie nun an, Ihr möglicher Zahlenbereich von 1 bis 64.000 läuft, dafür benötigt man 1000 64-Bit ints.
sehen wir uns nun auf ein paar Anwendungsfälle
-
Ich möchte den Bereich von 70 - 80. Um dies zu tun wir weitere 1000 ints für die Prüfung nicht brauchen, nur ein int, und wir wissen, dass wir überprüfen es gegen das zweite Element in unserem Angebote.
-
Ich möchte den Bereich von 2000 überprüfen - 10000 Auch hier müssen wir nur ein int, berechnen sie Position im Array 31. ist (glaube ich) und die Bits entsprechend und vergleichen eingestellt. Dann wiederholen Sie durch die Liste, bis Sie treffen 10.000 (Position 156?), Auf dem Weg zu vergleichen und bauen Sie sind Liste von ganzen Zahlen zurückzukehren.
Update 2 : Das ist nicht O (1)
In Abhängigkeit von der Größe des Bereichs zu überprüfen, können Sie dies implementieren als O (1)
Verwendung jedoch diesen Algorithmus der allgemeine Fall ist immer noch O (n)
Was ist, wenn Sie speichern die Bereiche sich innerhalb der Zahlengerade. Sie können eine Zusammenführung tun, wenn überlappende Bereiche hinzugefügt werden. Checkrange dann können die Bereiche abfragen, die innerhalb Zahlengerade gespeichert sind, anstelle der einzelnen Elemente. Dies wird dann zu O (N) in der Anzahl der Bereiche, anstelle von O (N) in der Anzahl der Elemente. Wenn Sie Bereiche Eine Zusammenführung, wenn möglich, dann die Anzahl der Bereiche kleiner als die Anzahl der Anrufe an AddRange wird.
Im folgenden sehen Sie das Codebeispiel. Ich bin kein Experte für .Net Sammlungen so eine effizientere Implementierung möglich sein könnte, durch eine bessere Sammlung Typen auswählen. _NT vorgeschlagenen Werten in einer Baumstruktur zu speichern. Sie können dies auf Bereiche gelten auch und speichert sie durch die Startnummer. Dies macht die Bereiche schnellere Suche, sowohl beim Hinzufügen und überprüfen. In meiner aktuelle Implementierung Bereiche bis zum Ende Zugabe langsamer als Bereich am Anfang hinzugefügt wird. Wenn dies in einer effizienten Baum speichert die Komplexität O (log N) in der Anzahl von Bereichen.
wirdusing 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) bedeutet, variiert wie die Anzahl der Elemente O (1) bedeutet, konstante Zeit
Ich kann nicht denken Sie an eine O (1) Weg, dies umzusetzen, auch nicht.
Ich bin über die Besonderheiten der App nicht sicher, aber meine Intuition sagt mir, das wäre viel besser in der Datenbank behandelt werden, da es eine Reihe basierte Betrieb ist.
d.
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
Wenn Sie versucht, dieses Problem zu lösen in helfen, dass iterativ. Zum Beispiel Ihre Klasse Linenumber mit einer Liste der Bereiche laden, müssen diese Bereiche einen Anfang und Ende int in ihnen. Dann anstelle eines Checkrange (a, b) "Methode, implementieren nur eine 'hasNumber (a)' Methode. Tun Sie dies einfach, indem Sie durch die Liste der Bereiche Looping und rufen eine Methode ‚isInRange (a) auf der Range-Klasse So Ihr Datenmodell könnte sein:
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);
}
Dies wird Ihnen einige Arbeitscode erhalten, und eine Schnittstelle. Es kann nicht schnell genug sein, aber Sie wissen nicht, dass noch. Lassen Sie die Lucene Implementierung für später. :)
Dies ist keine vollständige Lösung, aber vielleicht ein anderer Ansatz könnte dazu beitragen, bessere Ergebnisse zu erzielen.
