|
| |
VB.NET - Fortgeschrittene| große Zahlenreihen + Mustersuche | |  | | Autor: Jaeger | | Datum: 21.01.11 11:55 |
| Hallo,
ich habe z. Z. ein kniffliges Problem, schon fast ein Rätsel ^^. Zwar habe ich dafür schon eine funktionierende Lösung, allerdings ist diese noch nicht optimal. Daher würde mich interessieren, ob hier jemandem noch was Besseres einfällt. Ich knobel schon einige Zeit daran rum, leider ohne ein besseres System als mein jetziges zu finden 
Das Grundproblem ist eigentlich recht einfach erklärt.
Gegeben sind fünf SQL.Tabellen mit je einem Hauptwert (4 Byte Integer) mit theoretisch max. 16,7 Millionen Einträgen (beginnent mit 1 fortlaufend bis Maximalwert), von denen die Tabellen bis auf eine i. d. R. recht klein ausfallen.
Diese Werte haben je zwei weitere "ID" Spalten (ab jetzt mit ID1 und ID2 bezeichnet) mit einem 4 Byte Integer von denen es zwischen 1-1000 Rows pro Wert gibt.
Diese zwei IDs Columns sollen möglichst platzsparend in einer Binärdatei untergebracht werden, die Bedinungen ist, dass die Werte zusammenhängen (jede Column sperat)- die Reihenfolge muss auch bestehen bleiben, d. h. die Ketten dürfen NICHT anders sortiert werden, auch dürfen redundande IDs nicht entfernt werden. Rückgabewert ist immer der Startoffset, da das System die Länge der ID-Kette kennt, brauch man keinen Endpunkt speichern.
Beispiel:
der erste Wert hat ID1: 1,8,15,20 - ID2: 100,234,235,1000
Dann würde in die Datei geschrieben: 1,8,15,20,333,234,235,1000
Die zurückgegebenen Offsets wären: ID1: 0 ID2: 16 (jeweils vier Byte in der Datei pro Wert, beginnend bei "0")
der zweite Wert hat: ID1: 234 - ID2: 540
Dann müsste die ID1 logischerweise auf Offset 20 stehen und die ID2 auf Offset 32 eingefügt werden.
Die momentare Datei würde also so aussehen:
1,8,15,20,333,234,235,1000,540
Wenn jetzt eine ID-Kette mit den IDs "20,234,235" käme, dann könnte diese an Offset 12 eingetragen werden, ohne zusätzliche Elemente anzulegen.
Der Knackpunkt an der Sache ist natürlich, dass Speicher (RAM) und Zeit kritische Faktoren sind.
Im Moment verwende ich folgendes System:
1. Wird der maximale "Wert" in den Tabellen ermittelt. Dieser ist auch gleichzeitig die höchste ID, die in den ID-Spalten vorkommen kann
2. es wird ein Block mit den IDs von 1-Maximalwert in die Binärdatei geschrieben
3. Sämtliche Werte mit nur einer ID bekommen den Offset (ID-1)*4, da die Position in der Datei ja bekannt ist
4. anschliessend wird eine Schleife durchlaufen, die die immer ein Block mit einer bestimmten ID-Länge selektiert (z. B. alle Werte, die zwischen 20 und 40 ID Rows haben)
5. wird die Kette durchlaufen und überprüft, ob der Abstand zwischen einer ID und ihrem Nachfolger nur +1 beträgt. Ist das der Fall (z. B. 12344,12345,12346), dann wird diese Kette auch in dem Anfangsblock mit den fortlaufenden Werten untergebracht
6. ist das nicht der Fall, dann wird die Kette in einem Dictionary Object gesucht(Key = Wert, Value = Offset). Wenn also eine ID-Kette schonmal geschrieben wurde, wird nur der Offset zurückgeben, ansonsten die jeweilige Kette gespeichert und im Dictionary abgelegt.
Dieses System funktioniert wunderbar, aber natürlich lassen sich viele Redundanzen in der Datei nicht vermeiden was dazu führt, dass diese größer wird als nötig.
Da in meinem System nur identische ID-Ketten abgefagen werden, werden solche wie z. B. 1,5,8 und 1,5,8,9 komplett abgelegt.
Und jetzt die Preisfrage: wie würdet ihr dieses Problem lösen. Limitierung ist, dass es ein 32Bit System ist, d. h. mehr als ~1,2GB Speicher mit VB.NET könnte zu OOMs führen. In meinem Worst Case beträgt die Menge der IDs 170.000.000 * 2, also an die 340.000.000 IDs, aufgeteilt auf bis zu 18 Milliionen Werte. Selbst wenn ich es auf einem 64Bit System laufen lassen würde, wäre ich immernoch skeptisch, das in einer vernünftigen Zeitspanne abzuarbeiten.
Beitrag wurde zuletzt am 21.01.11 um 12:18:30 editiert. | |
 | Sie sind nicht angemeldet!
Um auf diesen Beitrag zu antworten oder neue Beiträge schreiben zu können, müssen Sie sich zunächst anmelden.
 Einloggen | Neu registrieren |
 |
|
vb@rchiv CD Vol.6 vb@rchiv  Vol.6
Geballtes Wissen aus mehr als 8 Jahren vb@rchiv!
Online-Update-Funktion
Entwickler-Vollversionen
u.v.m.Jetzt zugreifen Tipp des Monats sevGraph (VB/VBA) 
Grafische Auswertungen
Präsentieren Sie Ihre Daten mit wenig Aufwand in grafischer Form. sevGraph unterstützt hierbei Balken-, Linien- und Stapel-Diagramme (Stacked Bars), sowie 2D- und 3D-Tortendiagramme und arbeitet vollständig datenbankunabhängig! Weitere Infos
|
November 2025
Sie sind aktuell nicht angemeldet.
