Ich habe Datumsbereichsdaten in der SQL DB-Tabelle, die diese drei (nur relevanten) Spalten enthält:
ID (int Identität) RangeFrom (nur Datum) RangeTo (nur Datum) Für jeden beliebigen Datumsbereich kann eine beliebige Anzahl von Datensätzen vorhanden sein, die sich (vollständig oder teilweise) überlappen können.
ID (neuerer Datensatz) hat Vorrang vor älteren Datensätzen, die sich (vollständig oder teilweise) überlappen können RangeFrom und RangeTo unterscheiden sich um einen Tag) Da es sehr viele komplexe Daten im Zusammenhang mit diesen Bereichen gibt (viele Joins usw.) und da Prozessor + Speicherleistung viel effizienter ist als SQL-DB-Engine, habe ich mich entschieden, überlappende Daten aus der Datenbank in meine Datenschicht zu laden der Bereich Chopping / Splitting im Speicher. Das gibt mir viel mehr Flexibilität und Geschwindigkeit bei Entwicklung und Ausführung.
Wenn Sie denken, dass dies in DB besser gehandhabt werden sollte, lassen Sie es mich wissen.
Ich möchte den schnellsten und möglichst auch ressourcenfressenden Konvertierungsalgorithmus schreiben. Da ich viele dieser Datensätze erhalte und sie mit verschiedenen Benutzern verbunden sind, muss ich diesen Algorithmus für jeden Benutzer und seine Menge von überlappenden Bereichsdaten ausführen.
Was wäre der effizienteste (schnelle und nicht ressourcenhungrige) Weg, diese überlappenden Bereiche aufzuteilen?
Ich habe Datensätze ID=1 bis ID=5 , die sich auf diese Weise visuell überschneiden (Daten sind eigentlich irrelevant, ich kann diese Überlappungen besser so darstellen):
Ergebnis sollte wie folgt aussehen:
%Vor%Das Ergebnis sieht tatsächlich so aus, als würden wir diese Überlappungen von oben betrachten und dann IDs erhalten, die wir von dieser Top-Down-Ansicht aus sehen.
Das Ergebnis wird tatsächlich in neue Bereichsdatensätze umgewandelt, so dass alte IDs irrelevant werden. Aber ihre RangeFrom und RangeTo Werte (zusammen mit allen zugehörigen Daten) werden verwendet:
Dies ist natürlich nur ein Beispiel für überlappende Bereiche. Es kann alles von 0 bis X für einen bestimmten Zeitraum reichen. Und wie wir sehen können, wurde die Bereichs-ID = 2 vollständig von 4 und 6 überschrieben, so dass sie vollkommen obsolet wurde.
Ich habe eine eigene Idee:
Für den angegebenen Datumsbereich würde ich ein In-Memory-Array mit Ganzzahlen mit so vielen Elementen erstellen, wie es Tage im Bereich gibt.
Füllen Sie das Array mit null -Werten. Alle von ihnen.
Datensätze nach ID in umgekehrter Reihenfolge bestellen
Reduzieren Sie überlappende Bereiche, indem Sie über geordnete Datensätze iterieren, und gehen Sie für jedes Element folgendermaßen vor:
null ist
Sie erhalten ein Array von abgeflachten Bereichen und füllen mit Datensatz-IDs
erstellt einen neuen Datensatzsatz und erstellt jeden neuen Datensatz, wenn sich die ID im Array ändert. Jeder Datensatz sollte Daten verwenden, die mit der im Array
Wiederholen Sie das Ganze für die nächste Person und ihre Menge überlappender Bereiche (vergessen Sie nicht, dasselbe Array wiederzuverwenden). = gehe zurück zu Schritt 2.
Und das ist es im Grunde.
Ein 10 Jahre gegebener Datumsbereich erfordert ein Array von ca. 3650 nullable Integer, die ich denke, ist ziemlich klein Speicherbedarf (jede ganze Zahl 4 Byte, aber ich weiß nicht, wie viel Platz belegt eine nullbare Ganzzahl, die eine int und bool hat aber wir nehmen an, dass 8 Bytes insgesamt um 3650 * 8 = 28.52k) und kann leicht und ziemlich schnell im Speicher manipuliert werden. Da ich keine Datumsbereiche, Splits oder Ähnliches speichere, handelt es sich kaum um Zuweisungsoperationen mit einem if, das prüft, ob der Wert bereits gesetzt ist.
Ein 10-Jahres-Datumsbereich ist ein selten übertriebenes Extrem. 75% der Datumsbereiche liegen innerhalb von 3 Monaten oder einem Vierteljahr (90 Tage * 8 Bytes = 720 Bytes) und 99% fallen in den Bereich eines ganzen Jahres (365 * 8 = 2920 Bytes = 2,85k)
Ich finde diesen Algorithmus mehr als geeignet zum Überlappen überlappter Datumsbereiche.
Um den Speicherbedarf zu halbieren, könnte ich int anstelle von int? verwenden und auf -1 anstelle von null setzen.
Ich könnte auch eine Anzahl von Tagen behalten, die nicht gesetzt sind, und wenn sie 0 erreicht, kann ich die Schleife leicht unterbrechen, weil alle verbleibenden Bereiche vollständig überlappt sind, daher würden sie keine weiteren Werte im Array setzen. Das würde die Dinge sogar ein bisschen beschleunigen, wenn ich viele Streckenaufzeichnungen hätte (was eher selten sein wird).
Die kostenlose Zeitraumbibliothek für .NET enthält das Tool TimePeriodIntersector , die verschiedene überlappende Zeitbereiche schneidet.
Der Algorithmus verwendet eine Zeitleiste und zählt alle Momente innerhalb eines Zeitbereichs auf (Start- / Endpunkte pro Moment zählen):
%Vor%Das ID-Mapping sollte eine einfache Aufgabe sein.
Ich bin mir nicht ganz sicher, wie nützlich das wäre, aber so wie ich das angehen würde ... (zuerst nicht optimiert für das einfache Verständnis ...)
(nach Datum sortieren, jedes Datum - egal, Start oder Ende, ist ein Beginn eines Zeitbereichs, der bis zum nächsten Datum reicht.) Damit Ihr Tisch wie folgt aussehen würde:
%Vor%Da Sie doppelte IDs in Ihrer endgültigen Datenbank haben ("1" wird in Ihrem Beispiel auf zwei Segmente aufgeteilt), scheint am Ende die Datenbank im Datum- & gt; ID-Format im Gegensatz zum ID- & gt; -Bereich zu behalten .
Jetzt für offensichtliche Optimierungen - natürlich nicht die Liste der IDs mit jedem Datensatz halten. Füllen Sie einfach eine Datums- & gt; ID-Tabelle mit Null-IDs aus, und während Sie sie mit den endgültigen Datensätzen füllen, ersetzen Sie den bisher größten gefundenen Datensatz:
Das Hinzufügen eines neuen Datensatzes ist genau wie eine Iteration des Erstellungsvorgangs. Das Entfernen eines Datensatzes ist jedoch ziemlich schwierig.
Sie möchten effektiv die Daten stapeln und das Maximum aus dem Stapel auswählen. Ich musste etwas Ähnliches implementieren und der Ansatz, den wir verwendet haben, der uns ein bisschen mehr Flexibilität gab, als Sie benötigen, war vielleicht nicht passend, dies zu tun:
Verfügen Sie über ein Objekt zum Verwalten der Datensätze und fügen Sie jedem Datensatz dieses Objekt hinzu. Wenn ein Datensatz hinzugefügt wird, erstellen Sie einen neuen Datumsbereich und verknüpfen Sie den Wert des Datensatzes mit dem Bereich. Überprüfen Sie dann, ob sich der Bereich mit einem anderen vorhandenen Bereich überlappt. Wenn es sich überschneidet, erstellen Sie einen neuen Bereich für jede Überlappung und verknüpfen Sie alle Werte für beide / alle (abhängig davon, ob Sie beim Hinzufügen der einzelnen Bereiche oder in einem einzelnen Durchgang die überlappten Bereiche mit dem neuen Bereich verwenden) . Dies kann entweder erfolgen, indem Sie die Daten hinzufügen, oder in einem einzigen Durchgang, sobald alle Daten hinzugefügt wurden.
Am Ende haben Sie ein Objekt, das eindeutige Bereiche enthält, denen jeweils eine Sammlung von Werten zugeordnet ist, ein bisschen wie Ihr Bild oben.
%Vor%Sie können dann eine Klasse mit einer Glättungsfunktion (wahrscheinlich unter Verwendung des Strategie-Musters) versehen, die die eindeutigen Bereiche mit Sammlungen von Werten in eindeutige Bereiche mit einem einzigen Wert umwandelt, wodurch offensichtlich Bereiche verkettet werden, die mit demselben Wert enden .
Sie möchten eine Klasse, die den Maximalwert aus jedem eindeutigen Bereich auswählt, aber auch den Mindestwert auswählen, die Werte summieren, sie mitteln, zählen usw. usw. Jede dieser Optionen kann durch Übergeben ausgeführt werden eine andere Umsetzung der Strategie.
Wie gesagt, dieser Ansatz ist vielleicht weniger effizient als ein Ansatz, der nur den Maximalwert auswählt, da Sie in diesem Fall nicht alle Werte im Stack behalten müssten, aber die Implementierung war ziemlich geradlinig, wie ich mich erinnere .
Tags und Links c# split overlap date-range