Isn't this linear in the size of the vocabulary for every token you want to generate?
Fast Markov chains in ~20 lines of sh, grep, cut and Awk
21–30 of 42 posts
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#22Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#23This is awesome because it is a real shell script that does something interesting AND it's well documented. I'm bookmarking this as a bash script reference.
Not being pedantic, but OP's script isn't Bash, it's POSIX sh. POSIX sh can be executed in Bash, but there are several differences. The only non-POSIX command I can spot in that script is shuf.
Which makes it a valid reference for bash.
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#24Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#25The best read for something like this is The Practice of Programming which is a great little book to have in general. This link to a sample chapter covers the entire analysis and creation of a markov chain program, none of which require many lines of code. https://ptgmedia.pearsoncmg.com/images/9780201615869/samplep... One thing I've noticed from playing with these types of programs is the number of words to use as a…
I also recommend everyone read PoP.
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#26Earlier quoted context omitted.
grep is from AT&T Unix version 6. awk is from AT&T Unix version 7. Bash is from Gnu but the script is actually plain old Bourne Shell from AT&T Unix version 7.
`shuf` is not POSIX, so that would make this BASH.
It wouldn't necessarily make it Bash. That would mean using actual Bash features. It's still non-portable sh, because it relies on an extra program being available, but it isn't relying on Bash itself - none of expansions or so on.
This is what makes it Bash:
file="${1:-~/.mrkdb}"
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#27Earlier quoted context omitted.
Not being pedantic, but OP's script isn't Bash, it's POSIX sh. POSIX sh can be executed in Bash, but there are several differences. The only non-POSIX command I can spot in that script is shuf.
Which makes it a valid reference for bash.
That's like saying a well-written C program is a good reference for C++. In any case, writing POSIX-only shell scripts is much harder than writing Bash scripts, which can often be much faster (e.g., one can use {1..10}, which doesn't need an external call, instead of `seq 1 10` to iterate through a list of numbers). For POSIX-only shell scripts, the ones used in Git [1] are some of the best-written I've seen.
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#28I like this, it is sensible and goes against the status quo.
The usual thought is shell scripts are hacky and you need an ostensibly more powerful language like Python or Perl.
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#29In case of huge enough models it possibly can be made even faster using look (binary search), instead of grep... It is better in O terms, with maybe some large constant factor due to file seeking...
Re: Fast Markov chains in ~20 lines of sh, grep, cut and Awk
#30The best read for something like this is The Practice of Programming which is a great little book to have in general. This link to a sample chapter covers the entire analysis and creation of a markov chain program, none of which require many lines of code. https://ptgmedia.pearsoncmg.com/images/9780201615869/samplep... One thing I've noticed from playing with these types of programs is the number of words to use as a…
The question of how many words are used is discussed here: https://en.wikipedia.org/wiki/N-gram#n-gram_models See also https://en.wikipedia.org/wiki/Google_Ngram_Viewer which recently popularized the term n-gram.
> which recently popularized the term n-gram.
Eh? It's well known in Info Retrieval; it goes back at least to Salton's IR group at Cornell in the 1970's.