Daten schnell durchsuchen

LL0rd · Beiträge: 19

Hallo,

ich muss in C# eine Datenmenge verwalten. Ein Datensatz besteht aus zwei Integer Zahlen. Die Datenmenge besteht aus ca. 10 Mio Datensätzen. Es gibt nur drei Operationen, die mit der Datenmenge rechnen sollen.

1) Man gibt die Zahl 1 und die Zahl 2 ein und bekommt als Ergebnis zurück, ob es ein solches Zahlenpaar gibt
2) Man gibt die Zahl 1 ein und bekommt z.B. ein Array oder eine Liste mit allen vorhandenen Kombinationen
3) Man gibt die Zahl 2 ein und bekommt z.B. ein Array oder eine Liste mit allen vorhandenen Kombinationen

Also Quasi eine ganz typische Datenbank Funktionen. Aber wie lassen sie sich am besten / performantesten in C# umsetzen?

Xong · Beiträge: 113 WIN 2000 Borland Developer Studio 2006

Dazu brauchst du nur am Anfang beim Einsortieren (also einmalig) viel Aufwand!
Du speicherst eine Struktur mit drei Listen: Eine mit den Datensätzen mit den Zahlen 1, eine mit den Datensätzen mit den Zahlen 2 und eine, die die Datensätze mit den Zahlen 1 und 2 beinhaltet.

LL0rd hat folgendes geschrieben:

1) Man gibt die Zahl 1 und die Zahl 2 ein und bekommt als Ergebnis zurück, ob es ein solches Zahlenpaar gibt

Ist die dritte Liste leer, gibt die Funktion false zurück, ansonsten true. Aufwand: 1.

LL0rd hat folgendes geschrieben:

2) Man gibt die Zahl 1 ein und bekommt z.B. ein Array oder eine Liste mit allen vorhandenen Kombinationen

Liste 1 wird zurückgegeben. Aufwand: 0.

LL0rd hat folgendes geschrieben:

3) Man gibt die Zahl 2 ein und bekommt z.B. ein Array oder eine Liste mit allen vorhandenen Kombinationen

Liste 2 wird zurückgegeben. Aufwand: 0.

Entweder es ist wirklich so einfach, oder du hast wichtige Informationen verschwiegen. =)

LL0rd · Beiträge: 19

Hi,

ich verstehe schon, dass ich die Daten irgendwie indizieren muss, aber ich verstehe leider nicht so ganz, wie du es geschrieben hast... Oder wir sind uns noch nicht so ganz über die Aufgabe in klaren. Also ich habe z.B. folgende Datenmenge:

Zahl 1; Zahl 2
1;5
1;6
1;7
2;7
3;7

1) Ich such nach der Zahl 1 = "1", bekomme als Ergebnis {5,6,7} zurück
2) Ich such nach der Zahl 2 = "7", bekomme als Ergebnis {1,2,3} zurück
3) Ich such nach der Zahl 1 = "1" UND Zahl 2 = "6", zu den Werten ist ein Eintrag vorhanden, also bekomme ich true zurück.

Das ist in etwa das, was ich wollte.

Gausi · Verfasst: Mo 18.02.08 12:20

Ich würde mir zwei Kopien der Listen anlegen. Die erste Kopie sortierst du nach Zahl1, die zweite nach Zahl2. Je nach Anfrage (Typ 1 oder 2) suchst du dann in der ersten oder zweiten Liste mit Binärsuche einen Treffer für die eingegebene Zahl und gibts dann alle Zahlen aus, in dem du von dem Treffer, den die Binärsuche ergeben hat, linear noch oben und unten die Liste durchläufst, bis du eine andere Zahl 1 (bzw. Zahl 2) findest.

Für Anfrage vom Typ 3 kannst du die erste Liste bei Beginn nach Zahl 1 UND Zahl 2 sortieren, und dann eine entsprechend anders aussehende Binärsuche starten.

Aufwand einmalig fürs sortieren mit Quicksort: 2*n*log(n). Aufand fürs Suchen: log(n) + Anzahl Treffer.

_________________
We are, we were and will not be.

Xong · Beiträge: 113 WIN 2000 Borland Developer Studio 2006

Für mich war Zahl 1 die Zahl mit dem Wert 1.

Da bin ich ja voll vorbeigerauscht!

LL0rd · Beiträge: 19

Hallo,

sorry, aber irgendwie habe ich heute eine ganz lange Leitung bei dem Thema. (Ein Grund könnte die Uhrzeit des ersten Postings verraten.) Ich verstehe leider nicht, wie ihr die Liste sortieren wollt. Ich glaube, am einfachsten lässt es sich hier mit etwas Code beschreiben:

markieren

C#-Quelltext

1:
2:
3:
4:

            List<int> testListe = new List<int>();
            testListe.Add(2);
            testListe.Add(1);
            testListe.Sort();

Doch was habe ich denn nun davon? Ich habe nun eine Liste mit Zahlen, die aber keinerlei Zuordnung haben. Was ich mir vorstellen könnte, wäre so etwas in der Art wie:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:

            List<List<int>> testList2 = new List<List<int>>();
            List<int> tmpList = new List<int>();
            tmpList.Add(5);
            tmpList.Add(6);
            tmpList.Add(7);
            testList2.Add(tmpList);

Um mal auf mein Beispiel zu kömmen, hätte ich jetzt z.B.:

1;5
1;6
1;7

Unter der Listenposition 1 zusammengefasst. Aber irgendwie glaube ich nicht, dass es das ist, was Gausi gemeint hat. Und aus irgendeinem Grund glaube ich nicht wirklich daran, dass eine Liste bei millionen von Positionen so schnell angesprochen werden kann, oder?

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme