ACHTUNG. Das ist ein Archiv des alten forum.ruby-portal.de. Die aktuelle Mailingliste gibt es auf lists.ruby-lang.org/pipermail/ruby-de.

NOTICE. This is a ready-only copy of the old forum.ruby-portal.de. You can find the current mailing list at lists.ruby-lang.org/pipermail/ruby-de.

Die Programmiersprache Ruby

Blog|

Forum|

Wiki  


Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]

Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Haskell Frage
BeitragVerfasst: 24 Jun 2012, 10:47 
Offline
Nuby

Registriert: 24 Jun 2012, 10:41
Beiträge: 1
Hallo an alle,
hoffe es kennt sich hier der eine oder andere mit Haskell aus. Im Haskell Forum ist leider sehr wenig los, deswegen hoffe ich mal dass ich hier evtl. richtig bin.
würde gerne wissen welche Möglichkeiten es gibt eine DataMap zu sortieren. In eine DataMap speichere ich als Keys Strings.
Diese sollen auf eine bestimmte Art lexikografisch sortiert werden. Erst Kleinbuchstaben und bei gleichem Wort, soll
das Wort mit dem größeren Buchstaben zu erst stehen. Ich verwende DataMaps, da mir gesagt wurde, dass diese auf Grund ihrer Veränderlichkeit
eine bessere Performance als Listen besitzen. Nur weiß ich nicht wie ich die vorgebebene Sortierstruktur brechen kann und eine eigene
implementieren kann. Habe schon irgendwo gelesen dass ich sie in eine Liste umformen könnte und dann diese sortieren könnte. Bringt aber finde ich nicht wirklich was da ich dann a) wieder das Performance Problem habe und b) die Liste dann eh nicht wieder in dieser Reihenfolge als DataMap abspeichern kann da dann immer wieder die vorgelegte Reihenfolge von DataMap verwendet wird.
Irgendwelche Ideen was ich machen könnte?


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Haskell Frage
BeitragVerfasst: 24 Jun 2012, 23:19 
Offline
Interpreter
Benutzeravatar

Registriert: 03 Jul 2006, 14:53
Beiträge: 4872
Wohnort: RLP
Hi, hier findet sich sicher einer, der sich deiner Frage annimmt. Eine kurze Sache dennoch vorweg:

Hast du das Performanceproblem konkret oder hast du nur mal davon gehört? Wenn ja, kannst du ein Beispiel posten, dass dieses Problem offenbart?

An sich sind Listen schon effizient, wenn die Reihenfolge eben das wichtigste Merkmal ist. Meines Wissens sind auch Data.Map-Typen in Haskell nicht "veränderbar", aber da kann ich mich irren. Maps sind halt schneller, wenn du schnellen Lookup von Einzelelementen brauchst, Listen sind schneller, wenn du häufig über die gesamte Liste iterieren musst (da dir die Reihenfolge wichtig ist, gehe ich mal davon aus, dass das der Fall ist). Dafür sind Listen halt langsamer, wenn du darin suchen musst. Bei sortierten Listen kannst du allerdings auch an dieser Stelle mit ein paar Tricks ne ganze Menge sparen.

Insofern ist die Frage, ob das eine besser oder das andere schlechter ist, wahrscheinlich schwer zu beantworten, vor allem da Data.Map ja eine ganze Menge Funktionen anbietet, um aus assoziativen Listen Maps zu erstellen und umgekehrt wieder Listen. Als ersten Schritt wäre es wahrscheinlich sinnvoll, einfach mal das zu wählen, was man für den jeweiligen Einsatzzweck am häufigsten braucht und ansonsten zur Not in den anderen Typ zu konvertieren. Wenn man dann ein echtes Problem damit kriegt, kann man an der Stelle weiteroptimieren. Versteck das Ganze am besten hinter einen guten Interface.

Gruß,
Skade


Nach oben
 Profil  
 
 Betreff des Beitrags: Re: Haskell Frage
BeitragVerfasst: 25 Jun 2012, 02:11 
Offline
Nuby

Registriert: 13 Jan 2012, 21:43
Beiträge: 2
sharufa hat geschrieben:
Ich verwende DataMaps, da mir gesagt wurde, dass diese auf Grund ihrer Veränderlichkeit
eine bessere Performance als Listen besitzen.

Nur zur Klarstellung - ich nehme mal an, du willst sagen, dass du nachträglich neue Elemente hinzufügen oder entfernen willst? Ja, dann ist die Liste keine gute Wahl, denn diese Operationen wären damit schlimmstenfalls O(n).

Um die Sortierreihenfolge zu verändern, brauchst du eine andere Ord-Instanz für deinen Key. Da du den von String (noch) nicht überschreiben kannst, heißt das, dass du den Key-Typ ändern musst. Das ist nicht wirklich kompliziert:


1
2
3
4
newtype MyString = MyString { fromMyString :: String }
deriving (Eq, Show)
instance Ord MyString
(MyString s1) `compare` (MyString s2) = ...


Durch Verwendung von newtype wird das Ganze zu einem reinen Compile-Time-Konstrukt, dieser Wrapper kostet dich also nichts in Sachen Performance. Mit deriving kannst du so viele Instanzen übernehmen, wie du unverändert behalten möchtest.

Die interessantere Frage ist, ob du jetzt die Bilbiotheks-Funktionen so verpackst, dass sie jeweils String nach MyString konvertieren - oder ob du gleich überall MyString verwenden solltest. Ich würde zu letzterem raten :)


Nach oben
 Profil  
 
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 3 Gäste


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: