4
\$\begingroup\$

This is a simple real state based markov chain (I'm using real states instead of a markov matrix to enable making an animated version later).

My goal was to make the markov chain as generic and reusable as possible, while practicing using smart pointers.

What general coding style, performance, semantic, or functional improvements could I make?

#pragma once
#include <memory>
#include <list>
#include <vector>
#include <iostream>

template <typename T>
class State;

template <typename T>
struct Transition {
    std::shared_ptr<State<T>> nextState;
    int rawCount;
    float weight;
    Transition(std::shared_ptr<State<T>> nextState);
};

template <typename T>
class State {
    std::list<Transition<T>> transitions;

public:
    T data;
    float startWeight;
    int rawStartCount;

    State(T data);
    void addTransitionEvent(std::shared_ptr<State<T>> nextState);
    void calculateTransitionWeights();
    std::shared_ptr<State<T>> getNextState(float randomValue);
};

template <typename T>
class MarkovChain {
    std::vector<std::shared_ptr<State<T>>> states;
    std::shared_ptr<State<T>> currentState;

public:
    MarkovChain();
    void addData(T data, bool isStartData = false);
    void calculateWeights();
    void setStartState(float randomValue);
    T getDataAndAdvance(float randomValue);


};

template <typename T>
Transition<T>::Transition(std::shared_ptr<State<T>> nextState) {
    weight = 0;
    rawCount = 0;
    this->nextState = nextState;
}

template <typename T>
State<T>::State(T data) {
    rawStartCount = 0;
    startWeight = 0;
    this->data = data;
}

template <typename T>
void State<T>::addTransitionEvent(std::shared_ptr<State<T> > nextState) {
    bool tansitionAlreadyExists = false;
    for (auto&& transition : transitions) {
        if (nextState->data == transition.nextState->data) {
            transition.rawCount++;
            tansitionAlreadyExists = true;
            break;
        }
    }
    if (!tansitionAlreadyExists) {

        transitions.push_back(Transition<T>(nextState));
        transitions.back().rawCount++;

    }
}

template <typename T>
void State<T>::calculateTransitionWeights() {
    int weightCounter = 0;
    for(auto&& transition : transitions) {
        weightCounter += transition.rawCount;
    }
    for(auto&& transition : transitions) {
        if (!weightCounter) {
            std::cout << "No Counter Values!" <<std::endl;
            weightCounter = 1;
        }
        transition.weight = float(transition.rawCount) / float(weightCounter);
    }

}

template <typename T>
std::shared_ptr<State<T>> State<T>::getNextState(float randomValue) {
    float value = randomValue;
    for(auto&& transition : transitions) {
        value -= transition.weight;
        if (value >= 0.01) {
            return transition.nextState;
        }
    }
    return transitions.front().nextState;//This should never get called
    std::cout <<"\nError\n";
}

template <typename T>
MarkovChain<T>::MarkovChain() {
    currentState = std::shared_ptr<State<T>>(nullptr);
}

template <typename T>
void MarkovChain<T>::addData(T data, bool isStartData) {
    if (states.size()==0) {
        auto newState = std::make_shared<State<T>>(data);
        currentState = newState;
        newState->rawStartCount++;
        states.push_back(newState);
    } else {
        bool stateAlreadyExists = false;
        std::shared_ptr<State<T>> newState(nullptr);
        for (auto&& state: states) {
            if (state->data == data) {
                newState = state;
                stateAlreadyExists = true;
                break;
            }
        }
        if (!stateAlreadyExists) {
            newState = std::make_shared<State<T>>(data);
            states.push_back(newState);
        }
        currentState->addTransitionEvent(newState);
        currentState = newState;
        if (isStartData) {
            newState->rawStartCount++;
        }

    }
}

template <typename T>
void MarkovChain<T>::calculateWeights() {
    int startWeightCounter = 0;
    for (auto&& state: states) {
        startWeightCounter += state->rawStartCount;
        state->calculateTransitionWeights();
    }
    for (auto&& state: states) {
        state->startWeight = float(state->rawStartCount) / float(startWeightCounter);
    }
}

template <typename T>
void MarkovChain<T>::setStartState(float randomValue) {
    float value = randomValue;
    for (auto&&state :  states) {
        value -= state->startWeight;
        if (value > 0.01 ) {
            currentState = state;
        }
    }
}

template <typename T>
T MarkovChain<T>::getDataAndAdvance(float randomValue) {
    T currentData = currentState->data;
    currentState = currentState->getNextState(randomValue);
    return currentData;
}

Sample main()

#include <iostream>
#include <array>
#include <cstdlib>
#include <ctime>
#include <string>
#include "MarkovChain.hpp"
#include "MarkovChain.cpp"

int main(int argc, const char * argv[]) {

    srand (static_cast <unsigned> (time(0)));


    MarkovChain<std::string> chain;

    std::array<std::string, 4481> numbers {"the", "awful", "german", "language", "a", "little", "learning", "makes", "the", "whole", "world", "kin—proverbs", "xxxii", "7", "i", "went", "often", "to", "look", "at", "the", "collection", "of", "curiosities", "in", "heidelberg", "castle", "and", "one", "day", "i", "surprised", "the", "keeper", "of", "it", "with", "my", "german", "i", "spoke", "entirely", "in", "that", "language", "he", "was", "greatly", "interested", "and", "after", "i", "had", "talked", "a", "while", "he", "said", "my", "german", "was", "very", "rare", "possibly", "a", "unique", "and", "wanted", "to", "add", "it", "to", "his", "museum", "if", "he", "had", "known", "what", "it", "had", "cost", "me", "to", "acquire", "my", "art", "he", "would", "also", "have", "known", "that", "it", "would", "break", "any", "collector", "to", "buy", "it", "harris", "and", "i", "had", "been", "hard", "at", "work", "on", "our", "german", "during", "several", "weeks", "at", "that", "time", "and", "although", "we", "had", "made", "good", "progress", "it", "had", "been", "accomplished", "under", "great", "difficulty", "and", "annoyance", "for", "three", "of", "our", "teachers", "had", "died", "in", "the", "meantime", "a", "person", "who", "has", "not", "studied", "german", "can", "form", "no", "idea", "of", "what", "a", "perplexing", "language", "it", "is", "surely", "there", "is", "not", "another", "language", "that", "is", "so", "slipshod", "and", "systemless", "and", "so", "slippery", "and", "elusive", "to", "the", "grasp", "one", "is", "washed", "about", "in", "it", "hither", "and", "hither", "in", "the", "most", "helpless", "way", "and", "when", "at", "last", "he", "thinks", "he", "has", "captured", "a", "rule", "which", "offers", "firm", "ground", "to", "take", "a", "rest", "on", "amid", "the", "general", "rage", "and", "turmoil", "of", "the", "ten", "parts", "of", "speech", "he", "turns", "over", "the", "page", "and", "reads", "let", "the", "pupil", "make", "careful", "note", "of", "the", "following", "exceptions", "he", "runs", "his", "eye", "down", "and", "finds", "that", "there", "are", "more", "exceptions", "to", "the", "rule", "than", "instances", "of", "it", "so", "overboard", "he", "goes", "again", "to", "hunt", "for", "another", "ararat", "and", "find", "another", "quicksand", "such", "has", "been", "and", "continues", "to", "be", "my", "experience", "every", "time", "i", "think", "i", "have", "got", "one", "of", "these", "four", "confusing", "cases", "where", "i", "am", "master", "of", "it", "a", "seemingly", "insignificant", "preposition", "intrudes", "itself", "into", "my", "sentence", "clothed", "with", "an", "awful", "and", "unsuspected", "power", "and", "crumbles", "the", "ground", "from", "under", "me", "for", "instance", "my", "book", "inquires", "after", "a", "certain", "bird—it", "is", "always", "inquiring", "after", "things", "which", "are", "of", "no", "sort", "of", "consequence", "to", "anybody", "where", "is", "the", "bird", "now", "the", "answer", "to", "this", "question—according", "to", "the", "book—is", "that", "the", "bird", "is", "waiting", "in", "the", "blacksmith", "shop", "on", "account", "of", "the", "rain", "of", "course", "no", "bird", "would", "do", "that", "but", "then", "you", "must", "stick", "to", "the", "book", "very", "well", "i", "begin", "to", "cipher", "out", "the", "german", "for", "that", "answer", "i", "begin", "at", "the", "wrong", "end", "necessarily", "for", "that", "is", "the", "german", "idea", "i", "say", "to", "myself", "regen", "rain", "is", "masculine—or", "maybe", "it", "is", "feminine—or", "possibly", "neuter—it", "is", "too", "much", "trouble", "to", "look", "now", "therefore", "it", "is", "either", "der", "the", "regen", "or", "die", "the", "regen", "or", "das", "the", "regen", "according", "to", "which", "gender", "it", "may", "turn", "out", "to", "be", "when", "i", "look", "in", "the", "interest", "of", "science", "i", "will", "cipher", "it", "out", "on", "the", "hypothesis", "that", "it", "is", "masculine", "very", "well—then", "the", "rain", "is", "der", "regen", "if", "it", "is", "simply", "in", "the", "quiescent", "state", "of", "being", "mentioned", "without", "enlargement", "or", "discussion—nominative", "case", "but", "if", "this", "rain", "is", "lying", "around", "in", "a", "kind", "of", "a", "general", "way", "on", "the", "ground", "it", "is", "then", "definitely", "located", "it", "is", "doing", "something—that", "is", "resting", "which", "is", "one", "of", "the", "german", "grammars", "ideas", "of", "doing", "something", "and", "this", "throws", "the", "rain", "into", "the", "dative", "case", "and", "makes", "it", "dem", "regen", "however", "this", "rain", "is", "not", "resting", "but", "is", "doing", "something", "actively—it", "is", "falling—to", "interfere", "with", "the", "bird", "likely—and", "this", "indicates", "movement", "which", "has", "the", "effect", "of", "sliding", "it", "into", "the", "accusative", "case", "and", "changing", "dem", "regen", "into", "den", "regen", "having", "completed", "the", "grammatical", "horoscope", "of", "this", "matter", "i", "answer", "up", "confidently", "and", "state", "in", "german", "that", "the", "bird", "is", "staying", "in", "the", "blacksmith", "shop", "wegen", "on", "account", "of", "den", "regen", "then", "the", "teacher", "lets", "me", "softly", "down", "with", "the", "remark", "that", "whenever", "the", "word", "wegen", "drops", "into", "a", "sentence", "it", "always", "throws", "that", "subject", "into", "the", "genitive", "case", "regardless", "of", "consequences—and", "that", "therefore", "this", "bird", "staid", "in", "the", "blacksmith", "shop", "wegen", "des", "regens", "n", "b", "i", "was", "informed", "later", "by", "a", "higher", "authority", "that", "there", "was", "an", "exception", "which", "permits", "one", "to", "say", "wegen", "den", "regen", "in", "certain", "peculiar", "and", "complex", "circumstances", "but", "that", "this", "exception", "is", "not", "extended", "to", "anything", "but", "rain", "there", "are", "ten", "parts", "of", "speech", "and", "they", "are", "all", "troublesome", "an", "average", "sentence", "in", "a", "german", "newspaper", "is", "a", "sublime", "and", "impressive", "curiosity", "it", "occupies", "a", "quarter", "of", "a", "column", "it", "contains", "all", "the", "tenparts", "of", "speech—not", "in", "regular", "order", "but", "mixed", "it", "is", "built", "mainly", "of", "compound", "words", "constructed", "by", "the", "writer", "on", "the", "spot", "and", "not", "to", "be", "found", "in", "any", "dictionary—six", "or", "seven", "words", "compacted", "into", "one", "without", "joint", "or", "seam—that", "is", "without", "hyphens", "it", "treats", "of", "fourteen", "or", "fifteen", "different", "subjects", "each", "enclosed", "in", "a", "parenthesis", "of", "its", "own", "with", "here", "and", "there", "extra", "parentheses", "which", "reenclose", "three", "or", "four", "of", "the", "minor", "parentheses", "making", "pens", "within", "pens", "finally", "all", "the", "parentheses", "and", "reparentheses", "are", "massed", "together", "between", "a", "couple", "of", "kingparentheses", "one", "of", "which", "is", "placed", "in", "the", "first", "line", "of", "the", "majestic", "sentence", "and", "the", "other", "in", "the", "middle", "of", "the", "last", "line", "of", "it—after", "which", "comes", "the", "verb", "and", "you", "find", "out", "for", "the", "first", "time", "what", "the", "man", "has", "been", "talking", "about", "and", "after", "the", "verb—merely", "by", "way", "of", "ornament", "as", "far", "as", "i", "can", "make", "out—the", "writer", "shovels", "in", "haben", "sind", "gewesen", "gehabt", "haben", "geworden", "sein", "or", "words", "to", "that", "effect", "and", "the", "monument", "is", "finished", "i", "suppose", "that", "this", "closing", "hurrah", "is", "in", "the", "nature", "of", "the", "flourish", "to", "a", "mans", "signature—not", "necessary", "but", "pretty", "german", "books", "are", "easy", "enough", "to", "read", "when", "you", "hold", "them", "before", "the", "lookingglass", "or", "stand", "on", "your", "head—so", "as", "to", "reverse", "the", "construction—but", "i", "think", "that", "to", "learn", "to", "read", "and", "understand", "a", "german", "newspaper", "is", "a", "thing", "which", "must", "always", "remain", "an", "impossibility", "to", "a", "foreigner", "yet", "even", "the", "german", "books", "are", "not", "entirely", "free", "from", "attacks", "of", "the", "parenthesis", "distemper—though", "they", "are", "usually", "so", "mild", "as", "to", "cover", "only", "a", "few", "lines", "and", "therefore", "when", "you", "at", "last", "get", "down", "to", "the", "verb", "it", "carries", "some", "meaning", "to", "your", "mind", "because", "you", "are", "able", "to", "remember", "a", "good", "deal", "of", "what", "has", "gone", "before", "now", "here", "is", "a", "sentence", "from", "a", "popular", "and", "excellent", "german", "novel—with", "a", "slight", "parenthesis", "in", "it", "i", "will", "make", "a", "perfectly", "literal", "translation", "and", "throw", "in", "the", "parenthesismarks", "and", "some", "hyphens", "for", "the", "assistance", "of", "the", "reader—though", "in", "the", "original", "there", "are", "no", "parenthesismarks", "or", "hyphens", "and", "the", "reader", "is", "left", "to", "flounder", "through", "to", "the", "remote", "verb", "the", "best", "way", "he", "can", "but", "when", "he", "upon", "the", "street", "the", "insatinandsilkcovered", "nowveryunconstrainedlyafterthenewestfashiondressed", "government", "counsellors", "wife", "met", "etc", "etc1", "that", "is", "from", "the", "old", "mamselles", "secret", "by", "mrs", "marlitt", "and", "that", "sentence", "is", "constructed", "upon", "the", "most", "approved", "german", "model", "you", "observe", "how", "far", "that", "verb", "is", "from", "the", "readers", "base", "of", "operations", "well", "in", "a", "german", "newspaper", "they", "put", "their", "verb", "away", "over", "on", "the", "next", "page", "and", "i", "have", "heard", "that", "sometimes", "after", "stringing", "along", "on", "exciting", "preliminaries", "and", "parentheses", "for", "a", "column", "or", "two", "they", "get", "in", "a", "hurry", "and", "have", "to", "go", "to", "press", "without", "getting", "to", "the", "verb", "at", "all", "of", "course", "then", "the", "reader", "is", "left", "in", "a", "very", "exhausted", "and", "ignorant", "state", "we", "have", "the", "parenthesis", "disease", "in", "our", "literature", "too", "and", "one", "may", "see", "cases", "of", "it", "every", "day", "in", "our", "books", "and", "newspapers", "but", "with", "us", "it", "is", "the", "mark", "and", "sign", "of", "an", "unpractised", "writer", "or", "a", "cloudy", "intellect", "whereas", "with", "the", "germans", "it", "is", "doubtless", "the", "mark", "and", "sign", "of", "a", "practised", "pen", "and", "of", "the", "presence", "of", "that", "sort", "of", "luminous", "intellectual", "fog", "which", "stands", "for", "clearness", "among", "these", "people", "for", "surely", "it", "is", "not", "clearness—it", "necessarily", "cant", "be", "clearness", "even", "a", "jury", "would", "have", "penetration", "enough", "to", "discover", "that", "a", "writers", "ideas", "must", "be", "a", "good", "deal", "confused", "a", "good", "deal", "out", "of", "line", "and", "sequence", "when", "he", "starts", "out", "to", "say", "that", "a", "man", "met", "a", "counsellors", "wife", "in", "the", "street", "and", "then", "right", "in", "the", "midst", "of", "this", "so", "simple", "undertaking", "halts", "these", "approaching", "people", "and", "makes", "them", "stand", "still", "until", "he", "jots", "down", "an", "inventory", "of", "the", "womans", "dress", "that", "is", "manifestly", "absurd", "it", "reminds", "a", "person", "of", "those", "dentists", "who", "secure", "your", "instant", "and", "breathless", "interest", "in", "a", "tooth", "by", "taking", "a", "grip", "on", "it", "with", "the", "forceps", "and", "then", "stand", "there", "and", "drawl", "through", "a", "tedious", "anecdote", "before", "they", "give", "the", "dreaded", "jerk", "parentheses", "in", "literature", "and", "dentistry", "are", "in", "bad", "taste", "the", "germans", "have", "another", "kind", "of", "parenthesis", "which", "they", "make", "by", "splitting", "a", "verb", "in", "two", "and", "putting", "half", "of", "it", "at", "the", "beginning", "of", "an", "exciting", "chapter", "and", "the", "other", "half", "at", "the", "end", "of", "it", "can", "any", "one", "conceive", "of", "anything", "more", "confusing", "than", "that", "these", "things", "are", "called", "separable", "verbs", "the", "german", "grammar", "is", "blistered", "all", "over", "with", "separable", "verbs", "and", "the", "wider", "the", "two", "portions", "of", "one", "of", "them", "are", "spread", "apart", "the", "better", "the", "author", "of", "the", "crime", "is", "pleased", "with", "his", "performance", "a", "favorite", "one", "is", "reiste", "ab—which", "means", "departed", "here", "is", "an", "example", "which", "i", "culled", "from", "a", "novel", "and", "reduced", "to", "english", "the", "trunks", "being", "now", "ready", "he", "de", "after", "kissing", "his", "mother", "and", "sisters", "and", "once", "more", "pressing", "to", "his", "bosom", "his", "adored", "gretchen", "who", "dressed", "in", "simple", "white", "muslin", "with", "a", "single", "tuberose", "in", "the", "ample", "folds", "of", "her", "rich", "brown", "hair", "had", "tottered", "feebly", "down", "the", "stairs", "still", "pale", "from", "the", "terror", "and", "excitement", "of", "the", "past", "evening", "but", "longing", "to", "lay", "her", "poor", "aching", "head", "yet", "once", "again", "upon", "the", "breast", "of", "him", "whom", "she", "loved", "more", "dearly", "than", "life", "itself", "parted", "however", "it", "is", "not", "well", "to", "dwell", "too", "much", "on", "the", "separable", "verbs", "one", "is", "sure", "to", "lose", "his", "temper", "early", "and", "if", "he", "sticks", "to", "the", "subject", "and", "will", "not", "be", "warned", "it", "will", "at", "last", "either", "soften", "his", "brain", "or", "petrify", "it", "personal", "pronouns", "and", "adjectives", "are", "a", "fruitful", "nuisance", "in", "this", "language", "and", "should", "have", "been", "left", "out", "for", "instance", "the", "same", "sound", "sie", "means", "you", "and", "it", "means", "she", "and", "it", "means", "her", "and", "it", "means", "it", "and", "it", "means", "they", "and", "it", "means", "them", "think", "of", "the", "ragged", "poverty", "of", "a", "language", "which", "has", "to", "make", "one", "word", "do", "the", "work", "of", "six—and", "a", "poor", "little", "weak", "thing", "of", "only", "three", "letters", "at", "that", "but", "mainly", "think", "of", "the", "exasperation", "of", "never", "knowing", "which", "of", "these", "meanings", "the", "speaker", "is", "trying", "to", "convey", "this", "explains", "why", "whenever", "a", "person", "says", "sie", "to", "me", "i", "generally", "try", "to", "kill", "him", "if", "a", "stranger", "now", "observe", "the", "adjective", "here", "was", "a", "case", "where", "simplicity", "would", "have", "been", "an", "advantage", "therefore", "for", "no", "other", "reason", "the", "inventor", "of", "this", "language", "complicated", "it", "all", "he", "could", "when", "we", "wish", "to", "speak", "of", "our", "good", "friend", "or", "friends", "in", "our", "enlightened", "tongue", "we", "stick", "to", "the", "one", "form", "and", "have", "no", "trouble", "or", "hard", "feeling", "about", "it", "but", "with", "the", "german", "tongue", "it", "is", "different", "when", "a", "german", "gets", "his", "hands", "on", "an", "adjective", "he", "declines", "it", "and", "keeps", "on", "declining", "it", "until", "the", "common", "sense", "is", "all", "declined", "out", "of", "it", "it", "is", "as", "bad", "as", "latin", "he", "says", "for", "instance", "singular", "nominative—mein", "guter", "freund", "my", "good", "friend", "genitive—meines", "guten", "freundes", "of", "my", "good", "friend", "dative—meinem", "guten", "freund", "to", "my", "good", "friend", "accusative—meinen", "guten", "freund", "my", "good", "friend", "plural", "n—meine", "guten", "freunde", "my", "good", "friends", "g—meiner", "guten", "freunde", "of", "my", "good", "friends", "d—meinen", "guten", "freunden", "to", "my", "good", "friends", "a—meine", "guten", "freunde", "my", "good", "friends", "now", "let", "the", "candidate", "for", "the", "asylum", "try", "to", "memorize", "those", "variations", "and", "see", "how", "soon", "he", "will", "be", "elected", "one", "might", "better", "go", "without", "friends", "in", "germany", "than", "take", "all", "this", "trouble", "about", "them", "i", "have", "shown", "what", "a", "bother", "it", "is", "to", "decline", "a", "good", "male", "friend", "well", "this", "is", "only", "a", "third", "of", "the", "work", "for", "there", "is", "a", "variety", "of", "new", "distortions", "of", "the", "adjective", "to", "be", "learned", "when", "the", "object", "is", "feminine", "and", "still", "another", "when", "the", "object", "is", "neuter", "now", "there", "are", "more", "adjectives", "in", "this", "language", "than", "there", "are", "black", "cats", "in", "switzerland", "and", "they", "must", "all", "be", "as", "elaborately", "declined", "as", "the", "examples", "above", "suggested", "difficult—troublesome—these", "words", "cannot", "describe", "it", "i", "heard", "a", "californian", "student", "in", "heidelberg", "say", "in", "one", "of", "his", "calmest", "moods", "that", "he", "would", "rather", "decline", "two", "drinks", "than", "one", "german", "adjective", "the", "inventor", "of", "the", "language", "seems", "to", "have", "taken", "pleasure", "in", "complicating", "it", "in", "every", "way", "he", "could", "think", "of", "for", "instance", "if", "one", "is", "casually", "referring", "to", "a", "house", "haus", "or", "a", "horse", "pferd", "or", "a", "dog", "hund", "he", "spells", "these", "words", "as", "i", "have", "indicated", "but", "if", "he", "is", "referring", "to", "them", "in", "the", "dative", "case", "he", "sticks", "on", "a", "foolish", "and", "unnecessary", "e", "and", "spells", "them", "hause", "pferde", "hunde", "so", "as", "an", "added", "e", "often", "signifies", "the", "plural", "as", "the", "s", "does", "with", "us", "the", "new", "student", "is", "likely", "to", "go", "on", "for", "a", "month", "making", "twins", "out", "of", "a", "dative", "dog", "before", "he", "discovers", "his", "mistake", "and", "on", "the", "other", "hand", "many", "a", "new", "student", "who", "could", "ill", "afford", "loss", "has", "bought", "and", "paid", "for", "two", "dogs", "and", "only", "got", "one", "of", "them", "because", "he", "ignorantly", "bought", "that", "dog", "in", "the", "dative", "singular", "when", "he", "really", "supposed", "he", "was", "talking", "plural—which", "left", "the", "law", "on", "the", "sellers", "side", "of", "course", "by", "the", "strict", "rules", "of", "grammar", "and", "therefore", "a", "suit", "for", "recovery", "could", "not", "lie", "in", "german", "all", "the", "nouns", "begin", "with", "a", "capital", "letter", "now", "that", "is", "a", "good", "idea", "and", "a", "good", "idea", "in", "this", "language", "is", "necessarily", "conspicuous", "from", "its", "lonesomeness", "i", "consider", "this", "capitalizing", "of", "nouns", "a", "good", "idea", "because", "by", "reason", "of", "it", "you", "are", "almost", "always", "able", "to", "tell", "a", "noun", "the", "minute", "you", "see", "it", "you", "fall", "into", "error", "occasionally", "because", "you", "mistake", "the", "name", "of", "a", "person", "for", "the", "name", "of", "a", "thing", "and", "waste", "a", "good", "deal", "of", "time", "trying", "to", "dig", "a", "meaning", "out", "of", "it", "german", "names", "almost", "always", "do", "mean", "something", "and", "this", "helps", "to", "deceive", "the", "student", "i", "translated", "a", "passage", "one", "day", "which", "said", "that", "the", "infuriated", "tigress", "broke", "loose", "and", "utterly", "ate", "up", "the", "unfortunate", "firforest", "tannenwald", "when", "i", "was", "girding", "up", "my", "loins", "to", "doubt", "this", "i", "found", "out", "that", "tannenwald", "in", "this", "instance", "was", "a", "mans", "name", "every", "noun", "has", "a", "gender", "and", "there", "is", "no", "sense", "or", "system", "in", "the", "distribution", "so", "the", "gender", "of", "each", "must", "be", "learned", "separately", "and", "by", "heart", "there", "is", "no", "other", "way", "to", "do", "this", "one", "has", "to", "have", "a", "memory", "like", "a", "memorandum", "book", "in", "german", "a", "young", "lady", "has", "no", "sex", "while", "a", "turnip", "has", "think", "what", "overwrought", "reverence", "that", "shows", "for", "the", "turnip", "and", "what", "callous", "disrespect", "for", "the", "girl", "see", "how", "it", "looks", "in", "print—i", "translate", "this", "from", "a", "conversation", "in", "one", "of", "the", "best", "of", "the", "german", "sundayschool", "books", "“gretchen\ufeffwilhelm", "where", "is", "the", "turnip", "“wilhelm\ufeffshe", "has", "gone", "to", "the", "kitchen", "“gretchen\ufeffwhere", "is", "the", "accomplished", "and", "beautiful", "english", "maiden", "“wilhelm\ufeffit", "has", "gone", "to", "the", "opera", "to", "continue", "with", "the", "german", "genders", "a", "tree", "is", "male", "its", "buds", "are", "female", "its", "leaves", "are", "neuter", "horses", "are", "sexless", "dogs", "are", "male", "cats", "are", "female—tomcats", "included", "of", "course", "a", "persons", "mouth", "neck", "bosom", "elbows", "fingers", "nails", "feet", "and", "body", "are", "of", "the", "male", "sex", "and", "his", "head", "is", "male", "or", "neuter", "according", "to", "the", "word", "selected", "to", "signify", "it", "and", "not", "according", "to", "the", "sex", "of", "the", "individual", "who", "wears", "it—for", "in", "germany", "all", "the", "women", "wear", "either", "male", "heads", "or", "sexless", "ones", "a", "persons", "nose", "lips", "shoulders", "breast", "hands", "hips", "and", "toes", "are", "of", "the", "female", "sex", "and", "his", "hair", "ears", "eyes", "chin", "legs", "knees", "heart", "and", "conscience", "havent", "any", "sex", "at", "all", "the", "inventor", "of", "the", "language", "probably", "got", "what", "he", "knew", "about", "a", "conscience", "from", "hearsay", "now", "by", "the", "above", "dissection", "the", "reader", "will", "see", "that", "in", "germany", "a", "man", "may", "think", "he", "is", "a", "man", "but", "when", "he", "comes", "to", "look", "into", "the", "matter", "closely", "he", "is", "bound", "to", "have", "his", "doubts", "he", "finds", "that", "in", "sober", "truth", "he", "is", "a", "most", "ridiculous", "mixture", "and", "if", "he", "ends", "by", "trying", "to", "comfort", "himself", "with", "the", "thought", "that", "he", "can", "at", "least", "depend", "on", "a", "third", "of", "this", "mess", "as", "being", "manly", "and", "masculine", "the", "humiliating", "second", "thought", "will", "quickly", "remind", "him", "that", "in", "this", "respect", "he", "is", "no", "better", "off", "than", "any", "woman", "or", "cow", "in", "the", "land", "in", "the", "german", "it", "is", "true", "that", "by", "some", "oversight", "of", "the", "inventor", "of", "the", "language", "a", "woman", "is", "a", "female", "but", "a", "wife", "weib", "is", "not—which", "is", "unfortunate", "a", "wife", "here", "has", "no", "sex", "she", "is", "neuter", "so", "according", "to", "the", "grammar", "a", "fish", "is", "he", "his", "scales", "are", "she", "but", "a", "fishwife", "is", "neither", "to", "describe", "a", "wife", "as", "sexless", "may", "be", "called", "underdescription", "that", "is", "bad", "enough", "but", "overdescription", "is", "surely", "worse", "a", "german", "speaks", "of", "an", "englishman", "as", "the", "engländer", "to", "change", "the", "sex", "he", "adds", "inn", "and", "that", "stands", "for", "englishwoman—engländerinn", "that", "seems", "descriptive", "enough", "but", "still", "it", "is", "not", "exact", "enough", "for", "a", "german", "so", "he", "precedes", "the", "word", "with", "that", "article", "which", "indicates", "that", "the", "creature", "to", "follow", "is", "feminine", "and", "writes", "it", "down", "thus", "die", "englanderinn—which", "means", "the", "sheenglishwoman", "i", "consider", "that", "that", "person", "is", "overdescribed", "well", "after", "the", "student", "has", "learned", "the", "sex", "of", "a", "great", "number", "of", "nouns", "he", "is", "still", "in", "a", "difficulty", "because", "he", "finds", "it", "impossible", "to", "persuade", "his", "tongue", "to", "refer", "to", "things", "as", "he", "and", "she", "and", "him", "and", "her", "which", "it", "has", "been", "always", "accustomed", "to", "refer", "to", "as", "it", "when", "he", "even", "frames", "a", "german", "sentence", "in", "his", "mind", "with", "the", "hims", "and", "hers", "in", "the", "right", "places", "and", "then", "works", "up", "his", "courage", "to", "the", "utterancepoint", "it", "is", "no", "use—the", "moment", "he", "begins", "to", "speak", "his", "tongue", "flies", "the", "track", "and", "all", "those", "labored", "males", "and", "females", "come", "out", "as", "its", "and", "even", "when", "he", "is", "reading", "german", "to", "himself", "he", "always", "calls", "those", "things", "it", "whereas", "he", "ought", "to", "read", "in", "this", "way", "tale", "of", "the", "fishwife", "and", "its", "sad", "fate2", "it", "is", "a", "bleak", "day", "hear", "the", "rain", "how", "he", "pours", "and", "the", "hail", "how", "he", "rattles", "and", "see", "the", "snow", "how", "he", "drifts", "along", "and", "oh", "the", "mud", "how", "deep", "he", "is", "ah", "the", "poor", "fishwife", "it", "is", "stuck", "fast", "in", "the", "mire", "it", "has", "dropped", "its", "basket", "of", "fishes", "and", "its", "hands", "have", "been", "cut", "by", "the", "scales", "as", "it", "seized", "some", "of", "the", "falling", "creatures", "and", "one", "scale", "has", "even", "got", "into", "its", "eye", "and", "it", "cannot", "get", "her", "out", "it", "opens", "its", "mouth", "to", "cry", "for", "help", "but", "if", "any", "sound", "comes", "out", "of", "him", "alas", "he", "is", "drowned", "by", "the", "raging", "of", "the", "storm", "and", "now", "a", "tomcat", "has", "got", "one", "of", "the", "fishes", "and", "she", "will", "surely", "escape", "with", "him", "no", "she", "bites", "off", "a", "fin", "she", "holds", "her", "in", "her", "mouth—will", "she", "swallow", "her", "no", "the", "fishwifes", "brave", "motherdog", "deserts", "his", "puppies", "and", "rescues", "the", "fin—which", "he", "eats", "himself", "as", "his", "reward", "o", "horror", "the", "lightning", "has", "struck", "the", "fishbasket", "he", "sets", "him", "on", "fire", "see", "the", "flame", "how", "she", "licks", "the", "doomed", "utensil", "with", "her", "red", "and", "angry", "tongue", "now", "she", "attacks", "the", "helpless", "fishwifes", "foot—she", "burns", "him", "up", "all", "but", "the", "big", "toe", "and", "even", "she", "is", "partly", "consumed", "and", "still", "she", "spreads", "still", "she", "waves", "her", "fiery", "tongues", "she", "attacks", "the", "fishwifes", "leg", "and", "destroys", "it", "she", "attacks", "its", "hand", "and", "destroys", "her", "she", "attacks", "its", "poor", "worn", "garment", "and", "destroys", "her", "also", "she", "attacks", "its", "body", "and", "consumes", "him", "she", "wreathes", "herself", "about", "its", "heart", "and", "it", "is", "consumed", "next", "about", "its", "breast", "and", "in", "a", "moment", "she", "is", "a", "cinder", "now", "she", "reaches", "its", "neck—he", "goes", "now", "its", "chin—it", "goes", "now", "its", "nose—she", "goes", "in", "another", "moment", "except", "help", "come", "the", "fishwife", "will", "be", "no", "more", "time", "presses—is", "there", "none", "to", "succor", "and", "save", "yes", "joy", "joy", "with", "flying", "feet", "the", "sheenglishwoman", "comes", "but", "alas", "the", "generous", "shefemale", "is", "too", "late", "where", "now", "is", "the", "fated", "fishwife", "it", "has", "ceased", "from", "its", "sufferings", "it", "has", "gone", "to", "a", "better", "land", "all", "that", "is", "left", "of", "it", "for", "its", "loved", "ones", "to", "lament", "over", "is", "this", "poor", "smouldering", "ashheap", "ah", "woful", "woful", "ashheap", "let", "us", "take", "him", "up", "tenderly", "reverently", "upon", "the", "lowly", "shovel", "and", "bear", "him", "to", "his", "long", "rest", "with", "the", "prayer", "that", "when", "he", "rises", "again", "it", "will", "be", "in", "a", "realm", "where", "he", "will", "have", "one", "good", "square", "responsible", "sex", "and", "have", "it", "all", "to", "himself", "instead", "of", "having", "a", "mangy", "lot", "of", "assorted", "sexes", "scattered", "all", "over", "him", "in", "spots", "there", "now", "the", "reader", "can", "see", "for", "himself", "that", "this", "pronounbusiness", "is", "a", "very", "awkward", "thing", "for", "the", "unaccustomed", "tongue", "i", "suppose", "that", "in", "all", "languages", "the", "similarities", "of", "look", "and", "sound", "between", "words", "which", "have", "no", "similarity", "in", "meaning", "are", "a", "fruitful", "source", "of", "perplexity", "to", "the", "foreigner", "it", "is", "so", "in", "our", "tongue", "and", "it", "is", "notably", "the", "case", "in", "the", "german", "now", "there", "is", "that", "troublesome", "word", "vermählt", "to", "me", "it", "has", "so", "close", "a", "resemblance—either", "real", "or", "fancied—to", "three", "or", "four", "other", "words", "that", "i", "never", "know", "whether", "it", "means", "despised", "painted", "suspected", "or", "married", "until", "i", "look", "in", "the", "dictionary", "and", "then", "i", "find", "it", "means", "the", "latter", "there", "are", "lots", "of", "such", "words", "and", "they", "are", "a", "great", "torment", "to", "increase", "the", "difficulty", "there", "are", "words", "which", "seem", "to", "resemble", "each", "other", "and", "yet", "do", "not", "but", "they", "make", "just", "as", "much", "trouble", "as", "if", "they", "did", "for", "instancethere", "is", "the", "word", "vermiethen", "to", "let", "to", "lease", "to", "hire", "and", "the", "word", "verheirathen", "another", "way", "of", "saying", "to", "marry", "i", "heard", "of", "an", "englishman", "who", "knocked", "at", "a", "mans", "door", "in", "heidelberg", "and", "proposed", "in", "the", "best", "german", "he", "could", "command", "to", "verheirathen", "that", "house", "then", "there", "are", "some", "words", "which", "mean", "one", "thing", "when", "you", "emphasize", "the", "first", "syllable", "but", "mean", "something", "very", "different", "if", "you", "throw", "the", "emphasis", "on", "the", "last", "syllable", "for", "instance", "there", "is", "a", "word", "which", "means", "a", "runaway", "or", "the", "act", "of", "glancing", "through", "a", "book", "according", "to", "the", "placing", "of", "the", "emphasis", "and", "another", "word", "which", "signifies", "to", "associate", "with", "a", "man", "or", "to", "avoid", "him", "according", "to", "where", "you", "put", "the", "emphasis—and", "you", "can", "generally", "depend", "on", "putting", "it", "in", "the", "wrong", "place", "and", "getting", "into", "trouble", "there", "are", "some", "exceedingly", "useful", "words", "in", "this", "language", "schlag", "for", "example", "and", "zug", "there", "are", "threequarters", "of", "a", "column", "of", "schlags", "in", "the", "dictionary", "and", "a", "column", "and", "a", "half", "of", "zugs", "the", "word", "schlag", "means", "blow", "stroke", "dash", "hit", "shock", "clip", "slap", "time", "bar", "coin", "stamp", "kind", "sort", "manner", "way", "apoplexy", "woodcutting", "enclosure", "field", "forestclearing", "this", "is", "its", "simple", "and", "exact", "meaning—that", "is", "to", "say", "its", "restricted", "its", "fettered", "meaning", "but", "there", "are", "ways", "by", "which", "you", "can", "set", "it", "free", "so", "that", "it", "can", "soar", "away", "as", "on", "the", "wings", "of", "the", "morning", "and", "never", "be", "at", "rest", "you", "can", "hang", "any", "word", "you", "please", "to", "its", "tail", "and", "make", "it", "mean", "anything", "you", "want", "to", "you", "can", "begin", "with", "schlagader", "which", "means", "artery", "and", "you", "can", "hang", "on", "the", "whole", "dictionary", "word", "by", "word", "clear", "through", "the", "alphabet", "to", "schlagwasser", "which", "means", "bilgewater—and", "including", "schlagmutter", "which", "means", "motherinlaw", "just", "the", "same", "with", "zug", "strictly", "speaking", "zug", "means", "pull", "tug", "draught", "procession", "march", "progress", "flight", "direction", "expedition", "train", "caravan", "passage", "stroke", "touch", "line", "flourish", "trait", "of", "character", "feature", "lineament", "chessmove", "organstop", "team", "whiff", "bias", "drawer", "propensity", "inhalation", "disposition", "but", "that", "thing", "which", "it", "does", "not", "mean—when", "all", "its", "legitimate", "pendants", "have", "been", "hung", "on", "has", "not", "been", "discovered", "yet", "one", "cannot", "overestimate", "the", "usefulness", "of", "schlag", "and", "zug", "armed", "just", "with", "these", "two", "and", "the", "word", "also", "what", "cannot", "the", "foreigner", "on", "german", "soil", "accomplish", "the", "german", "word", "also", "is", "the", "equivalent", "of", "the", "english", "phrase", "you", "know", "and", "does", "not", "mean", "anything", "at", "all—in", "talk", "though", "it", "sometimes", "does", "in", "print", "every", "time", "a", "german", "opens", "his", "mouth", "an", "also", "falls", "out", "and", "every", "time", "he", "shuts", "it", "he", "bites", "one", "in", "two", "that", "was", "trying", "to", "get", "out", "now", "the", "foreigner", "equipped", "with", "these", "three", "noble", "words", "is", "master", "of", "the", "situation", "let", "him", "talk", "right", "along", "fearlessly", "let", "him", "pour", "his", "indifferent", "german", "forth", "and", "when", "he", "lacks", "for", "a", "word", "let", "him", "heave", "a", "schlag", "into", "the", "vacuum", "all", "the", "chances", "are", "that", "it", "fits", "it", "like", "a", "plug", "but", "if", "it", "doesnt", "let", "him", "promptly", "heave", "a", "zug", "after", "it", "the", "two", "together", "can", "hardly", "fail", "to", "bung", "the", "hole", "but", "if", "by", "a", "miracle", "they", "should", "fail", "let", "him", "simply", "say", "also", "and", "this", "will", "give", "him", "a", "moments", "chance", "to", "think", "of", "the", "needful", "word", "in", "germany", "when", "you", "load", "your", "conversational", "gun", "it", "is", "always", "best", "to", "throw", "in", "a", "schlag", "or", "two", "and", "a", "zug", "or", "two", "because", "it", "doesnt", "make", "any", "difference", "how", "much", "the", "rest", "of", "the", "charge", "may", "scatter", "you", "are", "bound", "to", "bag", "something", "with", "them", "then", "you", "blandly", "say", "also", "and", "load", "up", "again", "nothing", "gives", "such", "an", "air", "of", "grace", "and", "elegance", "and", "unconstraint", "to", "a", "german", "or", "an", "english", "conversation", "as", "to", "scatter", "it", "full", "of", "alsos", "or", "you", "knows", "in", "my", "notebook", "i", "find", "this", "entry", "july", "1—in", "the", "hospital", "yesterday", "a", "word", "of", "thirteen", "syllables", "was", "successfully", "removed", "from", "a", "patient—a", "northgerman", "from", "near", "hamburg", "but", "as", "most", "unfortunately", "the", "surgeons", "had", "opened", "him", "in", "the", "wrong", "place", "under", "the", "impression", "that", "he", "contained", "a", "panorama", "he", "died", "the", "sad", "event", "has", "cast", "a", "gloom", "over", "the", "whole", "community", "that", "paragraph", "furnishes", "a", "text", "for", "a", "few", "remarks", "about", "one", "of", "the", "most", "curious", "and", "notable", "features", "of", "my", "subject—the", "length", "of", "german", "words", "some", "german", "words", "are", "so", "long", "that", "they", "have", "a", "perspective", "observe", "these", "examples", "freundschaftsbezeigungen", "dilletantenaufdringlichkeiten", "stadtverordnetenversammlungen", "these", "things", "are", "not", "words", "they", "are", "alphabetical", "processions", "and", "they", "are", "not", "rare", "one", "can", "open", "a", "german", "newspaper", "any", "time", "and", "see", "them", "marching", "majestically", "across", "the", "page—and", "if", "he", "has", "any", "imagination", "he", "can", "see", "the", "banners", "and", "hear", "the", "music", "too", "they", "impart", "a", "martial", "thrill", "to", "the", "meekest", "subject", "i", "take", "a", "great", "interest", "in", "these", "curiosities", "whenever", "i", "come", "across", "a", "good", "one", "i", "stuff", "it", "and", "put", "it", "in", "my", "museum", "in", "this", "way", "i", "have", "made", "quite", "a", "valuable", "collection", "when", "i", "get", "duplicates", "i", "exchange", "with", "other", "collectors", "and", "thus", "increase", "the", "variety", "of", "my", "stock", "here", "are", "some", "specimens", "which", "i", "lately", "bought", "at", "an", "auction", "sale", "of", "the", "effects", "of", "a", "bankrupt", "bricabrac", "hunter", "generalstaatsverordnetenversammlungen", "alterthumswissenschaften", "kinderbewahrungsanstalten", "unabhaengigkeitserklaerungen", "wiederherstellungsbestrebungen", "waffenstillstandsunterhandlungen"};

    for(auto number : numbers) {
        chain.addData(number, true);
    }
    chain.calculateWeights();
    chain.setStartState(static_cast <float> (rand()) / static_cast <float> (RAND_MAX));
    for (int i = 0; i<100; i++) {
        std::cout << (chain.getDataAndAdvance(static_cast <float> (rand()) / static_cast <float> (RAND_MAX)));
        std::cout << " ";
    }

    std::cout << std::endl;

}
\$\endgroup\$
2
\$\begingroup\$

On your general coding style:

First the little things:

template <typename T>
Transition<T>::Transition(std::shared_ptr<State<T>> nextState) {
   weight = 0;
   rawCount = 0;
   this->nextState = nextState;
}
  • Use the initializer list of your constructor, that would also elide the necessity of the "this->" see here.
  • Later you will always set rawCount to 1 after the construction, so why not here? Your weight would also be better initialized with 1.0f. This would result in:

    template <typename T>
    Transition<T>::Transition(std::shared_ptr<State<T>> nextState) :
        weight(1.0f),
        rawCount(1),
        nextSate(nextState)
    {
        /* nothing */
    }
    
  • I would suggest to make the "transitions" member a std::vector. All you do is push_back and iterate over it. Since you asked specifically for performance: A vector stores its data in continous memory, a list not neccessraily, thus iterating over a vector will (general) be faster. See this question for detailed comparison.

  • If you want to only increment a variable use the prefix operator. For example this newState->rawStartCount++; should be changed to ++(newState->rawStartCount);. The brackets add a little clarity. The reason for that is discussed in many Q/A, for example here. One reason is that the postfix might be less efficient because it needs to store a temporal copy of the value. Another reason is clarity: If you want to increment a value just do it and do nothing extra. Or better: Using the postfix can always lead to someone wondering if you need the old value.

  • const-correctness in range-base for-loops. If you do not change the state of the elements make them const. So this

    for(auto&& transition : transitions) {
        weightCounter += transition.rawCount;
    }
    

    should become

    for(const auto&& transition : transitions) {
        weightCounter += transition.rawCount;
    }
    
  • const correctnes in general. I do not see a single const in your code. But there are variables and functions which should be const, for example the numbers in your main function. Always try to make your code as const correct as you can do it.

  • use static_cast for number conversions. In your main function you do it but in MarkovChain<T>::calculateWeights() you use float(state->rawStartCount) / float(startWeightCounter);. This should also be a static_cast. One reason is that you can better look it up with search-functions. And again it expresses clearly what you do which is a "static cast". Again more detailed discussion is here.

  • Replace std::endl with "\n" when appropriate. std::endl not only inserts a newline it also flushes the stream. This is in most situations not neccessary and can also lead to a huge performance impact.

  • Delete not reachable code. In getNextSate(float), the output after the return is useless.

Now a few design related things:

Class State:

  • Why do you make some variables public and some private? If you want to use it as a "Storage" which has nothing more to do as to save the data then use a struct, otherwise I would advise to use a class and make every Member private. The purpose is that you have control over the access of the member and thus you can make your class "hard to use wrong" and if you you need permanent access to it from somewhere else maybe the member is misplaced. Example "startWeight" of the Class State is never used in the class itself. Maybe the Class MarkovChain shoukd have a struct which savaes a State and its startWeight.

  • "Make it hard to use wrong" : Your program depends on the fact that a user first adds the data, than calls calculateWights() and than iterates. Why not let the addData function update the Weights every time it is called? If you feel bad about the performance maybe you can build a addData function which takes a whole std::vector.

  • "A Function should have only one responsibility" : I would break your getDataAndAdvance(float) in one function getData() and one advance(float). This would make the code better to understand and the user could also operate multiple times on the same data before advancing.

And last but not least Bugs:

  • The state for the data added last to the chain will not have any transitions, thus getNextState(float) will crash.

  • As for your return "will never be called" I would suggest to use assertions. These can be usefull to tell everyone who reads the code what preliminaries you expect. For example in getNextState: assert(randomValue <= 1.0 + 1e-06) will show that you expect the randomValue to be lower than 1.0. I inserted the + 1e-06 cause of problems with comparing floating points. You can insert the same for randomValue >= 0.

I hope this helps a bit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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