arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Thus spoke Martin Trautmann (on 2006-09-26 10:00):

> Datei1:
> ID: 11
> A: A1
> B: B1
> C: C1
>
> Datei2:
> ID: 2
> A: A2
> D: D2
> B: B2
>
> Das ganze soll dann als Tabelle ausgegeben werden:
>
> ID A B C D
> 2 A2 B2 D2
> 11 A1 B1 C1 -
> ...
> Moeglicherweise beeinflusst das, welche
> Datenstruktur man waehlen sollte?

Die Frage wäre erstmal, was denn für Daten das sind,
also
- gibt es immer "feste keys" (ID, A, D, X), die
überschaubar bleiben?

Also - könnte man praktisch mit einer festen
Array-Indizierung (columns) im Record arbeiten(?):

my $idx = { ID=>0, A=>1, B=>2, C=>3, D=>4 }; # feste indices

my $records = [
...
[ 11, 'A1', 'B1', 'C1', undef ],
[ 2, 'A2', 'B2', undef, 'D2' ],
...
];


- sind die ID's selbst "vorhersehbar" und mehr oder
weniger 'subsequent', also könnte man bereits ID
als Index für den Record verwenden?

...
$record[11] = [ 'A1', 'B1', 'C1', undef ];
$record[2] = [ 'A2', 'B2', undef, 'D2' ];
...

Ich würde wahrscheinlich versuchen, so wenig
wie möglich in den Records - und so viel
wie möglich in der 'Datenstruktur' zu haben.

Viele Grüße

M.

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Moin,


von wievielen Dateien/Datensätzen gehst Du momentan aus, die da in einem
Rutsch verwurschtet werden sollen?

Da die später notwendigen Auswetrungen/Darstellungsformen anscheinend
noch nicht sonderlich klar spezifiziert sind, würd' ich da recht schnell
an die Zwischenschaltung einer Datenbank denken.

Dein Script müsste dann nur noch die Daten in die DB pumpen. Zur
Auswertung kann man dann entweder ebenfalls wieder scriptgesteuert oder
mit einem beliebigen Reportgenerator auf die DB zugreifen.

Würd' ich mir zumindest einmal durch den Kopf gehen lassen.

Gruss,
Bernd

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Moin,


ok, Du scheinst Dir da schon Gedanken gemacht zu haben. Ich wollte es
nur ansprechen.

Ich würd' dann bei der Struktur einen Hash of Hashes nehmen.

Erste Ebene eine eindeutige ID. Wenn Du eine eindeutige in den letzlich
zu verarbeitenden Datensätzen hast, kannst Du die nehmen (wenn doppelte
IDs sowieso zu einer Fehlermeldung und/oder Nichtverarbeitung führen,
kannst Du ja einfach auf die Existenz prüfen, bevor Du mit den Daten
einen vielleicht schon bestehenden Satz überschreibst).

Darin liegt auch der Grund, warum ich einen HASH of Hashes nehmen würde,
und kein Array - die ID kann dann aussehen, wie sie will.

In der zweiten Ebene dann die Keys, und die Werte dann als Value.

Solange auch die Values nicht allzu dick werden, also nicht auf einmal
anstatt eine URL zu einem Bild das Bild selbst als BLOB auftaucht),
sollte das bei den angegebenen Datenmengen noch handlebar sein.

Gruss,
Bernd

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Moin,


>> Darin liegt auch der Grund, warum ich einen HASH of Hashes nehmen würde,
>> und kein Array - die ID kann dann aussehen, wie sie will.

> Hm - danke, das ist ein interessantes Argument. Ich haette vermutet,
> dass ein hash of hashes deutlich langsamer ist als ein array of hashes.
> Von meinem bisherigen Denken her haette ich sogar ein zweidimensionales
> array bevorzugt - also eher ein array of arrays. Aber mangels bisheriger
> Performance-Tests gehe ich jetzt mal davon aus, dass hashes in perl
> immens flott abgearbeitet werden.

meine rein persönlichen Erfahrungen aus den letzten, hmmmm, rund zehn
Jahren Perl: Hashes und Regular Expressions sind in Perl sehr effizient
realisiert. Zumindest, solange man genug Hauptspeicher hat - einen Tod
muss man halt sterben. Im Regelfall tendiert Perl nämlich dazu,
ordentlich Speicher auf ein Problem zu werfen, um dafür performant zu
bleiben.

Bei überschaubaren Datenmengen nehm' ich darum immer den Kram, in dem
die Realisierung am elegantesten geht und mach' mir keine grossen Sorgen.

Einzige Ausnahme: Web-Geschichten auf gut besuchten Sites, wo durchaus
auch 'mal Hundert oder mehr Instanzen parallel laufen können - da
summiert's sich eher.


Reine "Bauchgefühl" basierende Einschätzung:

> Grobe Abschaetzung der Menge: bis 100
> keys (typisch bis 10), bis 1000 Dateien

(aus einem älteren Posting)

und

> das sollte in der Regel zwischen in paar Bits
> und unter 256 Bytes liegen (max. 1 k) - laengeres
> ist ausgelagert.

Damit komme ich im Schnitt auf vielleicht 20 Keys/Datei, 1000 Dateien
(womit wir bei 20000 Keys wären), mal vielleicht 512Byte. Rund 10MB
"Values", die Du ja auf jeden Fall irgendwie im Speicher haben must.

Der I/O als grundsätzliche Bremse - viele kleine Dateien sind einfach
wesentlich langsamer zu verarbeiten als wenige grosse. Das ist Dir klar,
soll nicht geändert werden und wäre bei jeder denkbaren Realisiernug der
Fall.

Bleibt noch der Overhead bei der internen Organisation der Daten. Da
sind die Perl eigenen Mechanismen bei ausreichend Speicher eigentlich
ganz gut. Unabhängig, ob man mit Arrays oder Hashes arbeitet.

Nicht vergessen dabei: Die Arrays in Perl sind ja auch extrem dynamisch
und damit auch nicht sooooo trivial in ihrer internen Verwaltung.

Für beide (Hashes und Arrays) gilt ausserdem, dass sie seit den
"Ur-5er-Versionen" stetig weiter entwickelt wurden. Unter der Haube, und
fast immer ging es dabei um die Steigerung der Effizienz - Vermeidung
unnötigen internen Aufwandes bei häufig benutzten Operationen.

Desweiteren ist Perl nicht wirklich in der Lage, auf niedrigster Ebene
Bits so effizient durch die Gegend zu schubsen, dass Du damit Zeit im
Vergleich zur Behandlung komplexerer Strukturen sparst. Wirklich "hard
core optimizing" Deiner Datenstrukturen geht mit Perl nicht.


Solange das nicht gerade auf einem embedded System stattfinden soll,
würd' ich mir also keinen Stress machen und die Implementierung so
trivial und übersichtlich wie möglich halten.

Wäre ich mir unsicher, würd' ich vielleicht gucken, möglichst früh einen
Test nicht nur mit den üblichen 10, 15 Testdateien zu fahren sondern da
wirklich einmal realitätsnahe Datenmengen 'drauf zu werfen - die
Ergebnisse in einem solchen Fall hatten mich bislang aber so gut wie
immer davon überzeugt, dass ich richtig gelegen hatte.


Ist jetzt alles eine reine Bauch-Einschätzung gewesen. Würde mich
freuen, wenn Du Bescheid gibst, wie's in der Realität ausgegangen ist.

Gruss,
Bernd

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Moin,


> Meine ersten Gehversuche wackeln auf
> http://fa-technik.adfc.de/Codierung/fein.pl herum
> [...]

oh je, ein Fahrrad-Fahrer. Wenn ich das gewusst hätte... ;-)


> Wo die Performance spuerbar in die Knie geht, das ist die Suche in
> der bayrischen Provinz - da muss dann eine Gesamtliste mit 100 000
> Strassen durchsucht werden, und zwar nicht bis zum ersten Treffer,
> sondern komplett - und wenn beim ersten Durchgang nichts gefunden wurde,
> dann gibt's eben einen zweiten oder dritten Durchgang mit immer weiter
> gelockerten Kriterien (passt ganz, passt am Anfang, passt teilweise).

wie oft kommt es zu einer zweiten, dritten oder x-ten Suche?

Wenn oft genug, könnte man darüber nachdenken, *erst* die unschärfste
Suche zu machen, und dann auf die gelieferten Treffer-Teilmenge mit
immer präziseren Suchen loszugehen, bis man keine Treffer mehr erhält.

Oder nach der unschärfsten Suche nur noch die Treffer zu gewichten und
das dann als Sortierreihenfolge zur Darstellung anzubieten.

Ist auch wieder ohne viel nachzudenken aus der Hüfte geschossen, als
Denkansatz.


> Als naechstes soll da dann ein Komponenten-Wiki hinzukommen, um
> technische Daten zu suchen und zu sortieren bzw. auch selbst einzugeben.
>
> Wikidata kommt bisher nicht so richtig in die Gaenge, und ohne SQL
> sollte es obendrein auskommen. Daher der Perl-Ansatz. Mal sehen, was
> draus wird...

Bei "Wiki ohne SQL" fällt mir MoinMoin ein. Kenne ich allerdings nur als
User, und ausserdem basiert's auf Python.

Gruss,
Bernd

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Martin Trautmann wrote:

> Meine ersten Gehversuche wackeln auf
> http://fa-technik.adfc.de/Codierung/fein.pl herum - da kann man sich zur
> Wertsachen- und Fahrradcodierung eine Adressverschluesselung abrufen,
> die die Polizei wieder entschluesseln kann.

Versteh ich das richtig: Du willst ganz einfach einen Key und den
dazugehörigen Value finden.

> Das ganze laeuft fuer mich ueberraschend schnell, obwohl ich einige
> Eingabefehler abgefangen habe. Die Strassensuche aus einer Million
> Strassen geht da voellig unproblematisch, denn gesucht wird immer nur in
> einer kleinen Teildatei der Gemeinde.

Bei solchen Datenmengen, noch dazu in einer Web-Anwendung, würde ich
(als eingefleischter Gegner von Datenbanken) doch zu einer extern
indizierten Methode greifen.

> Wo die Performance spuerbar in die Knie geht, das ist die Suche in
> der bayrischen Provinz - da muss dann eine Gesamtliste mit 100 000
> Strassen durchsucht werden, und zwar nicht bis zum ersten Treffer,
> sondern komplett

Dazu gibt es Standardlösungen wie z.B. Datenbanken oder dict(d), die
jede ihre Vor- und Nachteile haben.

> Bei den Staedten und Gemeinden arbeite ich da schon 'vorverdaut' (upper
> case, Umlaute auscodiert, Getrenntschreibung aufgeloest).

Das sind Standardprobleme, die in dictd hochperformant gelöst sind.
Schau z.B. auf www.dict.org, wie einfach und schnell man dort suchen
kann. Auch für MySQL gibt es vermutlich Standardbibliotheken mit
Suchmethoden, wenn ich mir z.B. dict.cc (dürfte PHP+MySQL sein) anschau.

Helmut Wollmersdorfer

Re: arrays, hashes oder was?

Post removed (X-No-Archive: yes)

Re: arrays, hashes oder was?

Martin Trautmann wrote:

> Stimmt, die Woerterbuch-Suche kommt der Problematik recht nahe.
> Zu dictd habe ich noch wenig gefunden, und RFC 2229 mit dem
> DIC-Protokoll erscheint mir unnoetig.

Das ist ein einfaches Client-Server Protokoll, das sich über Net::Dict
oder über die Shell mit 'dict $suchbegriff' abwickeln lässt. Natürlich
hast Du dann einen Demon laufen, wie bei einer Datenbanklösung auch.

> http://packages.debian.org/stable/text/dictd zielt wohl eher auf
> englischsprachiges ab.

Die neuere Version 1.10.2 (Debian testing/unstable) hat gute utf-8
Unterstützung. Ich verwende sie hier http://www.nomen.at für derzeit 133
Sprachen, auch in ausgefallenen Schriftsystemen wie z.B. asiatische oder
sogar rechts-links-laufende wie Hebräisch oder Arabisch.

Sowas wie (Achtung - utf-8 erforderlich)
Query string: اللقلق
Search type: Match separate words within headword
funktioniert auch.

> Die passende Behandlung in Hinblick auf
> Strassennamen sehe ich da nicht im Zielfeld

Zunächst einmal sind das auch nur Wörter.

> - da gibt's z.B. spezielle
> Abkuerzungsprobleme

-g. für Gasse?
Mit prefix 'Einstein' würde z.B.
- Einsteing.
- Einsteingasse
- Einsteinplatz
etc. gefunden.

> und natuerlich Umlaute, alte und neue
> Rechtschreibung.

Obwohl 'SOUNDEX' von dict(d) am Papier nur Englisch unterstützt, ist das
doch auch für andere Sprachen halbwegs brauchbar.

Siehe z.B. auf http://www.nomen.at
Query string: Vögel (oder Voegel, Vogel, Vogl)
Search type: Match using SOUNDEX algorithm

Die Suche innerhalb Deines cgi ausdehnen oder einschränken, Abkürzungen
expandieren, Schreibweisen vereinheitlichen etc. kannst Du immer noch
ganz einfach.

> Daher kann ich noch nicht ganz erkennen, wo und wie mir
> das helfen könnte?

Vermutlich deckt das 95% Deiner Problematik ab, wenn nicht sogar 99%.
Sich selber Suchalgorithmen zusammenbasteln kann natürlich auch
interessant und lehrreich sein.

Der Nachteil von dict(d) ist IMHO halt, dass die Files statisch
generiert sind. Datenpflege über eine Community in Echtzeit wie z.B. auf
www.dict.cc wäre umständlich.

Helmut Wollmersdorfer

Re: arrays, hashes oder was?

Martin Trautmann writes:
> Wo die Performance spuerbar in die Knie geht, das ist die Suche in
> der bayrischen Provinz - da muss dann eine Gesamtliste mit 100 000
> Strassen durchsucht werden, und zwar nicht bis zum ersten Treffer,
> sondern komplett - und wenn beim ersten Durchgang nichts gefunden wurde,
> dann gibt's eben einen zweiten oder dritten Durchgang mit immer weiter
> gelockerten Kriterien (passt ganz, passt am Anfang, passt teilweise).
>
> Bei den Staedten und Gemeinden arbeite ich da schon 'vorverdaut' (upper
> case, Umlaute auscodiert, Getrenntschreibung aufgeloest).

Vielleicht solltest Du Dir eine geeignete C-Library zur
Stringverarbeitung suchen. Bei der String-Suche ist es immer noch am
besten, die Datenbank vorzuverarbeiten, so daß die Suchzeit nicht mehr
(nennenswert) von der Datenbankgröße abhängt.

Wenn's jedoch schon performant genug geht, kann man sich so etwas
natürlich sparen.

Thomas Jahns
--
"Computers are good at following instructions,
but not at reading your mind."
D. E. Knuth, The TeXbook, Addison-Wesley 1984, 1986, 1996, p. 9

Re: arrays, hashes oder was?

Moin,


>>Bei den Staedten und Gemeinden arbeite ich da schon 'vorverdaut' (upper
>>case, Umlaute auscodiert, Getrenntschreibung aufgeloest).

> Vielleicht solltest Du Dir eine geeignete C-Library zur
> Stringverarbeitung suchen. Bei der String-Suche ist es immer noch am
> besten, die Datenbank vorzuverarbeiten, so daß die Suchzeit nicht mehr
> (nennenswert) von der Datenbankgröße abhängt.

weniger zur Stringverarbeitung, als in einem grösseren Zusammenhang.
Deswegen hatte ich am Anfang eine Datenbank in's Spiel gebracht, und ein
weiterer Poster dict.

Die pure Stringverarbeitung ist in Perl (solange genug Speicher da ist)
schon recht fix, besonders wenn man die jeweils geeignete "kleinste" im
Perl Core verfügbare Lösung nimmt.

Soll, grob über den Daumen gepeilt, heissen: Nicht gleich auf alles mit
einer RegEx losgehen, sondern erst einmal die Doku zu Funktionen wie lc,
uc, substr, pack/unpack lesen, sich tr 'mal angucken, und erst dann zur
RegEx greifen. Ist in etwa die Performance-Hitliste (einfache,
eingebaute Funktionen -> tr -> RegEx).

Dann musst Du schon ernsthaft suchen, um performantere (und trotzdem
stabile) Libs für C zu finden. Klar, gibt es, aber die nächstbeste mit
'n paar netten Stringfunktionen ist wahrscheinlich nicht schneller als Perl.

Was Perl da bremsen kann, sind die langen Ladezeiten. Muss das Programm
aber nur einmal geladen werden und verarbeitet dann satte Datenmengen,
relativiert sich das.

Ebenfalls eng wird's, wenn eben nicht viel Speicher verfügbar ist. Perl
selbst schluckt schon einiges, und schmeisst zur
Geschwindigkeitsoptimierung gerne Speicher auf ein Problem. Vor dem
gleichen Problem stehen aber auch andere Libs: Performante, aber
trotzdem flexible Stringverarbeitung kostet einfach Speicher.

Wenn beide Punkte nicht relevant sind, schlägt sich Perl recht wacker.
Sind zumindest meine Erfahrungen, auch gewachsen durch den Wettkampf mit
einem recht fitten "also mit C würde das sicher noch schneller gehen,
lass' mich da 'mal einen Blick 'drauf werfen" Kollegen.

Gruss,
Bernd