Basic Markov Chain Algorithm

Question

So I have a file(story.dat) with a randomly generated story like: "Sleeping in his car was never the plan but sometimes things don't work out as planned. This..."

It will print out each word and the corresponding word to it like so:

0."It: was,
1."Pepsi-Cola.": He,
2."This: is,
3./: 50.,
4.50: /,
5.50.: I,
6.A: long,
7.All: that,
8.He: didn't,knew,had,
9.I: think,had,
10.I'd: love,
11.I'm: certain,
12.It: was,
13.Or: at,
14.She: knew,
15.Sleeping: in, ...

And then it prints the story like so:

have a cup of everything. The inside was ten, and a little strange, but he was either exhausted of days ago. It was supposed to hear from you today and fondling over it. He knew what made the last option is to make a year ago. It was supposed to make this case, was in months. The third is the sun. He knew...

Here's the code:

// #include files
namespace Randomiser
{
    std::mt19937 generator{ static_cast<std::mt19937::result_type>(std::time(nullptr)) };
}
int getRandomNumber(int min, int max)
{
    std::uniform_int_distribution<int> rand{ min, max };
    return rand(Randomiser::generator);
}

void markovIt(const std::map<std::string, std::vector<std::string>>& m)
{
    std::string temp{};
    std::vector<std::string> possibilities{};
    std::string next{};
    
    int i{ 0 };
    int randomNumber{ getRandomNumber(0, m.size()) };
    for (const auto& n : m)
    {
        if (i == randomNumber)
        {
            temp = n.first;
        }
        ++i;
    }

    auto found{ m.find(temp) };
    i = 0;
    while(found != m.end())
    {
        if (i == 255)
            break;

        possibilities = found->second;
        next = possibilities.at(getRandomNumber(0, possibilities.size() - 1));
        
        std::cout << temp << " ";
        temp = next;
        
        found = m.find(temp);
        ++i;
    }
}

int main()
{
    std::ifstream wordStream{ "story.dat" };
    std::string fWord;
    std::string sWord;
    std::vector<std::string> temp;
    std::map<std::string, std::vector<std::string>> gram{};
    int i{ 0 };
    while(wordStream)
    {
        wordStream >> fWord;
        if (i != 0)
            gram[sWord].push_back(fWord);
        wordStream >> sWord;
        gram[fWord].push_back(sWord);
        if (i == 0)
            i++;
    }

    i =  0;
    for (const auto& n : gram)
    {
        std::cout << i << "." << n.first << ": ";
        for (const auto& key : n.second)
            std::cout << key << ",";
        std::cout << '\n';
        ++i;
    }

    markovIt(gram);
    std::cout << '\n';

    return 0;
}

The implementation feels awful and I believe it could be optimised alot further. I'm just not sure where to take it.

Answer 1

Use std::random_device instead of time()

Stay within C++, and use a real random device to seed the generator, like so:

std::random_device rd;
std::mt19937 generator{rd()};

Consider turning Randomiser into an anonymous namespace

Does this namespace need a name? If only getRandomNumber() uses Randomiser::generator, and it's in the same source file, you can make it an anonynous namespace instead, just omit "Randomiser".

Be consistent with types

Avoid mixing types like int and size_t. It might seem to work fine, but it is easy for errors to happen this way. Before changing types, consider that sometimes you don't really need to specify a type explicitly, and can instead use template<> or auto. For example:

template<typename T>
auto getRandomNumber(T min, T max)
{
    std::uniform_int_distribution<T> rand{ min, max };
    return rand(Randomiser::generator);
}

However, you will now get some compiler errors, because you were actually calling getRandomNumber() with min and max having different types, like in:

int randomNumber{ getRandomNumber(0, m.size()) };

This is actually a good thing, the compiler is telling you something fishy is going on. In fact, m.size() returns a size_t, which can be bigger than what an int can hold on most 64-bit platforms, as well as being unsigned instead of signed. Considering that min is always 0 in your code, I would instead write:

template<typename T>
auto getRandomNumber(T max) {
    std::uniform_int_distribution<T> rand{ 0, max };
    return rand(Randomiser::generator);
}

...

auto randomNumber = getRandomNumber(m.size());

Note that you probably meant getRandomNumber(m.size() - 1) here. This brings me to:

Consider writing a getRandomElement() function

You actually use the random numbers to pick random elements out of containers. So write a function to do exactly that:

template<typename T>
static auto &getRandomElement(const T &container)
{
    std::uniform_int_distribution<size_t> rand{ 0, container.size() - 1 };
    return *std::next(std::begin(container), rand(Randomiser::generator));
}

Simplifying markovIt()

Now that we have the above, we can simplify markovIt() greatly. It can be rewritten as:

void markovIt(const std::map<std::string, std::vector<std::string>>& m)
{
    // Get the initial word
    auto word = getRandomElement(m).first;

    for (int i = 0; i < 255; ++i)
    {
        std::cout << word << " ";

        // Find the entry in m that matches word
        auto entry = m.find(word);
        if (entry == m.end())
            break;

        // Select a random word from the list of possibilities
        word = getRandomElement(entry->second);
    }
}

Move special cases out of loops if possible

While loading story.dat, you use the variable i do determine if you need to push back the first word. You can move that special case outside of the loop. The compiler will probably do this for you even if you don't, but it also cleans up the code if you do so in this case:

wordStream >> fword;
wordStream >> sWord;
gram[fWord].push_back[sWord];

while(wordStream)
{
    wordStream >> fWord;
    gram[sWord].push_back(fWord);
    wordStream >> sWord;
    gram[fWord].push_back(sWord);
}

However, why read two words in each loop iteration? You can rewrite this to:

wordStream >> fWord;

while(wordStream)
{
    wordStream >> sWord;
    gram[fWord].push_back(sWord);
    fWord = sWord;
}

Move more functionality into functions

You are doing too much inside main(). Move more functionality into functions, and keep main() as high-level as possible. For example:

static auto load_gram(const std::string &filename)
{
    std::map<std::string, std::vector<std::string>> gram{};
    std::ifstream wordStream{ filename };

    // load the data into gram here
    ...

    return gram;
}

int main(int argc, char *argv[])
{
    auto gram = load_gram("story.dat");
    markovIt(gram);
}