nicht angemeldet
Hi,
würde mich aber auch brennend interessieren!!!
Geschwindigkeit ist sicherlich nicht IMMER das
WICHTIGSTE, aber grundsätzlich finde ich solche
Dinge schon auch interessant.
Also, im Grunde gibt es drei große Suchallgorythmen. Der
erste ist auch der einfachste Allgorythmus:
man geht einfach das gesamte Feld durch und sieht nach,
ob das aktuelle Element das gesuchte ist. Das könnte z.
B. so aussehen:
for($i=0;$i<=$#feld && $feld[$i] != $such; $i++) ;
Dieser Allgoryhtmus hat den Vorteil, daß er sehr einfach
ist *g*
Aber der Nachteil ist, daß er sehr langsam ist. Das
macht sich bei Datensätzen > 500 in der Zahl schon in
Sekunden bemerkbar. Außerdem findet der auch keine
Dubletten, sondern er sucht nur bis zum ersten
Vorkommen ,) Würde man ihn bis zum Ende laufen lassen,
würde er noch mehr Zeit benötigen.
Der zweite Allgorythmus geht von einem sortierten Feld
aus (egal, ob aufsteigend oder absteigend, ich gehe mal
von einem absteigend sortiertem Feld aus) und arbeitet
rekursiv. Dadurch ist er natürlich auch komplizierter ,)
Also, man definiert eine Sub. Der Sub werden 4
Parameter übergeben:
$a als linke Begrenzung für das Feld,
$b als rechte Begrenzung für das Feld,
@feld (das Datenfeld) und
$such, der gesuchte Wert.
$a und $b werden benutzt, um das Feld einzuteilen: man
errechnet zuerst die Mitte des eingegrenzten Feldes:
$mitte = ($a + $b) / 2;
So, wenn nun $a != $b und $a < $b, dann wird nachgesehen, ob
$such > $feld[$mitte]. Ist dies der Fall, so wird die Sub wieder
aufgerufen, diesmal mit den Parametern
$mitte als linke Feldbegrenzung,
$b als rechte Feldbegrenzung,
@feld als das zu durchsuchende Feld und
$such als der zu suchende Wert ,)
Ist $such aber <= $feld[$mitte], so wird nachgesehen,
ob $feld[$mitte] kleiner oder gleich $such ist. Ist dies
der Fall, so wird die Sub wieder aufgerufen, diesmal mit
den Parametern
$a als linke Feldbegrenzung,
$b als rechte Feldbegrenzung,
@feld als das zu durchsuchende Feld und
$such als der zu suchende Wert.
Ist $such aber == $feld[$mitte], so
wird die Stelle gespeichert, ausgegeben,
was weiß ich, egal, auf jeden Fall wird
hier die Rekursion durchbrochen.
Das sähe so oder so ähnlich aus:
sub such_sort_feld
{
my $a = shift;
my $b = shift;
my @feld = shift;
my $such = shift;
my $mitte = ($a + $b) / 2;
if ($a != $b && $a < $b)
{
if($such > $feld[$mitte])
{
&such_sort_feld($mitte, $b, @feld, $such);
} else {
if($such < $feld[$mitte])
{
&such_sort_feld($a, $mitte, @feld, $such);
}
if($such == $feld[$mitte])
{
# Verarbeitung der Stelle, Abbruch der Rekursion
}
}
}
}
@feld = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
&such_sort_feld(0,0,@feld,9);
Dieser Allgorythmus hat den Vorteil, daß er sehr
schnell ist und alle Entsprechungen findet. Der
Nachteil ist allerdings, das er sehr speicherintensiv
ist und ein sortiertes Feld vorraussetzt.
Der dritte Allgorythmus funzt noch ganz anders. Hierbei
wird ein Hash erstellt, bei dem alle Einträge als Key
vorhanden sind:
@feld = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);
%bla = {};
foreach (@feld)
{
$bla{$_} = 1;
}
So kann ganz einfach festgestellt werden, ob der
gesuchte Eintrag vorhanden ist:
if(defined $bla{$such})
{
print "Eintrag ist vorhanden";
} else {
print "Nicht vorhanden";
}
Das ist natürlich noch nicht alles, das kann man
noch viel weiter ausbauen, aber es reicht, um
das Prinzip zu erklären ,)
Der Nachteil ist, daß man zwei große Felder hat,
die natürlich auch den Speicher verstopfen... außerdem
ist auch der wieder sehr Zeitaufwendig, ich hab zwar
nicht getestet, wie langsam, aber ich denke, das lohnt
sich nur, wenn man viele Suchen durchführt, da die
Initialisierung des Hashes genau so lange dauert wie
der erste beschriebene Suchallgorythmus.
So, ich bin mir fast sicher, ich hab nicht alle
Allgorythmen beschrieben, aber das sollten so die
3 größten sein ,)
Arrogant klingt es nicht, aber schön wäre es
dennoch, auch über solche Dinge zu diskutieren,
denn oftmals hat man einfach keinen Zugriff auf 'ne
Datenbank (bzw. es besteht nicht die Notwendigkeit)!
naja, ich wollte nur nich den Eindruck eines arroganten
Oberlehrers erwecken ,)
mfg
CK1
P. S.: Sorry für das Riesen-Posting *g*