Re: Zeichen zaehlen
Bernd Eckenfels
> Wie sähe ein entsprechender Programmteil in einer rein
> funktionalen Sprache aus?
Statt dem Array global zu verwenden gibt deine Visitor Funktion einfach eine
Liste von Tupeln (codepoint,count) zurueck
Ich hab den Syntax nimmer im kopf aber im prinzip ist der einfachste ansatz
bei einem eingangsstrom immer das einfach rekursiv hinzushreiben, aus einer
Liste von Chars erstelle ich eine Liste von Tupels mit Char und Anzahl:
[char] -> [(char,int)]
Der einfachste fall, wenn die Liste aus einem c besteht ist einfach:
hist c = [(c,1)]
Wenn es mehr als eines ist dann uebergebe ich alle bis auf eine an mich
selbst, und ueber das ergebnis iteriere ich um den richtigen counter zu
erhoehen.
hist c:cs = addorincrement c hist cs
char -> [(char, int)] -> [(char, int)]
addorincrement newc (c,i) = newc==c?(c,i+1):[(newc,1),(c,i)]
Ist das neue Zeichen das selbe wie der übergebene Tuppel, dann gib den
Tuppel wieder zurueck mit dem zaehler erhoeht, sonst gib 2 Tupels zurueck,
mit der anzahl =1 fuer das neue Zeichen.
addorincrement newc (c,i):cs = newc==c?[(c,i+1),cs]:[(c,i),addorincrement newc cs]
Wenn das Zeichen das gleiche ist wie im ersten tupel, dann erhoehen wir es
und geben es zurueck. Sonst lassen wir das erste tupel unangetasstet und
machen mit dem rest weiter.
Gruss
Bernd
Bernd Eckenfels
> Ich hatte ja nun einige Milliarden Zeichen gezählt und frage
> mich, ob die funktionale Lösung dann nicht deutlich
> ineffizienter ist, da sie anscheinend für jedes Zeichen die
> Liste durchsucht und dabei ständig neue Listen konstruiert.
Es gibt auch Arrays in einigen Sprachen (z.B.
http://www.haskell.org/tutorial/arrays.html). Aber das Problem mit dem neu
erstellen (COW) hat man bei funktionalen Ansätzen immer (und die
Laufzeitumgebungen können das ganz gut optimieren).
Ich sehe grade man kann wohl sogar mit diesem Accumulation feature arbeiten
bei Haskell.
hist :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]
Aber das ist wohl ein Spezielfall.
Gruss
Bernd
Nils M Holm
> 192 16260102
> 137 16264455
> 202 16511251
> (...)
> 't' 134133571
> 'e' 180181881
> ' ' 344587770
>
> Wie sähe ein entsprechender Programmteil in einer rein
> funktionalen Sprache aus?
In Scheme etwa so:
(define (count-chars source)
(define *counts* (make-vector 256 0))
(define (count char)
(if (eof-object? char)
*counts*
(let ((i (char->integer char)))
(vector-set! *counts* i (+ 1 (vector-ref *counts* i)))
(count (read-char source)))))
(count (read-char source)))
Intern benutzt die Funktion zwar ein veraenderliches Object,
naemlich den Vektor *COUNT*, aber nach aussen ist die Prozedur
rein funktional: Input-port rein, Ergebnisvector raus.
Referentielle Transparenz bleibt vollstaendig erhalten.
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
Nils M Holm
> Ich hatte ja nun einige Milliarden Zeichen gezählt und frage
> mich, ob die funktionale Lösung dann nicht deutlich
> ineffizienter ist, da sie anscheinend für jedes Zeichen die
> Liste durchsucht und dabei ständig neue Listen konstruiert.
Wie Bernd schon schrieb, ist das Prinzip der Liste nicht
notwendigerweise mit Funktionaler Programmierung verbunden.
Funktionale Sprachen bieten durchaus auch andere Datenstrukturen
an, wie hash tables (die spaetestens interessant werden, wenn
Du Unicode-Zeichen zeahlen willst) und Arrays bzw. Vektoren.
Wichtig ist lediglich, dass der Einsatz solcher Datenstrukturen
hinter Abstraktionsbarrieren verborgen wird, um referentielle
Transparzen zu wahren.
> (Natürlich könnte sie ein sehr schlauer optimierender Compiler
> zu demselben Code übersetzen, wie ein C-Programm mit demselben
> Verhalten - aber so gut sind die Compiler wohl noch nicht.)
Es gibt *ziemlich* schlaue Compiler, z.B. STALIN, der in manchen
Faellen durchaus Code erzeugt, der C schlaegt. Das mag daran
liegen, dass die semantische Analyse funktionaler Programme
leichter ist und umfassender durchgefuehrt werden kann als die
von C-Code.
Georg Bauhaus
> Stefan Ram <r...@zedat.fu-berlin.de> wrote:
>> Ich hatte ja nun einige Milliarden Zeichen gezählt und frage
>> mich, ob die funktionale Lösung dann nicht deutlich
>> ineffizienter ist, da sie anscheinend für jedes Zeichen die
>> Liste durchsucht und dabei ständig neue Listen konstruiert.
>
> Wie Bernd schon schrieb, ist das Prinzip der Liste nicht
> notwendigerweise mit Funktionaler Programmierung verbunden.
> Funktionale Sprachen bieten durchaus auch andere Datenstrukturen
> an, wie hash tables (die spaetestens interessant werden, wenn
> Du Unicode-Zeichen zeahlen willst) und Arrays bzw. Vektoren.
> Wichtig ist lediglich, dass der Einsatz solcher Datenstrukturen
> hinter Abstraktionsbarrieren verborgen wird, um referentielle
> Transparzen zu wahren.
Da wedelt ein Wald von Händen.
Entweder ist eine *Sprache* referentiell transparent,
heißt: außer I und O gibt es nirgendwo in allem Quellcode
Veränderliche, oder nicht. Scheme, als Sprache, ist nicht
referentiell transparent.
Haskell ist eine imperative Programmier-Sprache,
dank der Monade, vgl. wörtlich in Peyton Jones' Büchlein
(... the finest imperative language ...).
Eine C-Funktion, die referentiell transparent genutzt
werden kann, macht aus C noch keine *rein* *funktionale*
Sprache.
Abstraktionsbarrieren sind gut. Machen aber noch keine
referentiell transparente Sprache, weil sie nicht zur
Sprache gehören.
Wer in einer funktionalen Sprache rein funktional
arbeiten will, dem fehlt eben die operationale
Semantik. Zwangsläufig, sofern die Operationen
nicht bis in die Ausführungsebene hinein deklariert
werden können.
Ergo, [1 .. n] ist ein sehr einfacher Haskell-Ausdruck,
dessen Laufzeitverhalten katastrophal sein kann, aber
nicht muss - man weiß es eben nicht, denn hier liegt
referentielle Transparenz vor.
Nils M Holm
> Entweder ist eine *Sprache* referentiell transparent,
> heißt: außer I und O gibt es nirgendwo in allem Quellcode
> Veränderliche, oder nicht. Scheme, als Sprache, ist nicht
> referentiell transparent.
Der mir bekannten Definition nach ist eine *Funktion*
referentiell transparent, wenn ich ihre Anwendung mit
denselben Parametern stets durch das entsprechende
Ergebnis ersetzen kann.
In Scheme (beispielsweise) kann ich Prozeduren schreiben,
die referentiell transparent sind und solche, die es nicht
sind.
Ich weiss nicht, was daran "Haendewedeln" sein soll.
Georg Bauhaus
> Georg Bauhaus <rm.dash...@futureapps.de> wrote:
>> Entweder ist eine *Sprache* referentiell transparent,
>> heißt: außer I und O gibt es nirgendwo in allem Quellcode
>> Veränderliche, oder nicht. Scheme, als Sprache, ist nicht
>> referentiell transparent.
>
> Der mir bekannten Definition nach ist eine *Funktion*
> referentiell transparent, wenn ich ihre Anwendung mit
> denselben Parametern stets durch das entsprechende
> Ergebnis ersetzen kann.
Ja. Schon.
> In Scheme (beispielsweise) kann ich Prozeduren schreiben,
> die referentiell transparent sind und solche, die es nicht
> sind.
>
> Ich weiss nicht, was daran "Haendewedeln" sein soll.
Das rhetorische Leugnen von set! :-)
Scheme ist keine rein funktionale Sprache.
Eine C-funktion kann referentiell transparent sein.
Ist C deswegen eine rein funktionale Sprache?
Es verwäscht die Trennlinie zwischen den Begriffen,
wenn die Besprechung von Algorithmen einerseit
die Zuweisung an Variable einschließt, andererseits
aber eine rein funktionale Sprache in Rede stand,
in der es nun mal keine Zuweisung gibt. Vielleicht
is Ablenkungsmanöver ein besseres Wort als
Händewedeln.
Nils M Holm
> Scheme ist keine rein funktionale Sprache.
> Eine C-funktion kann referentiell transparent sein.
> Ist C deswegen eine rein funktionale Sprache?
Zitiere bitte die Stelle, an der ich behauptet habe,
dass Scheme als Sprache "referentiell transparent"
oder "rein funktional" sei.
Zu Deiner Beruhigung fasse ich also zusammen:
- Scheme ist *keine* "rein funktionale" Sprache.
- Du kannst in vielen nicht-"rein funktionalen"
Sprachen funktional programmieren; das macht
diese Sprachen nicht zu funktionalen Sprachen.
Jedoch:
- Meine Beispiel-Prozedur benutzt VECTOR-SET! als
einziges nicht-funktionales Konstrukt. Deswegen
und auf Grund der *von meiner Prozedur gewahrten*
referentiellen Transparenz halte ich es fuer ein
akzeptables Beispiel.
Eine rein funktionale Loesung waere in der Tat
diese hier, die aber, wie Stefan zurecht vermutet,
ineffektiv ist, weil UPDATE jedesmal die liste
durchsuchen muesste:
(define (count-chars source)
(define (update char counters)
(cond ((null? counters)
`((,char 1)))
((char=? char (caar counters))
`((,char ,(+ 1 (cadar counters))) ,@(cdr counters)))
(else
(cons (car counters)
(update char (cdr counters))))))
(define (count char counters)
(if (eof-object? char)
counters
(count (read-char)
(update char counters))))
(count (read-char) '()))
Natuerlich laesst sich der Suchaufwand mit geeigneten
Strukturen minimieren, es bleibt aber das Problem, dass
beim Update einer unveraenderlichen Datenstruktur immer
Daten kopiert werden muessen, was die Prozedur ausbremst.
Daher meine -- zugegebenermassen nicht rein funktionale
-- Verwendung eines Vektors.
Zufrieden?
Lutz Donnerhacke
> Wie sähe ein entsprechender Programmteil in einer rein
> funktionalen Sprache aus?
Verschiedene Herangehensweisen:
1. Sortieren, Gruppieren und Zählen
histogram = map (\xs -> (head xs, length xs)) . group . sort
2. Häufigkeiten akkumulieren
http://www.haskell.org/ghc/docs/latest/html/libraries/base/GHC-Arr.html#v%3AaccumArray
historgram = assocs . accumArray (+) 0 ('\0', '\255') . map ((,) 1)
Martin Neitzel
>public static void countFile
>( final java.io.BufferedInputStream bufferedInputStream )
>{ for( boolean looping = true; looping; )
> { final int octet = bufferedInputStream.read();
> if( octet == -1 )looping = false; else ++count[ octet ]; }}}
>
> Wie sähe ein entsprechender Programmteil in einer rein
> funktionalen Sprache aus?
(#;{.)/.~ @ (1!:0)
Martin Neitzel
Nils M Holm
Georg Bauhaus
> Stefan Ram wrote:
>> public static void countFile
>> ( final java.io.BufferedInputStream bufferedInputStream )
>> { for( boolean looping = true; looping; )
>> { final int octet = bufferedInputStream.read();
>> if( octet == -1 )looping = false; else ++count[ octet ]; }}}
>>
>> funktionalen Sprache aus?
>
> (#;{.)/.~ @ (1!:0)
>
Wie effizient macht J das denn im Vergleich?
Georg Bauhaus
> Daher meine -- zugegebenermassen nicht rein funktionale
> -- Verwendung eines Vektors.
>
> Zufrieden?
>
Viel besser. :)
Martin Neitzel
>> (#;{.)/.~ @ (1!:0)
> Wie effizient macht J das denn im Vergleich?
Keine Ahnung -- ich kann kein Java ;-). Wenn mir jemand erzaehlt,
welchen Java-Interpreter/Compiler ich am besten auf meinen 486er
mit 48MB RAM und FreeBSD-4.7 packe, dann kann ich ja mal den Java-
Code tumb reinfallen lassen und vergleichend messen.
Das Klassifizieren (mittles "/.") ist in der gaengigen J-Implementierung
Hash-basiert, und die Aktion #;{. ("Anzahl nebst 1. Element")
bekommt als Idiom noch einmal eine Sonderbehandlung.
Das "1!:0" war uebrigens falsch aus dem Handgelenk geschuettelt,
es haette ein "1!:1" sein muessen; das ist ein buffered-fileread
wie es das Java-Original hatte. Wenn Effizienz das Ziel ist, dass
waere ein mmapped file besser, aber nicht so huebsch funktional.
(Das File wird dabei auf einen Variablennamen gemapped.)
Martin Neitzel
Georg Bauhaus
> nei...@marshlabs.gaertner.de (Martin Neitzel) writes:
>> Keine Ahnung -- ich kann kein Java ;-). Wenn mir jemand erzaehlt,
>> welchen Java-Interpreter/Compiler ich am besten auf meinen 486er
>> mit 48MB RAM und FreeBSD-4.7 packe, dann kann ich ja mal den Java-
>> Code tumb reinfallen lassen und vergleichend messen.
>
>
> http://www.purl.org/stefan_ram/java/DirectoryCharCount.java
Das sollte mit 48MB RAM auf Unices auskommen:
#include <stdio.h>
#include <stdbool.h>
long count[ 256 ];
bool countFile(FILE* bufferedInputStream )
{
if (bufferedInputStream) {
for(bool looping = true; looping; )
{
int octet = fgetc(bufferedInputStream);
if( octet == EOF )looping = false;
else ++count[ octet ];
}
}
else {
fprintf(stderr, "file pointer is %p\n", (void*) bufferedInputStream);
}
return true;
}
int main()
{
/* Zählen. */
countFile(stdin);
/* Bericht. */
for(int k = 0; k < 256; ++k)
printf("%d: %ld\n", k, count[ k ]);
printf("%s\n", "Done");
return 0;
}