Geschwindikeit beim Vergleichen von zwei Tabellen

Guten Tag,

ich habe zwei Tabellen in denen jeweils eine Spalte als ID hinterlegt ist. Die ID’s sind derzeit in beiden Tabellen unsortiert.

Für den Datenabgleich wird derzeit mittels zweier ineinander geschachtelter For-Next-Schleifen die ID aus beiden Tabellen ausgelesen und miteinander vergliechen.

Derzeit bestehen Probleme mit der Laufzeit - sprich in einer Tabelle sind gut 40.000 Datensätze und in der anderen ca. 2.000 Datensätze enthalten.

Die innere Schleife wird so 2.000 mal 40.000 = 80.000.000 mal durchlaufen, was Zeit „frist“. :wink:

Was gibt es grundsätzlich für Möglichkeiten der Perfomence-Optimierung?

Vorsortierung beider Tabellen wäre vielleicht eine Möglichkeit.

Könnte z. B. das Einlesen der 2.000 Datensätze in ein Array Zeitvorteile beim Vergleichen bringen?

was für Tabellen sind das ?

Oracle?
MSSql?
MySql?
Excel?

Prinzipiell sollte ein vorheriges sortieren schon einen deutlichen Performancegewinn bringen…

Gruß

Es handelt sich um zwei Excel-Tabellenblätter, die in einer Excel-Tabelle untergebracht sind.
Als Programmiersprache nutze ich VBA-Excel und komme damit ganz gut klar.
Sicher, eine richtige Datenbank wäre wahrscheinlich „die“ Alternative, aber mich interessiert es, wie man solch einen Datenvergleich auch mit einem schnellen Algorithmus hingekommen könnte.
Viele Grüße.

Hallo schmidi,

also in VBA gibt es ein funktion find bzw. findnext die einen Range durchsuchen kann. Schau dir diese mal an.

Alternativ würde ich mal sverweis als formel ausprobieren. Mag sein, dass das schneller geht, hängt aber auch davon ab, was du benötigst.

biba

Dirk.Pegasus

Moien

Vorsortierung beider Tabellen wäre vielleicht eine
Möglichkeit.

Ja, hilft. Aber nur wenn man dann auch wirklich eine binäre Suche benutzt/implementiert. Du must nicht unbedingt beide vorsortieren. Die Grössere sortieren sollte schon einen gewaltigen Unterschied machen.

Eine zusätzliche Sortierung der kleinen bringt auch was (man kann die binäre Suche einschränken auf letzte-gefundene-Position bis Ende).

((Und immer die Keys aus der kleineren Tabelle holen und in der grösseren suchen. nicht die kleine sortieren … ))

Könnte z. B. das Einlesen der 2.000 Datensätze in ein Array
Zeitvorteile beim Vergleichen bringen?

Ja, hilft bei Excel auch etwas. Aber im Vergleich zum sturen Durchsuchen ist binäres suchen so abartig schnell, das lohnt sich im Aufwand nicht. Bisher hast du ja 2 000 * 40 000 Operationen. Danach sind es 2 000 * log(40 000) ~= 10 000 Operationen.

cu

Geeignetes Werkzeug muss zum Problem passen

Was gibt es grundsätzlich für Möglichkeiten der
Perfomence-Optimierung?

Grundsätzlich gibt es die Möglichkeiten
* Hardware (Schnellerer Rechner)
* Laufzeitumgebung (Effizientere Entwicklungs- und Laufzeitumgebung)
* Algorithmus

Welchen Weg man geht, hängt maßgeblich davon ab, welche Dimension das Problem hat, wie häufig man die Anwendung braucht und welches die Anforderungen sind. Aber vielleicht geht es auch gar nicht um Wirtschaftlichkeit sondern ums Prinzip oder die Reine Lehre.

Im gewerblichen Umfeld dürfte Hardware der billigste Weg sein, da man sich damit ein vergleichsweise niedriges Risiko einhandelt und wenig Personalaufwand in Entwicklung und Test stecken muss.
Die Performance-Steigerung ist aber limitiert und bei wirklich großen Dimensionen schlägt immer die Qualität des Algorithmus durch.

Meist ist eine erhebliche Steigerung in Verbindung mit der Entwicklungs- und Laufzeitumgebung realisierbar. Denn der Unterschied zwischen einer Routine in Maschinencode und einer primitiven Interpretersprache kann schon mal den Faktor 100 bis 1000 ausmachen.

Das gleiche Problem kann mit dem gleichen Algorithmus in Excel VBA programmiert schon mal das in Stunden dauern, wofür eine Implementierung in ANSI C Sekunden gebraucht hätte. Wenn Excel nicht gleich ganz darüber abstürzt.

Kommt einfach daher, dass die gleiche Operation im Prozessor-Cache und Hauptspeicher schneller abläuft als im Hauptspeicher und auf Platte. Da schlägt halt zu, dass Excel 99,9% der Ressourcen für sich selbst verbraucht und damit die Datenmenge und die Anzahl der Operationen gigantisch aufbläht.

Vorsortierung beider Tabellen wäre vielleicht eine
Möglichkeit.

Genau DAS wäre die algorithmisch sinnvollste Lösung, da die Sortierung der beiden Tabellen deutlich weniger Vergleiche benötigt.
Dann müssten nur noch zwei Indizes die sortierten Listen runterlaufen und Quervergleiche anstellen. Statt 80.000.000 nur noch 42.000 Vergleiche (zusätzlich zum Sortieraufwand von ca. 420.000)

Und vielleicht ist beim Anwendungsfall auch noch eine Tabelle langfristig stabil.

Könnte z. B. das Einlesen der 2.000 Datensätze in ein Array
Zeitvorteile beim Vergleichen bringen?

Eine Optimierung innerhalb von Excel kann sicherlich nur sehr begrenzte Beschleunigung bringen. Leichtlauföl und Superplus machen aus einem Polo halt keinen Porsche.

Excel ist ein Werkzeug für Büroarbeiten und nicht für performante Rechenleistung bei großen Datenmengen gedacht. Nicht umsonst waren frühere Excelversionen auch gar nicht in der Lage, größere Datenmengen zu verwalten.

Vielleicht ist der Kauf einer Espressomaschine für die Wartezeit die günstige Lösung für Budget und Nerven. :smile:

Ciao, Allesquatsch

Eine ganz einfache Optimierung ist das Verlassen der Schleife, wenn du die ID gefunden hast
For i = 1 to 2000
For j = 1 to 80000
If Then

Exit For
End If
Next
Next

Ansonsten wurde Find schon erwähnt:
For Each c in SourceRange
Set DestinationCell=DestinationRange.Find (c.Value)
if DestinationCell = Nothing Then

Else

End If
Next

Leider geht aus deiner Aussage nicht klar hervor, was genau du bezwecken willst.

Vielen Dank für euren Input. Hat mir wirklich sehr geholfen und natürlich hat es Spaß gemacht, solch ein Problem mal wieder theoretisch zu durchdenken. :wink:

Werde die Daten nun in beiden Tabellen vorsortieren lassen (was relativ fix umzusetzen geht) und anschließend den Vergleich der beiden Tabellen in der Form vornehmen, dass zwar die ID-Spalte einer Tabelle vollständig durchlaufen aber parallel dazu ein einmaliger Vergleich in der ID-Spalte der zweiten Tabelle durchgeführt wird (was bei unsortierten Daten ja nicht möglich ist). Das sollte deutlich Performence bringen! Genial einfach! :wink: