mboost-dp1

Donald Knuth on Machine Learning and the Meaning of Life


Gå til bund
Gravatar #2 - larsp
22. okt. 2021 08:35
Gode gamle Knuth.

Det minder mig om den famøse word count affære, hvor Knuth løste opgaven at finde de n hyppigst forekommende ord i en tekst ved at skrive et omstændigt (og smukt?) 10 siders program. En gut ved navn McIlroy svarede tilbage spydigt med en kort shell kommando pipeline konstruktion der løste samme opgave.

McIlroy:
The simple pipeline given above will suffice to get answers right now, not next week or next month. It could well be enough to finish the job. But even for a production project, say for the Library of Congress, it would make a handsome down payment, useful for testing the value of the answers and for smoking out follow-on questions.

Knuth has shown us here how to program intelligibly, but not wisely. I buy the discipline. I do not buy the result. He has fashioned a sort of industrial-strength Fabergé egg—intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start.

Fra: http://www.leancrew.com/all-this/2011/12/more-shel...
Gravatar #3 - arne_v
22. okt. 2021 13:43
#2

Der er en god pointe i at løse en opgave så simpelt som muligt.

Men kritikken her virker lidt malplaceret.


so he asked Donald Knuth to write a program in that style as a guest column and Doug McIlroy to write a literary-style critique of it.

Literate programming is an interesting topic in its own right. The idea, which originated with Knuth, is to write a program and its documentation at the same time, interleaved with each other. It’s not just writing good comments or including docstrings or using systems like POD. In literate programming, the code is subservient to the documentation. For example, the various sections of the code are written not in the order the compiler (or interpreter) wants them, but in the order most appropriate for the explanation.


Så Knuth fik en hel præcis opgave - at tælle de ord med brug af literary-style (og løse opgaven fra bunden af).

Og McIlroys script løser ikke den stillede opgave - hans script tæller ord men ikke literary-style (og ved at genbruge noget eksisterende funktionalitet fremfor selv at kode det).

Knuth kunne uden tvivl godt have lavet en anden løsning hvis han var blevet stillet en anden opgave - at tælle de ord med færrest mulige linier). Men han havde nok afslået opgaven - kryptiske shell-scripts er uden for hans interesse-område.
Gravatar #4 - larsp
24. okt. 2021 09:13
arne_v (3) skrev:
Så Knuth fik en hel præcis opgave - at tælle de ord med brug af literary-style (og løse opgaven fra bunden af).

Og McIlroys script løser ikke den stillede opgave

Ja, det er ikke fair direkte at sammenligne de to løsninger.

Her er en codegolf challenge om problemet: https://codegolf.stackexchange.com/questions/18813... Rust tager føringen :)
Gravatar #5 - arne_v
16. nov. 2021 02:32
#4

Der er mange snørklede løsninger der.

Det burde være en simpel opgave.

Pseudo kode:


for each line in file with name arg[0] {
for each word in line with word break defined by regex [^a-z] {
count[word]++
}
}
for first arg[2] elements of reverse sort of count by value {
print result
}


Det kræver:
* regex split
* map/dictionary/associativt array
* builtin sortering

Men det har de fleste nyere sprog.

Og egenskaberne er OK.

O(n) i fil størrelse
O(n*logn) i antal distinkte ord

Java:


import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.regex.Pattern;

public class TextFun {
private static final Pattern w = Pattern.compile("[^a-z]+");
public static void main(String[] args) throws IOException {
Map<String, Integer> count = new HashMap<String, Integer>();
Files.lines(Paths.get(args[0])).forEach(line -> {
Arrays.stream(w.split(line.toLowerCase())).forEach(word -> {
if(word.length() > 0) count.put(word, count.getOrDefault(word, 0) + 1);
});
});
count.entrySet().stream().sorted((e1,e2) -> e2.getValue() - e1.getValue()).limit(Integer.parseInt(args[1])).forEach(e -> {
System.out.printf("%s : %d\n", e.getKey(), e.getValue());
});
}
}


C#:


using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

namespace TextFun
{
public static class MissingStuff
{
public static T2 GetOrDefault<T1,T2>(this IDictionary<T1,T2> dic, T1 key, T2 defval)
{
if(dic.ContainsKey(key))
{
return dic[key];
}
else
{
return defval;
}
}
}
public class Program
{
private static Regex w = new Regex("[^a-z]+", RegexOptions.Compiled);
public static void Main(string[] args)
{
IDictionary<string, int> count = new Dictionary<string, int>();
foreach(string line in File.ReadAllLines(args[0]))
{
foreach(string word in w.Split(line.ToLower()))
{
if(word.Length > 0)
{
count[word] = count.GetOrDefault(word, 0) + 1;
}
}
}
foreach(KeyValuePair<string, int> kvp in count.OrderByDescending(e => e.Value).Take(int.Parse(args[1])))
{
Console.WriteLine("{0} : {1}", kvp.Key, kvp.Value);
}
}
}
}


Python:


import sys
import re

count = {}
for line in open(sys.argv[1], 'rt', encoding='utf-8'):
for word in re.split('[^a-z]+', line.lower()):
if len(word) > 0:
count[word] = count.get(word, 0) + 1
for e in sorted(count.items(), key=lambda itm:itm[1], reverse=True)[0:int(sys.argv[2])]:
print('%s : %d' % (e[0],e[1]))


Indrømmet - C version i linket er over dobbelt så hurtig som ovenstående Java kode. Men C koden er altså også over 200 linier kode som ikke er helt overskueligt - og med en forudsætning om at hele filen kan være i hukommelsen.

Rust koden er 150 linier og fejler ved default command line oversættelse.

C:\Work>rustc u.rs

C:\Work>u ulysses64.txt 10
thread 'main' panicked at 'attempt to subtract with overflow', u.rs:95:31
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Gravatar #6 - arne_v
16. nov. 2021 13:52
#5


og med en forudsætning om at hele filen kan være i hukommelsen.


og med en forudsætning om at fil størrelsen i bytes kan være i en long

og med en forudsætning om at fseek til EOF og ftell vil fortælle hvor mange bytes der læses ved mode "rb" (hvilket ret eksplicit siges ikke at være tilfældet i C standarden)

og det sidste problem vil ikke blev ordentligt fanget, da koden ikke bruger retur værdien fra fread omkring hvor meget der faktisk er læst

og en omskrivning til support af UTF-8 vil være en omfattende ændring

Ikke god kode!

Gravatar #7 - larsp
17. nov. 2021 18:46
#6 Ja, og unicode er elefanten i rummet ingen taler om i denne opgave. Hvis opgaven skulle udføres med faktisk tekst in real life tror jeg unicode processering, f.eks. at lave lower case, vil tage en betydelig del af tiden, og så er det måske andre sprog der ender med at tage føringen.

Gad vide hvilke sprog der har de hurtigste UTF-8 engines derude? Eller bruger alle programmerne mon de samme OS libraries i sidste ende?
Gravatar #8 - arne_v
18. nov. 2021 00:49
#7

Java, C# og Python koden virker med Unicode bare regex justeres til hvad der skal skille ord. De bruger en Unicode aware tolower funktion.

C og Rust koden bruger ASCII specifikke hacks for at være hurtige.

Gravatar #9 - arne_v
18. nov. 2021 01:18
#7

Jeg ved ikke hvad de forskellige sprog til encode og decode.

Et forsigtigt g;t vil v;re at store sprog bruger noget egen kode mens mindre sprog bare bruger libiconv.
Gå til top

Opret dig som bruger i dag

Det er gratis, og du binder dig ikke til noget.

Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.

Opret Bruger Login