squeez07.04.2007 · Beitrag #12922Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag
Im Thread [1] habe ich behauptet, dass der von Stefan gepostete Artikel Performanceprobleme aufgrund der verwendeten Hashmap provoziert.
Ich habe festgestellt, dass das Problem etwas komplexer ausfällt, wenn man diese Aussage genau betrachtet.
Hier die Quizfrage:
Stimmt diese Aussage ?
· Wenn ja, unter welchen Voraussetzungen trifft sie zu ?
· Wenn nein, was muss gegeben sein, damit die Performance nicht beeinträchtigt wird ?
Es genügt jeweils eine Abschätzung.
Nur Mut mit den Antworten, es wäre interessant was dabei herauskommt.
Marco
[1]http://www.computec.ch/forum_viewtopic.php?11.12904
[ Bearbeitet ]
Mitglied seit: 04.04.2007
Forenbeiträge: 33
Besuche: 446
Ich würde mal behaupten, dass hängt davon ab, wie voll die Hashmap ist, und ob da viele Kollisionen drin vorkommen. Ob es sinnvoll ist, hängt davon ab, wie gut man die Auswahloptionen kennt.
Ich schätze auch, desto weniger Kollisionen existieren, desto weniger ist die Performance beeinträchtigt.
squeez10.04.2007 · Beitrag #12976Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag
Eine gute Antwort.
Betrachten wir folgendes:
Ablauf gemäss Link:
1) Bei der Setup Routine des Programmes wird von verschiedenen Strings ihr Hashwert berechnet.
Dieser dient als Key in die Hashtabelle.
1.1) Hashfunktionen laufen im worst case mit O(n). Diese Feststellung ist lediglich wichtig, um ein lineares Wachstum zu betrachten.
1.2) Diese Hashwerte werden mittels einer Zahl (Value) in der Tabelle abgelegt.
2) Vor dem switch () erfolgt eine Hashberechnung des eingegebenen Strings.
3)Dieser Hashwert wird genau 1-mal berechnet.
Für die 'case' Zuordnung ist nun genau 1 Vergleich notwendig.
Ablauf gemäss strcmp oder interne Funktionen
Wenn die Lösung mit einem Vergleich der Strings erfolgt, würde dies folgendes Szenario ergeben:
1) Die Anzahl der Vergleiche für die einzelnen Strings ist intern in den Funktionen optimiert. Dh, wenn ein
String mit einem 'a' beginnt, und ein damit zu vergleichender mit 'b', so kehrt die Funktion gleich wieder zurück und verschwendet keine weiteren Rechenoperationen für die Vergleiche.
1.1) Im worst case bedeutet dies, dass sich alle Strings lediglich um ein Zeichen (am Schluss oder am Anfang, je nach zu Grunde liegendem Vergleichalgorithmus) unterscheiden, und damit n-1 Vergleiche geführt werden müssen, und zwar pro String in der Auswahl.
Vergleiche der beiden Verfahren
· Die Performance der Hashfunktion hängt nicht vom Inhalt des Strings ab, sondern lediglich von der Länge der Eingabe.
· Die Performance des Stringvergleichs mittels strcmp oder interner Funktion hängt hingegen sehr stark von der Länge einerseits und vom Inhalt andererseits ab.
Fazit
Die Hashfunktion ist schon schnell einmal effizienter, besonders wenn man viele 'case' Aufrufe hat.
hth
Marco