Die Programmiersprache Ruby

Blog|

Forum|

Wiki  


Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]

Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: CachingHash-Pattern
BeitragVerfasst: 28 Sep 2010, 02:30 
Offline
Böser Admin 2
Benutzeravatar

Registriert: 17 Mär 2004, 17:03
Beiträge: 2544
Wohnort: Berlin
Meine Lieblingsfunktion von Hashes ist die new-Methode mit Block. Damit kann man in 3 Zeilen einen Cache erzeugen:



1
2
3
cache = Hash.new do |hash, key|
hash[key] = expensive_calculation(key)
end


Ich schätze, das Muster ist vielen bekannt. Die Frage ist, warum so kompliziert?



1
2
3
cache = Hash.cache do |key|
expensive_calculation(key)
end


So eine Version wäre obendrein schneller, da nur ein Argument in den Block übergeben werden muss (das macht einen ziemlichen Unterschied nach meiner Erfahrung).

Gibt es das schon? Wäre das ein RCR wert?

Und: Kommt das in Zucker 6? ;)

_________________
Ruby-Mine | (almost) murphy.de | rubychan.de


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 28 Sep 2010, 09:01 
Offline
Rubyist
Benutzeravatar

Registriert: 04 Jun 2008, 22:03
Beiträge: 394
Gibt es das schon?
: soweit ich weis nicht
Wäre das ein RCR wert?
: ich denke ja
Kommt das in Zucker 6? ;)
: warum nicht? xD wobei ich es lieber hätte das in C als in Ruby zu programieren


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 28 Sep 2010, 12:09 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
Die Zeitgeschichte wäre bei teuren Berechnungen wohl eher nebensächlich, aber Sinn würde so etwas schon machen.

Ich frage mich allerdings, ob nicht eine Klasse Cache, die von Hash abgeleitet ist, noch besser wäre. Da könnten dann auch Methoden wie Cache#refresh rein - diese Methode gehört meiner Meinung nach dazu.

Wie gross aber die Möglichkeit ist, einen diesbezüglichen RCR durchzubekommen ist, wage ich nicht abzuschätzen - einfacher und leichter geht das mit einem RCR bezüglich Hash.cache bestimmt (dann fehlte mir aber noch so etwas wie Hash#reinitialize, was dem oben genannten Cache#refresh entsprechen würde).

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 28 Sep 2010, 12:17 
Offline
Böser Admin 2
Benutzeravatar

Registriert: 17 Mär 2004, 17:03
Beiträge: 2544
Wohnort: Berlin
#refresh wäre doch einfach mit #clear zu erreichen, oder?

_________________
Ruby-Mine | (almost) murphy.de | rubychan.de


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 28 Sep 2010, 14:59 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
Ja - ich war in Gedanken bei einer Klasse Cache, zu der aber noch mehr gehören würde.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 08:51 
Offline
Rubyist
Benutzeravatar

Registriert: 04 Jun 2008, 22:03
Beiträge: 394
man könnte auch lustiger weise die new bzw die init überladen xD

wenn der übergebene block mehr als 1 paramether will (|hash,key|)
verhalte dich normal.
will der block aber nur einen (|key|) dann nutz den neuen code
(das könnt ich heute sogar in c basteln :P)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 11:18 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
Ich finds eher schlecht, sowas an Hash zu tackern, zumal Hashes eh schlechte Datenstrukturen sind, wenn man sowas im großen Stil betreibt.

Da finde ich Charles Nutters Vorschlag[1], memoisierende Methoden im Core effizient zu unterstützen eher von Kernrelevanz.

Gruß,
Skade

[1]: grad kein Bock, core zu durchsuchen, daher kein link.


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 12:40 
Offline
Böser Admin 2
Benutzeravatar

Registriert: 17 Mär 2004, 17:03
Beiträge: 2544
Wohnort: Berlin
Skade hat geschrieben:
zumal Hashes eh schlechte Datenstrukturen sind, wenn man sowas im großen Stil betreibt.
Warum? Hash hat garantiertes O(1) fetch...

_________________
Ruby-Mine | (almost) murphy.de | rubychan.de


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 13:56 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
Also abgesehen davon, dass Hashes nur ein amortisiertes O(1) haben, sind verschiedenste Baumimplementierungen u.U. trotzdem schneller, weil die Vergleiche manchmal schneller funktionieren als (hash(obj)) und der retrieval.

Generelle Aussagen lassen sich da natürlich schwer treffen, da das alles vom Tuning der Hashtable und dem exakten Einsatzzweck abhängt. Wenn du nur so 8 Werte hast, wird das unter Umständen nicht ins Gewicht fallen, aber eventuell ist da auch eine Memomethode noch schneller.

http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/ bietet übrigens einen interessanten Überblick.

Insofern fände ich ein caching-Mixin für Dictionaries wie den Hash interessanter, egal, wie die Implementierung dahinter aussieht (die in Ruby nunmal eine Hashmap ist, deren Parameter schwer tunebar sind).

Gruß,
Skade


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 14:15 
Offline
Böser Admin 2
Benutzeravatar

Registriert: 17 Mär 2004, 17:03
Beiträge: 2544
Wohnort: Berlin
Laut http://rhg.rubyforge.org/chapter03.html ist es echts O(1). Aber darum geht's hier gar nicht.

Hash.cache oder Hash.new(1) wäre deutlich flexibler als ein Methoden-Caching - nicht immer ist das, was man cachen will, eine Methode. Und es wäre sehr viel einfacher in Ruby einzufügen.

@Hanmac: Ich bin nicht sicher, ob man Blöcke nach Parameterzahl überladen sollte…gibt es für so etwas Präzendenzfälle in Ruby?

_________________
Ruby-Mine | (almost) murphy.de | rubychan.de


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 16:25 
Offline
Interpreter

Registriert: 15 Mär 2005, 19:26
Beiträge: 6142
Wohnort: Karlsruhe
Ein Problem gibt es mit Hash-Codes natürlich immer. Wenn durch die Daten oder durch zu vollen Hash-Space extrem viele Konfliktbehandlungen erforderlich werden, geht das in die Richtung einer linearen Suche.

Abgesehen davon würde mir für einen Cache-Typ noch etwas fehlen. Das wäre eine Grössenangabe in der Form, dass die maximale Anzahl der zu cachenden Elemente angegeben werden kann. Dazu würde natürlich auch ein anzugebendes Verfahren gehören, welches die als nächstes zu löschenden Einträge ermittelt.

Wenn die anfallende Datenmenge klein ist, aber der Berechnungsaufwand gross, dürfte eine weitere Optimierung eher selten nötig sein, weil der Gewinn schon gross ist. Sollte es trotzdem Performance-Probleme beim Zugriff geben, frage ich mich, ob dann eine Implementierung der speziellen Funktionalität in C nicht angebrachter wäre.

_________________
WoNáDo.set_state!(:retired)


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 16:25 
Offline
Interpreter
Benutzeravatar

Registriert: 21 Mai 2007, 11:30
Beiträge: 1283
Wohnort: Thüringen
Naja, Rubyhashs sind auch von der Hashfunktion abhängig. Wenn ich die Stringklasse überschreibe und ihr die Hashfunktion "def hash(); return 0; end" gebe, dann dürfte die Laufzeit eines String-Hashs in den Keller gehen.

Muss aber Hashs verteidigen. In den meisten Fällen sind sie sehr effizient. Zumindest wenn man weiß wie viele Elemente man in sie einfügen will und wenn diese Elemente eine konstant-komplexe Hashfunktion haben (also ich nicht gerade Strings oder Arrays als Schlüssel verwende. In Ruby werden z.B. gerade deswegen meistens Symbole als Keys verwendet).
Und gerade in Ruby stelle ich mir Binary-Trees aufwendiger vor, weil hier eine Menge Overhead durch den Aufruf der Vergleichsmethoden entsteht (die ja als Rubymethoden realisiert sein müssten).

@Skade: Meinst du sowas?


1
2
3
4
5
6
class MeineKlasse
cache
def eine_methode()
eine_berechnung()
end
end


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 29 Sep 2010, 19:00 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
Mein Punkt war jetzt weniger, ob jetzt Hashes schlecht oder gut sind: sie sind (genauso wie binary trees) sehr speziell. Es gibt in Ruby ja auch alternative Map-Implementierungen wie z.B. rbtree, die durchaus effizient arbeiten, gerade bei großen Datenmengen. Ich find einfach die Fixierung von Ruby auf die Hash-Klasse, weil sie nunmal ein Literal und eine Core-Klasse hat eher unpraktisch.

Deswegen ist mir mein Nachsatz wichtiger: ich fänd es angenehmer, wenn es sowas als Mixin gäbe, genauso, wie ich "Map" als Mixin eigentlich garnicht so schlecht fände.

Memomethoden: klassisch so:



1
2
3
4
5
6
def foo
a = somelongoperation # token von nem Fremdrechner holen oder so
singleton_class.define_method(:foo) do
a
end
end


Das Problem an dem Code ist, dass die Effizienz davon sehr vom Interpreter abhängt (unter Ruby 1.8.7 zum Beispiel ist define_method langsamer als eval...). Daher gab es den Vorschlag, MemoMethoden im Core zu implementieren, damit jeder Interpreter das selbst implementieren kann.

Gruß,
Skade


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 01 Okt 2010, 01:04 
Offline
Böser Admin 2
Benutzeravatar

Registriert: 17 Mär 2004, 17:03
Beiträge: 2544
Wohnort: Berlin
Mmh ich sehe schon, das ist komplizierter...aber ich würde schon bei Rubys Hashs bleiben, denn damit kennen die Leute sich aus.

Skade hat geschrieben:
unter Ruby 1.8.7 zum Beispiel ist define_method langsamer als eval...
Wow, wusste ich gar nicht! Wieso denn das? Gruselig.

_________________
Ruby-Mine | (almost) murphy.de | rubychan.de


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: CachingHash-Pattern
BeitragVerfasst: 01 Okt 2010, 02:00 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
Die Leute kennen sich mit RubyHashs genauso gut aus, wie sie sich in Java mit dem Unterschied zwischen einer ArrayList und einer LinkedList auskennen. Mappt irgendwas auf irgendwas bzw. kettet irgendwas aneinander. Ich sehe da nur das Problem, dass die Überfrachtung der Hash-Klasse mit Funktionalität dazu führt, dass andere, eventuell besser geeignete Klassen lieber beiseite geschoben werden.

define_method ist meines Wissens langsamer, weil es in Ruby 1.8 einen Methodenknoten (im AST) generiert, die als einzige Aktion den Procaufruf ausführt. Procaufrufe in 1.8 sind zwar fix, aber Methodenaufrufe schneller. Das liegt ca. im Bereich von 50%. Wir reden allerdings über wirklich kleine Zeiten (Millionen Methodenaufrufe sinnerhalb einer Sekunde sind kein Problem). Ich weiss nicht genau, wie das Problem bei Ruby 1.9 liegt, auf jeden Fall sollte es nicht mehr so stark ausgeprägt sein.


Nach oben
 Profil  
 
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach: