<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Alex Woods on Medium]]></title>
        <description><![CDATA[Stories by Alex Woods on Medium]]></description>
        <link>https://medium.com/@alexhwoods?source=rss-4976141c4872------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*Y2Q115wzxBrIUuUI.jpeg</url>
            <title>Stories by Alex Woods on Medium</title>
            <link>https://medium.com/@alexhwoods?source=rss-4976141c4872------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 08:38:02 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@alexhwoods/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Inline Functions in Kotlin]]></title>
            <link>https://medium.com/@alexhwoods/inline-functions-in-kotlin-23f56544b39a?source=rss-4976141c4872------2</link>
            <guid isPermaLink="false">https://medium.com/p/23f56544b39a</guid>
            <category><![CDATA[kotlin]]></category>
            <dc:creator><![CDATA[Alex Woods]]></dc:creator>
            <pubDate>Mon, 27 Jan 2020 15:05:45 GMT</pubDate>
            <atom:updated>2020-01-27T15:05:45.073Z</atom:updated>
            <content:encoded><![CDATA[<p>Originally posted on <a href="https://www.atomiccommits.io/inline-functions/">Atomic Commits</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*r10qCYxiVMcL--kN1KDYIA.jpeg" /></figure><p>Do you remember when you first started programming, and instead of breaking repeated code into a function, you copied and pasted it anywhere you needed? That’s what the compiler does with an inline function.</p><p>The compiler <strong>inlines</strong> the function and any lambdas passed to it, meaning it takes the function’s bytecode and pastes it directly at the call site.</p><pre>inline fun &lt;T&gt; log(name: String, action: () -&gt; T) {<br>    println(&quot;Before $name&quot;)<br>    action.invoke()<br>    println(&quot;After $name&quot;)<br>}<br><br>log(&quot;foo&quot;) { println(&quot;foo&quot;) }<br><br>// compiler generates<br>println(&quot;Before foo&quot;)<br>println(&quot;foo&quot;)<br>println(&quot;After foo&quot;)</pre><h3>When should you use an inline function?</h3><h4>Performance</h4><p>We use inline functions every time we use a collection operation. I’m talking about map, filter, etc. This is great news since it allows us to use <a href="https://en.wikipedia.org/wiki/Higher-order_function">higher order functions</a> at no cost—enabling clean and fast functional programming.</p><pre>val newList = listOf(1, 2, 3, 4).map { it * 2 }<br><br>// compiles to<br>val temp: MutableList&lt;Int&gt; = mutableListOf()<br>for (x in listOf(1, 2, 3, 4)) {<br>	temp.add(x * 2)<br>}<br><br>val newList = temp.toList()</pre><h3>Why does inlining gain performance?</h3><p>To understand why inlining functions can increase performance, we have to understand what Kotlin does when we don’t inline a function:</p><ul><li>It jumps to a different place in memory, to get the function’s code.</li><li>If the function contains a lambda argument, an extra object is created to hold all of its information.</li></ul><p>Therefore when we inline a function, we avoid a memory jump, and if there’s a lambda argument, we avoid extra object creation. In general this is not game changing, but for functions like map, forEach, and filter, which are heavily used and take lambda function arguments, inlining is a valuable feature.</p><h3>Non-local returns</h3><p>Speaking of the collection operations: have you noticed you can return from them?</p><pre>fun findIndex(value: String, list: List&lt;String&gt;): Int? {<br>    list.forEachIndexed { index, item -&gt;<br>        if (item == value) return index<br>    }<br><br>    return null<br>}</pre><p>Try that from a normal function, the compiler won’t allow it.</p><pre>fun bar(): Int {<br>    normalFunction {<br>        return 5   // `return` is not allowed here!<br>    }<br>}</pre><p>In the first example, because the compiler is inlining the code, in terms of return, it&#39;s as if the function call wasn&#39;t there. return goes back to the nearest fun declaration, and with inline functions, the compiler has stripped that away.</p><h3>Reified Type Parameters</h3><p>Sometimes, functions using generics need type information. For example, the collection function filterIsInstance.</p><pre>abstract class Animal(name: String)<br><br>data class Dog(val name: String): Animal(name)<br>data class Cat(val name: String): Animal(name)<br><br>val pets: List&lt;Animal&gt; = listOf(Cat(&quot;Cleatus&quot;), Cat(&quot;Jim&quot;), Dog(&quot;Morgana&quot;))<br><br>pets.filterIsInstance&lt;Dog&gt;()  // [Dog(name=Morgana)]</pre><p>Because the function is inlined, we don’t have to do any reflection. We can use the type operators is and as. The filterIsInstance function is a simple extension function on Iterable that does just that.</p><pre>inline fun &lt;reified T&gt; kotlin.collections.Iterable&lt;*&gt;.filterIsInstance(): List&lt;T&gt; {<br>    val newList = mutableListOf&lt;T&gt;()<br><br>    this.forEach { if (it is T) newList.add(it) }<br><br>    return newList.toList()<br>}</pre><h4>Why doesn’t type erasure apply to inlined functions?</h4><p>Because the compiler is inlining the function’s bytecode, it knows the <em>actual type</em> used as an argument. When the compiler pastes the code, there is no notion of generics. It’s using a real type — the type is used at that particular call site. A type we can access and get information about.</p><p>This is significantly different behaviour than a normal function. It’s so different that it allows us to gather type information, even in the presence of type erasure.</p><h3>Limitations of inline functions</h3><p>You might ask — why not make every function inline?</p><p>It’s easy to abuse inline functions. If we create a large inline function, or an inline function that calls an inline function, our code can quickly balloon in size. When in doubt, think about what the compiler is doing–are you comfortable with it pasting the code at every call site? Are you content losing the stack-trace if you need to debug? If not, use a regular function.</p><p>Furthermore, inline functions cannot use elements with a more restrictive visibility [4]. Your inline function might be pasted to a class in another module, where that private class it’s using won’t be accessible.</p><p>Lastly, inline functions can’t be recursive. Think about what the compiler would do if it encountered one.</p><p>Inline functions are a simple tool to increase performance, but they should only be used at the right time.</p><h3>Sources</h3><ol><li><a href="https://kotlinlang.org/docs/reference/inline-functions.html">Kotlin documentation</a></li><li><a href="https://stackoverflow.com/questions/45949584/how-does-the-reified-keyword-in-kotlin-work">How does reified keyword in Kotlin work?</a></li><li><a href="https://www.reddit.com/r/Kotlin/comments/59dh54/inlining_generated_code_explanation/">Inlining Generated Code Explanation</a></li><li><a href="https://leanpub.com/effectivekotlin">Effective Kotlin</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=23f56544b39a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How similar is the execution of Java and JavaScript?]]></title>
            <link>https://medium.com/@alexhwoods/how-similar-is-the-execution-of-java-and-javascript-73ec2fd8fe62?source=rss-4976141c4872------2</link>
            <guid isPermaLink="false">https://medium.com/p/73ec2fd8fe62</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[v8-engine]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Alex Woods]]></dc:creator>
            <pubDate>Tue, 06 Aug 2019 23:25:09 GMT</pubDate>
            <atom:updated>2019-08-06T23:25:09.638Z</atom:updated>
            <content:encoded><![CDATA[<p>April 14, 2019</p><p>In this article, I will compare the execution of Java and JavaScript. I am intentionally avoiding a lot of details about memory, as that is a whole other topic.</p><h3>Execution at the processor level</h3><p>With each passing clock cycle, the processor executes a single microinstruction. These are strings whose bits drive the control lines of the CPU. We get a series of microinstructions by the translation of an instruction (frequently called machine code). The set of all available instructions for a processor is called the Instruction Set Architecture (ISA), which in a sense is the API of your computer’s processor.</p><p>source code -&gt; instructions (now within processor) -&gt; microinstructions (executed each clock cycle)</p><p>Statements in a program can be taken by a compiler and turned into machine code (instructions). The <a href="https://jvns.ca/blog/2014/09/06/how-to-read-an-executable/">best example</a> of this is C. Different processors, however, provide different Instruction Set Architectures. Does this mean we have to write a different compiler for each processor? (Yes, it does.) This is a problem as compiler’s do more and more work for the programmer.</p><p>We can solve this by keeping all the added features in our program executor the same, except for the processor. If we virtualize the processor, and provide an ISA specially designed for the execution of the language in question, we now have a component we can take in and out, as we move from one OS to another (presumably with different processors).</p><h3>Virtualizing the processor</h3><p>As alluded to above, both the languages in question (Java and JavaScript), provide an abstraction on top of machine code in order manage this complexity. This “abstraction of machine code” is called bytecode. In Java, <a href="https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html">it is the .class files</a>, and with JavaScript it varies depending on the engine in question. To see the bytecode used by the V8 engine (the one used in Node.js and Chrome), execute it with the --print-bytecode flag.</p><blockquote><em>To run a JavaScript program purely with V8 (excluding Node’s runtime), install V8 and run </em><em>v8 hello.js (where </em><em>hello.js is your program) <br> e.g. </em><em>v8 --print-bytecode hello.js (Because seeing the bytecode of Node&#39;s runtime isn&#39;t the best for education purposes).</em></blockquote><p>When I say “virtualizing the processor”, what I mean is that we are executing the program in a virtual machine. We have some entity (either the JVM interpreter or the Ignition bytecode executor), that knows how to execute their version of bytecode. What we are using here is called a <a href="https://en.wikipedia.org/wiki/Virtual_machine#Process_virtual_machines">process virtual machine</a>. This is in stark contrast to a <a href="https://en.wikipedia.org/wiki/Virtual_machine#System_virtual_machines">system virtual machine</a>, which has its own guest operating system (think VMWare). A process virtual machine is much lighter, and its sole purpose is executing a program. To be clear, it does further virtualize other things, such as memory, which means there exists a mapping. For simplicity, the <a href="http://www.ittc.ku.edu/~kulkarni/teaching/EECS768/slides/chapter3.pdf">mapping is just a direct mapping</a>. Note that memory is already virtualized on the host OS; the memory blocks given to a process appear continuous, but are not guaranteed to be so. The most complicated thing we are abstracting away is the processor and it’s machine code.</p><p>In the JVM, for example, the interpreter takes a line of bytecode, and knows how to execute it without providing further translation into machine code.</p><p>In V8, the Ignition interpreter acts in a similar way. it takes a statement from the parsed <a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree">AST</a>, turns it into bytecode, and executes it by itself.</p><p>Let’s dive deeper into the details of the two.</p><h3>How the JVM Executes Programs</h3><p>Let’s say we have some Java source code. We use the Java compiler (javac) to turn it into bytecode (.class files). Then we feed it into the JVM.</p><p>The JVM takes it, and after some initialization steps (class loading, bytecode verifying, etc.), a statement of bytecode arrives at the interpreter, which executes it.</p><p>As execution continues, if some piece of code (e.g. a function) has been executed a certain number of times (i.e. it is “hot”), the JVM execution engine contains a JIT optimizing compiler which will turn it into machine code, allowing it to execute faster.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/531/0*sWdWVqUxqtAeNa1g.png" /></figure><blockquote><em>Note that the “JIT compiler” in this case goes from bytecode to machine code. JavaScript’s JIT compiling, in contrast, goes from source code to bytecode.</em></blockquote><h3>How the V8 Engine Executes Programs</h3><p>In contrast, JavaScript is JIT compiled. That means there is no pre-compilation step before it is fed into the execution engine; we feed the engine raw source code.</p><p>Say, we have some JavaScript source code. It is parsed and turned into an AST. That is then fed into Ignition, V8’s interpreter. <a href="https://v8.dev/docs/ignition">Ignition</a> turns that into bytecode, and executes it.</p><p>Just like before, if we discover a hot function, we have an optimizing compiler to turn that into machine code. In V8, this entity is called <a href="https://v8.dev/docs/turbofan">TurboFan</a>.</p><p>Going to steal Franziska Hinkelmann’s picture, from her great <a href="https://medium.com/dailyjs/understanding-v8s-bytecode-317d46c94775">blog post</a> on the topic.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*YP2ypjsKlz3nFwyl.png" /></figure><p>Note — Above I talked about process virtual machines. V8 is pretty sparse on those kind of internal details, but I did read enough to convince myself that they use a process virtual machine. (See <a href="https://codeburst.io/node-js-v8-internals-an-illustrative-primer-83766e983bf6">here</a>, <a href="https://v8.dev/blog/turbofan-jit">here</a>, and <a href="https://docs.google.com/presentation/d/1chhN90uB8yPaIhx_h2M3lPyxPgdPmkADqSNAoXYQiVE/edit#slide=id.g1ba7f92079_2_0">here</a>).</p><h3>Similarities Between Java and JavaScript Execution</h3><ul><li>Both are run inside process virtual machines. They both have their own “bytecode”, which is just an abstraction of machine code. Those process virtual machines execute their corresponding bytecode.</li><li>They both take the same approach for code that is “hot”. That is, an optimizing compiler turns the bytecode into machine code, using profiling information accumulated throughout execution.</li></ul><h3>Differences Between Java and JavaScript Execution</h3><p>There is one major difference here-JavaScript is JIT compiled, Java is not. Due to this, there’s no abstraction in between the JavaScript language and it’s execution engine (V8, in this case). That means it’s impossible to use V8 to execute another language.</p><p>The JVM, on the other hand, only knows about .class file bytecode. This gives space for other language that can compile to .class files. Enter Scala, Groovy, Clojure, and Kotlin.</p><p>It’s ironic because this layer of abstraction only exists because there was a necessity to send bytecode over the network, around the time Java came out (early World Wide Web days, when Java was supported in the browser). Nowadays, this doesn’t matter <em>at all</em>. These days we send JavaScript source code over the network, and the browser uses an execution engine (like V8) to execute it.</p><p>I find this point fascinating, and I believe this indirection might lead to the JVM sticking around for a very long time, because we can choose to use it even if we don’t want to use Java. It’s appealing for language designers, because over half the work is done for them-all they have to do is design a language spec and a compiler to .class bytecode.</p><h3>Conclusion</h3><p>After researching and writing this, my opinion is now that the way that JVM languages and JavaScript are executed is much closer than I originally imagined. Hope ya learned something.</p><p><em>Originally published at </em><a href="https://www.alexhwoods.com/how-similar-is-the-execution-of-java-and-javascript"><em>https://www.alexhwoods.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=73ec2fd8fe62" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Data Structures and Database Indexes]]></title>
            <link>https://medium.com/@alexhwoods/data-structures-and-database-indexes-a552cf3ba2c5?source=rss-4976141c4872------2</link>
            <guid isPermaLink="false">https://medium.com/p/a552cf3ba2c5</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Alex Woods]]></dc:creator>
            <pubDate>Fri, 21 Jun 2019 14:13:54 GMT</pubDate>
            <atom:updated>2019-06-21T14:13:54.661Z</atom:updated>
            <content:encoded><![CDATA[<p>A database index is an extra data structure in a storage engine w/ the goal of faster retrieval. It’s not the primary storing entity for the data, and it has to be maintained on writes.</p><h3>Hash Index</h3><p>The simplest type of index. The keys are whatever column the index is built on, and the value is the location of the data on disk — this prevents us for having to scan for the values.</p><p>Hash indexes work well for simple equality (select * from table_name where id = 4;). They don’t work for range queries (select * from table_name where id &gt; 4 and where id &lt; 16;), due to the nature of a hash map (hash functions are by no means sequential).</p><p>Hash indexes are stored in memory (in RAM), and so if the database crashes, they’re wiped out and have to be rebuilt.</p><p>Note that putting and getting from a hash table is <em>O(1)</em> in most cases (as in, when a hash collision doesn’t occur), so this type of index is extremely fast, and works well for it’s limited set of use cases (equality!). Note that hash collisions are minimized when sufficient memory is allocated to the hashmap.</p><h3>B-Tree Index</h3><p>This is the most common type of index. In fact, when you use create index in Postgres, it creates a B-Tree index by default.</p><p>B-Trees keep the key-value pairs sorted in order by key, which allows for great performance on range queries.</p><p>A B-Tree is made up of pages, with page size <em>P</em>, each of which has <em>b</em>possible references to child pages. We call <em>b</em> the <strong>branching factor</strong>. If a page has d children, then it is storing <em>d-1</em> keys, and <em>d &lt;= b</em>.</p><p>When dealing with the data structure (as opposed to the database index), you will often hear “pages” referred to as nodes. They’re the same thing, just different contexts.</p><h3>Maintaining Balance</h3><p>The key properties of a B-Tree are the following:</p><ul><li>Each node can store <em>b-1</em> keys, where <em>b</em> is the <strong>branching factor</strong>. This is in contrast to something like a <a href="https://en.wikipedia.org/wiki/Splay_tree">splay tree</a>, where each node stores only a single value.</li><li>It is always balanced. Insert and delete operations, if they put the tree out of balance, are followed by some balancing operation. (A splay tree acts the same in this regard).</li></ul><p>For the following example, we’ll be dealing with 2–4 trees, which are a B-Tree, with a branching factor of 4. Meaning, a node can have a maximum of 4 children, and a maximum of 3 values.</p><h3>Overflow</h3><p>When a node overflows (the # of keys allowed has been exceeded upon an insertion), we split the node.</p><p>e.g. If a node has keys [1,2,3,4], it has overflowed. Therefore, we must split it.</p><p>We do this by promoting one of the keys in the middle to the parent, and making children out of the keys on the left and right of the value promoted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/661/1*uERC-mM1YjDrUQ7shawShw.png" /><figcaption>Overflow results in splitting</figcaption></figure><p>One challenge for implementers is that overflow can propagate — if we overflow a leaf node, then we split it, and promote a key, that can cause overflow on the parent node, which we will then further have to split. This can (and should) be solved recursively, but it is nonetheless a challenge.</p><h3>Underflow</h3><p>Upon deletion of a value, we can have a node that has no values. We have two cases — transfer and fusion. When a node has a sibling node with at least 2 values, then we can perform transfer.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/701/1*KfiPewsbbeYmNUpKvja_-A.png" /><figcaption>Underflow, able to transfer</figcaption></figure><p>In the case where there isn’t such a sibling, and transferring would just propagate the underflow to the sibling, we use fusion — the combining of two nodes. We combine the empty node with its sibling, and also move a value from parent into that node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*3Zge49_92L5UQoYqYeNi0A.png" /><figcaption>Underflow, have to use fusion</figcaption></figure><p><a href="https://www.cs.usfca.edu/~galles/visualization/BTree.html">This website</a> has a fantastic visualization of how it works. The main thing to take away about the structure is that it is always balanced, and so when we go to search for a key-value pair, it is worst case <em>O(logn)</em>.</p><h3>Storage Capacity</h3><p>B-Tree indexes, unlike hashmap indexes, are usually maintained on disk. This is because we usually keep a large page size. When a B-Tree has a large page size and branching factor, it has a very high storage capacity.</p><p>storage capacity = (b^n) * P</p><p>Where <em>n</em> is the length of the tree, <em>b</em> is the branching factor, and <em>P</em> is the page size. e.g.</p><p>500^4 * 4KB = 250TB (example from [1]).</p><h3>Sources</h3><p>[1] <a href="https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321">Designing Data Intensive Applications</a></p><p>[2] <a href="https://www.postgresql.org/docs/">Postgres documentation</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a552cf3ba2c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Generating Text Using a Markov Model]]></title>
            <link>https://medium.com/@alexhwoods/generating-text-using-a-markov-model-bc7648b4de6e?source=rss-4976141c4872------2</link>
            <guid isPermaLink="false">https://medium.com/p/bc7648b4de6e</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[nlp]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Alex Woods]]></dc:creator>
            <pubDate>Wed, 05 Aug 2015 02:17:19 GMT</pubDate>
            <atom:updated>2015-08-05T02:17:19.283Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/414/0*Z5X2-J0baP-bMaD7.jpg" /></figure><p>A Markov Chain is a random process, where we assume the previous state(s) hold sufficient predictive power in predicting the next state. Unlike flipping a coin, these events are dependent. It’s easier to understand through an example.</p><p>Imagine the weather can only be rainy or sunny. That is, the <strong>state space</strong> is rainy or sunny. We can represent our Markov model as a <strong>transition matrix</strong>, with each row being a state, and each column being the probability it moves to another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/125/0*-OU7RgLRzlAHapzV.png" /></figure><p>However, it’s easier to understand with this state transition diagram.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/0*k7pmUzcHAeCl5MCH.png" /></figure><p>In other words, given today is sunny, there is a .9 probability that tomorrow will be sunny, and a .1 probability that tomorrow will be rainy.</p><h2>Text Generator</h2><p>One cool application of this is a language model, in which we predict the next word based on the current word(s). If we just predict based on the last word, it is a first-order Markov model. If we use the last two words, it’s a second-order Markov model.</p><p>In my example I trained the model using Walden by Henry Thoreau. I also included files of Thus Spoke Zarathustra by Nietszche , and some speeches by Obama to make it easy to experiment. The cool thing about this is that whatever text you train it on, the model spits out really similar text.</p><p>First we have to import NLTK, the best NLP library in Python. I would say the natural language processing we’re doing here to be pretty mild, but their built in functions save me a lot of code. We then turn the string (taken from the text file) into an array using the split() function.</p><pre>import nltk<br>import random</pre><pre>file = open(&#39;Text/Walden.txt&#39;, &#39;r&#39;)<br>walden = file.read()<br>walden = walden.split()</pre><p>These two functions are the meat of the code. The Conditional Frequency Dictionary from NLTK that we are going to eventually use has to take the array as pairs. So the phrase “Hi my name is Alex” would becomes [(“Hi”, “my”), (“my, “name”), (“name”, “is”), (“is”, “Alex”)]. The makePairs function takes in an array (a string split by word) and outputs an array in the above format.</p><p>The generate method takes in a conditional frequency distribution. Think — how many times did each word appear after ‘farm’? That is what a conditional frequency distribution outputs (for all words, not just ‘farm’). The rest of the generate function does is output text based on the distribution observed in the training data. I did this by making an array with each word that appeared after the current word. The array also has the correct counts, so then I can just randomly pick a word from the array and the distribution will be obeyed.</p><pre>def makePairs(arr):<br>    pairs = []<br>    for i in range(len(arr)):<br>        if i &lt; len(arr)-1: <br>            temp = (arr[i], arr[i+1])<br>            pairs.append(temp)<br>    return pairs</pre><pre>def generate(cfd, word = &#39;the&#39;, num = 50):<br>    for i in range(num):<br>        arr = []                 # make an array with the words shown by proper count<br>        for j in cfd[word]:<br>            for k in range(cfd[word][j]):<br>                arr.append(j)<br>        <br>        print(word, end=&#39; &#39;)<br>        word = arr[int((len(arr))*random.random())]</pre><p>With these final three lines, we output some text, that looks a lot like Walden.</p><pre>pairs = makePairs(walden)<br>cfd = nltk.ConditionalFreqDist(pairs)<br>generate(cfd)</pre><p><em>the question, perhaps from the leisure fruitful. “But,” says pertinently that sound asleep thus. Yet his gentle rain while to choose. If he was nearly level, and wisely; as he sprang upon the entrance of goldenrod (Solidago stricta) grows a half-hour’s nap after practising various animals of some cheerful it</em></p><p>I encourage you to look at the iPython notebook on my <a href="https://github.com/alexhwoods/alexhwoods.com/tree/master/Machine%20Learning/Markov%20Chains">github</a>, since I continued to make a method where all you have to do is enter a file name, and it will output generated text. The Obama example is also pretty cool.</p><p>If you want to try this yourself, just make a text file and put it in the correct directory.</p><p>P.S. You’ll noticed I put Hal from 2001 A Space Odyssey in the beginning of the article. That’s because there is a conversation simulator called <a href="https://megahal.alioth.debian.org/">megaHAL</a> that uses Markov Models!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bc7648b4de6e" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>