Donald Knuth on Machine Learning and the Meaning of Life

https://thenewstack.io/donald-knuth-on-machine-lea...

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...

#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.

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 :)

#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

#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!

#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?

#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.

#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.