maths - Finde den Zahlenbereich-Schnittpunkt



math solver (4)

Wie kann man am besten herausfinden, ob sich zwei Zahlenbereiche schneiden?

Mein Nummernkreis ist 3023-7430 , jetzt möchte ich testen, welche der folgenden Nummernbereiche sich damit schneiden: <3000, 3000-6000, 6000-8000, 8000-10000,> 10000. Die Antwort sollte 3000-6000 und 6000-8000 sein .

Was ist der schöne, effiziente mathematische Weg, dies in irgendeiner Programmiersprache zu tun?

https://ffff65535.com


Dies hängt stark von Ihren Bereichen ab. Ein Bereich kann groß oder klein und gruppiert oder nicht gruppiert sein. Wenn Sie große, gruppierte Bereiche haben (denken Sie an "alle positiven 32-Bit-Ganzzahlen, die durch 2 geteilt werden können), wird der einfache Ansatz mit Range (niedriger, oberer) nicht erfolgreich sein.

Ich denke, ich kann Folgendes sagen: Wenn Sie kleine Bereiche haben (Clustering oder nicht Clustering ist hier nicht wichtig), betrachten Sie Bitvektoren. Diese kleinen Lebewesen sind blitzschnell in Bezug auf Unions-, Kreuzungs- und Mitgliedschaftstests, obwohl die Iteration über alle Elemente je nach Größe eine Weile dauern kann. Da sie für jedes Element nur ein einziges Bit verwenden, sind sie ziemlich klein, es sei denn, Sie werfen riesige Bereiche auf sie.

Wenn Sie weniger, größere Bereiche haben, reicht ein Klassenbereich wie von anderen beschrieben aus. Diese Klasse hat die Attribute Lower und Upper und der Schnittpunkt (a, b) ist grundsätzlich b.upper <a.lower oder a.upper> b.lower. Union und Kreuzung können in konstanter Zeit für einzelne Bereiche und für Composite-Bereiche implementiert werden, die Zeit wächst mit der Anzahl der Teilbereiche (Sie wollen also nicht zu viele kleine Bereiche)

Wenn Sie einen riesigen Platz haben, wo Ihre Zahlen sein können, und die Bereiche in einer unangenehmen Weise verteilt sind, sollten Sie einen Blick auf binäre Entscheidungsdiagramme (BDDs) werfen. Diese raffinierten Diagramme haben zwei Endknoten, True und False, und Entscheidungsknoten für jedes Bit der Eingabe. Ein Entscheidungsknoten hat ein Bit, das er betrachtet, und zwei folgende Graphknoten - einen für "Bit ist Eins" und einen für "Bit ist Null". Unter diesen Bedingungen können Sie große Bereiche auf kleinstem Raum kodieren. Alle positiven ganzen Zahlen für beliebig große Zahlen können in 3 Knoten im Graphen kodiert werden - im Grunde ein einziger Entscheidungsknoten für das niedrigstwertige Bit, der auf 1 auf Falsch und auf 0 auf Wahr geht.

Kreuzung und Vereinigung sind ziemlich elegante rekursive Algorithmen, zum Beispiel nimmt die Kreuzung grundsätzlich zwei entsprechende Knoten in jedem BDD, durchquert die 1-Kante, bis ein Ergebnis erscheint und prüft: Wenn eines der Ergebnisse das Falsche Terminal ist, erstelle eine 1 -branch zum False-Terminal im Ergebnis BDD. Wenn beide das True-Terminal sind, erstellen Sie eine 1-Verzweigung zum True-Terminal im Ergebnis-BDD. Wenn es etwas anderes ist, erstellen Sie eine 1-Verzweigung zu diesem something-else im Ergebnis-BDD. Danach setzt eine Minimierung ein (wenn der 0- und der 1-Zweig eines Knotens zu demselben BDD / Terminal gehen, entfernen Sie ihn und ziehen Sie die eingehenden Übergänge zum Ziel) und Sie sind golden. Wir gingen noch weiter, wir arbeiteten an der Simulation der Addition von Mengen von Ganzzahlen auf BDDs, um die Wertvorhersage zu verbessern, um die Bedingungen zu optimieren.

Diese Überlegungen legen nahe, dass Ihre Operationen durch die Anzahl der Bits in Ihrem Nummernbereich begrenzt sind, dh durch log_2 (MAX_NUMBER). Denken Sie daran, Sie können beliebige Sätze von 64-Bit-Ganzzahlen in nahezu konstanter Zeit schneiden.

Weitere Informationen finden sich beispielsweise in der Wikipedia und den referierten Beiträgen.

Wenn falsch positive Ergebnisse erträglich sind und Sie nur eine Existenzprüfung benötigen, können Sie sich Bloom-Filter ansehen. Bloom-Filter verwenden einen Vektor von Hashes, um zu prüfen, ob ein Element in der dargestellten Menge enthalten ist. Schnittpunkt und Union sind konstante Zeit. Das Hauptproblem hierbei ist, dass Sie eine steigende Falsch-Positiv-Rate erhalten, wenn Sie den Blütenfilter zu sehr auffüllen. Informationen zum Beispiel in der Wikipedia .

Hach, Satzdarstellung ist ein Spaßfeld. :)


Ich würde eine Range-Klasse erstellen und ihr eine Methode boolescher Schnittmengen (Range) geben. Dann können Sie ein tun

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

Die Kreuzung selbst ist so etwas wie

this.start <= other.end && this.end >= other.start

Nur ein Pseudo-Code-Tipp:

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;
}





math