Kniffliges Problem mit einer verschachtelten Schleife

[Darthshoot]

Hallo!

Also nehmen wir mal an ich habe lauter Zahlencodes (15302 Stück) in das Array "Hauptliste" gespeichert und in eine "Abgleichliste" (115 Stück) zum Vergleichen. Jetzt sollen also diese Zahlencodes verglichen werden und jedesmal, wenn ein Code aus der Abgleichliste nicht in Hauptliste gefunden werden kann, soll er in eine Textdatei die ich vorher schon geöffnet habe reinschreiben, dass die Zahl net da ist. Jetzt mal zur Schleife:

for ($i = 1; $i <= 15302; $i++)
{
for ($j = 1; $j <= 115; $j++)
{
if ($Hauptliste[$i] == $Abgleichliste[$j])
{
print liste $Abgleichliste[$j]."\n";
}
}
}

Also zuerst sollen 15302 Codes aus Hauptliste verglichen werden. Jeder Code DAVON soll mit 115 Codes aus Abgleichliste verglichen werden. Ne einfache ineinander verschachtelte Schleife halt. Aber irgendwie geht's net. Er meint immer:

Use of uninitialized value in numeric eq (==)

Und ich habe nur einmal == im Programm stehen: In der if Abfrage, wo nun endlich geprüft wird, ob die Codes übereinstimmend sind.

Bitte helft mir ich bin schon am verzweifeln o.O bin hier auf der Arbeit und komm nicht weiter.

Danke im Voraus.
MfG Darthshoot

[smg]

#!/usr/bin/env perl

use utf8;
use strict;
use warnings;

my @hauptliste = (1..15302);
my @abgleichliste = (1..115);

for my $h (@hauptliste) {
for my $a (@abgleichliste) {
if ($h == $a) {
print STDOUT $a
}
}
}

Geht ohne Probleme!

[Darthshoot]

EDIT: Es funzt doch! Danke!!! Ich hatte bloß net damit gerechnet, dass aus 115 Zahlen nur knapp 10 mit den 15000 übereinstimmen.... XD

[gencha]

Das Teil schreit ja förmlich nach Optimierungen :P

[smg]

EDIT: Es funzt doch! Danke!!! Ich hatte bloß net damit gerechnet, dass aus 115 Zahlen nur knapp 10 mit den 15000 übereinstimmen.... XD

lol

Das Teil schreit ja förmlich nach Optimierungen :P

Premature optimization is the root of all evil. ~ Donald Knuth

[73r0c001]

Premature optimization is the root of all evil. ~ Donald Knuth

On the other hand, we cannot ignore efficiency. ~ Jon Bentley

[gencha]

Das is ja wohl lachhaft ;) Eine quadratische Laufzeit kann man mit ruhigem Gewissen sofort beseitigen. Das hat mit verfrühter Optimierung echt garnix zu tun.

[smg]

Das is ja wohl lachhaft ;) Eine quadratische Laufzeit kann man mit ruhigem Gewissen sofort beseitigen. Das hat mit verfrühter Optimierung echt garnix zu tun.
Tjo, O(n^2) ist noch nicht soo schlimm :P Aber kannst es ihm ja gerne optimieren, ich hab dafür keine Zeit.

[eViL_oNe]

warum nicht folgender Ansatz:

man durchläuft die Hauptliste, und prüft, ob deren Wert nicht in einer Hashtable existiert. Durch dieses Vorgehen erreicht man fast lineares Laufzeitverhalten und hat kaum Aufwand:

my @hauptliste = ...;
my %abgleichliste = ...;

my $i;
for my $zahlencode ( @hauptliste )
{
if ( exists( $abgleichliste{$zahlencode} ) )
{
print $zahlencode . "\n";
}
}

welche Werte man zu den Keys der abgleichliste erfasst, ist im Grunde genommen egal -- etwa 1 oder so was ;)

jetzt könnte man natürlich noch auf die Idee kommen, die Abgleichliste irgendwo dynamisch auszulagern oder ähnliche nette Optimierungen, die ich hier nicht weiter ausführen will ;)

[cracki]

@smg:

python code:
Hauptset = set(Hauptliste)
[x for x in Abgleichliste if x not in Hauptset]


das ist hoechstens n * log(n) laufzeitkomplexitaet, weil python's "x in S" operation auf sets doch recht fix ist (log n schlimmstens, eventuell sogar konstant).

wie gencha, 73r0c001 und eViL_oNe schon erkannt haben, gibt es hashes in perl, mit denen man sets nachahmen kann.

dein code fuehrt 115*15302 = 1.76 millionen vergleiche durch. mit einem einfachen break bei erfolgreichem fund haettest du die vergleiche halbieren koennen.
wenn ich bei einem hash/set von log_2(n) laufzeit ausgehe, bleiben noch etwa 115*log_2(15302) = 1600 vergleiche uebrig.

in der gegebenen datenmenge ist die geschachtelte schleife mit quadratischer laufzeit 1000 mal langsamer.

bei scriptsprachen wuerde ich sowas nicht unter den tisch kehren. im kopf mal ueberschlagen, wenn du mit halbwegs grossen datenmengen hantierst.

schaut euch alle mal http://www.projecteuler.net/ an. dort kann man mit einer scriptsprache und guten algorithmen jeden handoptimierten aber naiven algorithmus schlagen.

[eViL_oNe]

@Jan: wie kommst du auf O(log(n)) bei perl hashes? Auch wenn es sicherlich gewagt ist, bei einem hash von O(n) auszugehen, sind perl hashes afaik unsortiert und werden ähnlich implementiert sein wie etwa in java.util.HashMap...

[smg]

cracki: mir geht's garnet dadrum, ich wollte nur testen ob dem Thread Starter sein Code überhaupt funktioniert, und das hat er, ob er nun zu optimieren ist, ist mir egal, natürlich ist O(n^2) scheisse... aber das war ja garnicht die Frage, der hatte ein Problem mit dem == und eq Teil seines Codes den ich nicht nachvollziehen konnte, jetzt geht's ja auch bei ihm.

eulerproject, kann ich dir sagen dass ich 99% genius dort bin (d.h. ich hab fast alles gelöst, nicht nur mit perl, auch mit haskell, common lisp und python) ich weiss wie man optimiert... und ich weiss dass die for-loops sehr suboptimal sind, aber darum ging es nicht in diesem thread (eigentlich) sondern um das "problem" dass er mit dem == und eq hatte, und nur dort wollte ich nachhaken. da der code ja schlecht ist von der laufzeit her könntest du es dem Thread Starter empfehlen oder diesen negativ bewerten, da das ja nicht MEIN code ist. ich wollte seinen code kurz nachvollziehen aber weder optimieren noch verbessern... das kann dann der jenige tun der den code geschrieben hatte.

ich finde es nur nicht nett, dass du so heimlich einfach negativ bewertest obwohl ich überhaupt nicht den code von ihm optimieren wollte, und ich auch keinen neuen _optimierten_ code posten wollte sondern nur diesen nachvollziehen.

EOD für mich

[Jan Krüger]

@Jan: wie kommst du auf O(log(n)) bei perl hashes? Auch wenn es sicherlich gewagt ist, bei einem hash von O(n) auszugehen, sind perl hashes afaik unsortiert und werden ähnlich implementiert sein wie etwa in java.util.HashMap...
Per Definition ist der Abruf von Elementen aus Hashtabellen im schlimmsten Fall in O(n); das tritt aber bei einer guten Hashfunktion und einer hinreichend großen Hashtabelle nur sehr selten auf. Der durchschnittliche Fall ist in O(1). Wie du schon sagst, sind sie unsortiert.

Bei typischen Set-Implementierungen ist der Abruf in O(log n), da die Elemente sortiert gespeichert sind (entweder als sortierte Folge oder in einem Suchbaum irgendeiner Art).

Fazit: bei einer geeigneten Hashtabellen-Implementierung ist die Verwendung einer solchen die bessere Wahl (auch der Aufwand für die Initialisierung ist erwartungsgemäß kleiner, nämlich normalerweise in O(n)).

Bleibt nur noch die Frage, ob der Threadstarter das überhaupt so genau wissen wollte. ;)