I've created a variable order Markov chain built on top of a tree, but I can't train on datasets >1MB worth of text without running out of memory. I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.

Below is the AddString method for variable order chains (of characters).

public void AddString(string s)
    // Construct the string that will be added.
    StringBuilder sb = new StringBuilder(s.Length + 2 * (MarkovOrder));

    sb.Append(StartChar, MarkovOrder);
    sb.Append(StopChar, MarkovOrder);

    for (int i = 0; i < sb.Length; ++i)
        // Get the order 0 node
        Node parent = root.AddChild(sb[i]);

        //add N-grams
        for (int j = 1; j <= MarkovOrder && j + i < sb.Length; j++)
            Node child = parent.AddChild(sb[j + i]);
            parent = child;

(code base found here)

This code bloats my memory with every order up to the defined order, and I'm not sure how I'd alter it to only store one order without it completely breaking down. I'd like to do something like

markov = new markovChain(order = 3);.

I've been playing around with algorithms that can store a chain of order (i.e.) 4 without going through the other orders. These implementations aren't performing as well, and I keep resorting to several lists that make node creation complex for me. (https://gist.github.com/mtbarta/8127895)

I'm not sure what structure to use so that I can generate a chain at a given order without bloating memory use. Can I implement a linked list that stores a list of following nodes? Does that ruin the point of a linked list while bloating my memory anyway?

  • \$\begingroup\$ Can you git a source files and/or startup code? \$\endgroup\$ Dec 27, 2013 at 11:26
  • \$\begingroup\$ I can't donload FairyTales.txt etc... \$\endgroup\$ Dec 27, 2013 at 11:34
  • \$\begingroup\$ I uploaded the training data files to github. Just throw them in your debug folder and the program will start. \$\endgroup\$
    – mtbarta
    Dec 27, 2013 at 23:49
  • \$\begingroup\$ Are you shure the code is not running? It runs almost perfectly and I really can't find breaking changes to debug \$\endgroup\$ Dec 30, 2013 at 6:58
  • 1
    \$\begingroup\$ It runs, but I'm wondering if it can be optimized since the tree stores every order. If I use a larger training file, I run out of memory. \$\endgroup\$
    – mtbarta
    Jan 1, 2014 at 19:11

1 Answer 1


I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.

Perhaps use the SortedList class instead of the Dictionary class.

For example, this blog entry says,

Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.

Other optimizations might include:

  • Don't allocate Node.Children until/unless the AddChild method is called.
  • Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
  • Add a KeyValuePair<char,Node> OnlyChild member to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child

Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment) might result in bigger savings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.