PureBasic 4.40 Beta1 released!

[Little John]

Ich freue mich sehr über die neue Map-Library, da ich sowas öfter gut gebrauchen kann. Dafür nochmal vielen Dank!

In einigen meiner Programme liegt eine Situation ähnlich wie z.B. am Empfangsschalter eines Kongressbüros vor: Jeder ankommende Besucher soll ein eindeutiges Namensschild bekommen, auch wenn manche Namen mehrfach vorkommen.

Ich benutze dafür im Moment eine selbst geschriebene Hash-Funktion, fände es aber schöner (und es wäre im Prinzip wohl auch schneller) zu diesem Zweck die Map-Library von PB 4.40+ zu verwenden. Folgender Code demonstriert was ich meine:

Code: Alles auswählen

; PB 4.40 Beta 1

EnableExplicit

Define k, p
Define name$

;-- Testdaten (könnten auch z.B. in einer Datei stehen)
Dim people$(10)
people$(0) = "Fred"
people$(1) = "Timo"
people$(2) = "Sara"
people$(3) = "Paul"
people$(4) = "Sara"
people$(5) = "Mary"
people$(6) = "Anna"
people$(7) = "Timo"
people$(8) = "Sara"
people$(9) = "Fred"

;-- Liste der unterschiedlichen Namen aufbauen und Personen mit gleichen Namen durchnummerieren
NewMap nameCount()

For k = 0 To 9
   name$ = people$(k)
   p = FindMapElement(nameCount(), name$)   ;*1
   If p = 0
      AddMapElement(nameCount(), name$)
   EndIf
   nameCount(name$) + 1                     ;*2
   Debug name$ + " #" + Str(nameCount())
Next

Der Code funktioniert genau wie erwartet, ich mache mir nur Gedanken über die Dauer. Meine Programme verarbeiten zig-tausende von Namen, und da spielt die Geschwindigkeit eine wichtige Rolle. Das ist ja einer der Gründe weshalb man Hash-Tables benutzt, weil die für solche Zwecke im Prinzip schnell sind.

Meine Sorge ist, dass in obigem Code der Hash-Table nameCount() 2x nach jedem Element durchsucht wird: einmal an der Stelle *1, und einmal an der Stelle *2. Stimmt das? Wenn nicht, bitte den folgenden Text ignorieren.

Oder kann man das Ergebnis von FindMapElement() (ein Pointer?) irgendwie weiterverwenden? Ich stelle mir sowas vor wie:

Code: Alles auswählen

p = FindMapElement(...)
If p <> 0
   SetCurrentMapElement(p)
EndIf

Dann wäre bis auf weiteres das gefundene Element auch das aktuelle, und der/die/das Map müsste nicht wieder neu durchsucht werden. Aber wie gesagt, vielleicht liege ich ja mit meinen Annahmen falsch ... Freak?

Und ist nach AddMapElement() das neu hinzugefügte Element automatisch das aktuelle?

Gruß, Little John

[ZeHa]

Meine Sorge ist, dass in obigem Code der Hash-Table nameCount() 2x nach jedem Element durchsucht wird: einmal an der Stelle *1, und einmal an der Stelle *2.

Ich glaube kaum, daß Fred so krank drauf ist

[Andesdaf]

Ich würde gerne noch das Projekt mit dem [X]-Schalter rechts
schließen, die Icons gefallen mir auch sehr gut und das Projektmanagement
sowiso.

[Little John]

Meine Sorge ist, dass in obigem Code der Hash-Table nameCount() 2x nach jedem Element durchsucht wird: einmal an der Stelle *1, und einmal an der Stelle *2.

Ich glaube kaum, daß Fred so krank drauf ist

Es ist immer wieder schön, solch "sachliche" Beiträge zu lesen.

Fest steht doch wohl:
Bei FindMapElement(nameCount(), name$) wird der/die/das Map durchsucht.
Bei nameCount(name$) + 1 allein wird der/die/das Map durchsucht.
"Weiß" PB tatsächlich dass nameCount() hier genau das Element verwenden soll, welches zuvor mit FindMapElement(nameCount()) gefunden wurde? Bzw. wie kann ich PB das mitteilen? Die Frage ist keineswegs abwegig, zumal die Funktionen der Map-Library noch nicht ausführlich dokumentiert ist.

Gruß, Little John

[Thorium]

Fest steht doch wohl:
Bei FindMapElement(nameCount(), name$) wird der/die/das Map durchsucht.
Bei nameCount(name$) + 1 allein wird der/die/das Map durchsucht.
"Weiß" PB tatsächlich dass nameCount() hier genau das Element verwenden soll, welches zuvor mit FindMapElement(nameCount()) gefunden wurde? Bzw. wie kann ich PB das mitteilen? Die Frage ist keineswegs abwegig, zumal die Funktionen der Map-Library noch nicht ausführlich dokumentiert ist.

http://en.wikipedia.org/wiki/Hash_table

Ne Hash Map ist ne Hash Table. Da wird im klassischen Sinne garnicht durchsucht. Da der Hash der direkte Arrayindex ist. Ein wenig durchsucht werden muss nur bei Hash-Kollisionen. Die dürften aber alle zusammengefasst sein.

Also desdo mehr Elemente du hast, desdo sinnvoller ist es die Hash Map zu nutzen, da es der Hash Map ziemlich egal ist wie viele Elemente sie hat. Das junkt die Performance nicht.

[Little John]

Ne Hash Map ist ne Hash Table. Da wird im klassischen Sinne garnicht durchsucht. Da der Hash der direkte Arrayindex ist.

Dazu muss der Hash-Wert zuvor erstmal berechnet werden ...

Ein wenig durchsucht werden muss nur bei Hash-Kollisionen.

Genau. Und bei sehr vielen Elementen muss evtl. auch etwas mehr durchsucht werden.

Es ist doch bekannt, dass unterschiedliche Implementierungen von Hash-Funktionen bzw. -tables z.T. deutlich unterschiedliche Performance zeigen. Wieso soll es hier nun egal sein, ob das Ganze doppelt gemacht wird oder nur einmal?

Gruß, Little John

[Thorium]

Es ist doch bekannt, dass unterschiedliche Implementierungen von Hash-Funktionen bzw. -tables z.T. deutlich unterschiedliche Performance zeigen. Wieso soll es hier nun egal sein, ob das Ganze doppelt gemacht wird oder nur einmal?

Gruß, Little John

Ja, ok, stimmt. Ich glaub ich hatte dich nicht ganz verstanden.

[ZeHa]

@ Little John, hatte das etwas falsch interpretiert, ich dachte Du wolltest wissen ob "jedes Element" durchsucht wird

[Little John]

@ Little John, hatte das etwas falsch interpretiert, ich dachte Du wolltest wissen ob "jedes Element" durchsucht wird

Ach so ... ja das wäre ziemlich "verrückt", bzw. nichts was man guten Gewissens als Hash-Table bezeichnen könnte.

Gruß, Little John

[freak]

Eine Map in PB hat ein "aktuelles Element", so wie eine LinkedList. In der Map ist es immer das letzte verwendete Element. Auf das aktuelle element wird so zugegriffen:

Code: Alles auswählen

Map("key") = 123 ; sucht nach "key" und legt ihn an wenn nicht gefunden (danach ist das das aktuelle Element) 
Map() = 321 ; ändert das aktuelle Element ohne erneutes hashing

In dem Beispiel hier würde man also einfach nach dem FindMapElement(nameCount(), name$) nur noch nameCount() benutzen um auf das gefundene Element zuzugreifen.