Schnellere Suche?

[Cruz]

Hallo hängt ihr auch die ganze Zeit im Internet?

Ich habe ein Frage zu der Schnelligkeit von 2 verschiedenen Ansätzen von Suchalgorithmen (durch Textbasierte Datenbanken).

Man kann ja z.B. eine Datei einfach öffnen und in einen String packen. Dann kann man ja diesen String durchsuchen $string =~ m/blabla/; und hoffen, daß man etwas findet. Dabei hat man allerdings einen ganzen Batzen reduntante Daten eingelesen...alles was nicht gefunden wird, ist eigentlich redundant.

Was ist, wenn man eine Datei schon während des Einlesens durchsucht?
Also..

open (FILE, "$file)
while (<FILE>) {
if (/blabla/) {
  close(FILE);
  exit;
}
}

Ist das nicht schneller, da man sich die Einlesezeit nach der Fundstelle spart?
Oder ist es aus irgendeinem Grund doch langsamer?

Gruß
Cruz

[Calocybe]

Tag Cruz!

Hallo hängt ihr auch die ganze Zeit im Internet?

Naja, schon ab und zu. *g* Aber was hat das mit der Frage zu tun?

Man kann ja z.B. eine Datei einfach öffnen und in einen String packen. Dann kann man ja diesen String durchsuchen $string =~ m/blabla/; und hoffen, daß man etwas findet. Dabei hat man allerdings einen ganzen Batzen reduntante Daten eingelesen...alles was nicht gefunden wird, ist eigentlich redundant.

"Redundant" bedeutet eigentlich, dass dieselben Daten mehrmals an verschiedenen Stellen vorkommen. Was Du meinst, ist schlicht und einfach "ueberfluessig".

Was ist, wenn man eine Datei schon während des Einlesens durchsucht?
Also..

open (FILE, "$file)
while (<FILE>) {

»»  if (/blabla/) {

close(FILE);
  exit;

»»  }

}

Ist das nicht schneller, da man sich die Einlesezeit nach der Fundstelle spart?
Oder ist es aus irgendeinem Grund doch langsamer?

Nun... Wenn Du eine Datei zeilenweise einliest, braucht der Perl-Interpreter (bzw. die darunterliegende C-Runtime library) etwas Zeit, um die Zeilenenden zu finden, Dir Deine Daten schoen zeilenweise zu liefern, bereits gelesene Daten irgendwo zu puffern. Daher sollte man, wenn eine gesamte Datei einlesen will, und den Inhalt nicht zeilenweise braucht, dies besser so tun (incl. der geschweiften Klammern):
{
    local $/;
    undef $/;
    $content = <FILE>;
}

Fuer Deinen Fall ist das ganze Datei einlesen aber in der Tat eher ungeeignet. Denn wenn Dein Suchbegriff z.B. in der Mitte steht (und durchschnittlich wird er das wohl), liest Du die Haelfte der Datei umsonst ein. Das braucht auch nen Haufen Zeit (und zwar wahrscheinlich mehr als fuer das Zeilenenden finden, da Plattenzugriff) und auch mehr Speicher (Du haeltst ja nur eine Zeile im Speicher, nicht die ganze Datei). Und die einzelnen Zeilen brauchst Du fuer Deinen Zweck wahrscheinlich sowieso. Daher wirst Du wohl mit dem zeilenweisen Einlesen besser beraten sein.

So long

[Cruz]

Hallo Calocybe,

ich habe es gerade ausprobiert. Ich habe eine Datei mit 27000 Zeilen genommen. Zeilenweise durchsuchen ging wesentlich schneller.

Gruß
Cruz

[CK1]

Hi,

ich habe es gerade ausprobiert. Ich habe eine Datei
mit 27000 Zeilen genommen. Zeilenweise durchsuchen
ging wesentlich schneller.

naja, es kommt auch auf den Such-Allgorythmus zusammen..
eine rekursive Suche auf einem Feld ist beispielsweise
wesentlich schneller als eine iterative Suche, sprich
man geht von vorn bis hinten das Array durch und guckt,
ob das Element das gesuchte ist ,)

Ich weiß ja nicht, welchen Allgorythmus du verwendet
hast, aber bei Interesse kannst du dich ja (perl Mail?)
melden ,)

mfg
CK1

P. S.: ich möchte damit NICHT arrogant wirken, sondern
NUR meine Hilfe anbieten... auch wenns anders klingt
(leider)

[Reiner]

Hallo CK1,

Ich weiß ja nicht, welchen Allgorythmus du verwendet
hast, aber bei Interesse kannst du dich ja (perl Mail?)
melden ,)

würde mich aber auch brennend interessieren!!!
Geschwindigkeit ist sicherlich nicht IMMER das WICHTIGSTE, aber grundsätzlich finde ich solche Dinge schon auch interessant.

mfg
CK1

P. S.: ich möchte damit NICHT arrogant wirken, sondern
NUR meine Hilfe anbieten... auch wenns anders klingt
(leider)

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)!

Reiner

[CK1]

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*

[Frank Schönmann]

hi!

...alles was nicht gefunden wird, ist eigentlich redundant.
"Redundant" bedeutet eigentlich, dass dieselben Daten mehrmals an verschiedenen Stellen vorkommen.
Was Du meinst, ist schlicht und einfach "ueberfluessig".

"Redundant" bedeutet eigentlich genau das gleiche wie "überflüssig"... auch wenn es im technischen
Bereich eher für "doppelt vorhanden" steht.

bye, Frank!