2010-01-19T17:59:05 pq

2010-01-19T17:52:50 bianca

2010-01-19T17:47:06 pq

also dank der komplexität von (merge)sort O(n log(n)) ist das ganze nun wieder ineffizienter als wenn man die daten in einem hash plus array vorhält O(n).

Sorry, das ist nicht meine Welt, k.A. Hat das etwas mit meinem Lösungsvorschlag zu tun?

es ging hier um speicherverbrauch und geschwindigkeit. mit deinem algorithmus von O(n log(n)) bist du nunmal langsamer als mit einem algorithmus von O(n).
wenn das nicht deine welt ist, solltest du vielleicht lieber gar nix dazu sagen, denn genau darum geht es hier.
was habe ich von einem algorithmus, wenn durch das sort ein teil des geschwindigkeitsvorteils wieder zunichte gemacht wird?
ich bin jetzt doch etwas verwirrt, dass du hier code präsentierst und dann sagst, algorithmus-komplexitäten seien nicht deine welt. schliesslich war die laufzeit des programms ja einer der aufhänger dieses teilthreads.

bitte klär mich auf, falls du etwas ganz anderes im sinn hattest.

Moment, jetzt läuft hier was daneben!
Der Fragesteller durchläuft für jedes Element von Liste A jedes weitere Element von Liste B, also Menge A mal Menge B, um doppelte zu finden.
Meine Lösung durchläuft dafür die Liste garnicht, es baut auf if exists.....
Ich habe den ganzen Heckmeck mit der ursprünglichen Sortierung der Liste nur gemacht, weil meine Hash-Lösung insofern "angegriffen" (sachlich, nicht persönlich!) wurde, als man da keine Reihenfolge hat, was in meinen Augen zwar technisch zutrifft, weil Perl von Natur aus ein Hash nicht sortiert, man dies aber durch eine zweite Dimension ganz leicht beheben kann.

Angenommen, der Fragesteller braucht die Reihenfolge seiner Liste garnicht (wissen wir ja bisher nicht), kommt meine Lösung ohne jegliches Sort aus und hat die gesamte Liste nur einmal im Speicher.

Edit: Ich vergaß zu erwähnen, dass das sort in JEDEM Fall nur einmal bei der Ausgabe zwecks ursprünglicher Sortierung gemacht wird, was man aber ja eigentlich auch dem Code entnehmen kann aber anscheinend dennoch nicht verstanden wurde (?)
Last edited: 2010-01-19 19:24:51 +0100 (CET)