linux-l: perl und schnelle Suche

[Steffen Dettmer]

* Ulrich Wiederhold wrote on Fri, Jun 15, 2001 at 20:34 +0200:
> 1. Einlesen in ein hash, mittels

Das mit dem Hash ist nicht schlecht. Ein Hash ist ja ein Index.
Dazu mußt Du aber genau wissen, wie die Suchanfragen später
aussehen, sonst bringt das nix. Angenommen, als Anfrage kommt ein
Word. Case interessiert Dich nicht.

1. vereinfachungs-Funktion:
sub index_word($)
{
	my $word = shift;
	$word = lc($word);
	$word =~ tr/ /_/;
	#usw.
	return $word;
}

2. Index aufbauen
foreach my $word (@words) {
	#word speichern:
	$index{ index_word($word) } = $word;
	#Wenn weitere Infos gebraucht werden, was ja normal sein
	#sollte, muß man ne Liste verwenden:
	$index{ index_word($word) } = [$word, "weitere Infos"];
	#oder einen hash:
	$index{ index_word($word) } = { 'word'  => $word, 
	 				'info1' => "weitere Infos" };
}

3. Durchsuchen:
sub return_info($)
{
	my $word = shift;
	$word_i = index_word($word);
	#angenommen, wir haben einen Hash mit info1
	if ($index{ $word_i }->'word' eq $word) {
		return $index{$word_i}->{'info1'};
	}
}

Das geht natürlich nicht mehr, wenn Du Wörter hast, die nach dem
index_word gleich werden, z.B. zwischen "paar" und "Paar"
unterscheiden möchtest (was bei case-in-sensitivität eh schlecht
geht :)). Dann jedenfalls keinesfalls schreiben: 

foreach my $key (keys %index) 

oder so, weil Du dann den Hash mißbrauchst und langsam machst.
Der Trick ist, eben immer nur einen Zugriff zu brauchen, um den
Wert zu finden. Hast Du mehere, mache lieber ein Index-Hash, der
eine Liste mit Wörtern enthält, oder eine liste mit hashes, z.B.:

	push @{$index{ index_word($word) }}, 
		{ 'word'  => $word, 'info1' => "weitere Infos" };

Zugriff dann so wie:

sub return_info($)
{
	my $word = shift;
	$word_i = index_word($word);
	#angenommen, wir haben einen Hash mit info1
	my $i_list_ref = $index{ $word_i };

	foreach my $hash_ref (@$i_list_ref) {
		if ($hash_ref->{'word'} eq $word) {
			return $hash_ref->{'info1'};
		}
	}
}

Idee verstanden? Auf große Daten (hier $index) wird nur ein
Zugriff ausgeführt. Das liefert dann wenig Daten, die man dann
sequentiell durchsuchen kann. Das ist dann schnell, deshlab
machen Datenbanken das auch so :)

oki,

Steffen

-- 
Dieses Schreiben wurde maschinell erstellt,
es trägt daher weder Unterschrift noch Siegel.