# Matching a generated string of random letters to an input

I made a program in Python and wanted it to be faster, so I wrote it on C# because it's compiled. To my surprise, the Python program is much faster. I guess there is something wrong with my C# code, but it is pretty simple and straightforward, so I don't know. They are structured about the same way.

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;

//This program generates a string of random lowercase letters and matches it to the user's input
//It does this until it gets a match
//It also displays the closest guess so far and the time it took to guess

namespace Monkey
{
class Program
{
static string userinput()
{
//Takes user input, makes sure it is all lowercase letters, returns string
string input;

while(true)
{
input = Console.ReadLine();

if (Regex.IsMatch(input, @"^[a-z]+$")) { return input; } } } static string generate(int len) { //generates string of random letters, returns the random string Random rnd = new Random(); string alpha = "abcdefghijklmnopqrstuvwxyz"; int letterInt; StringBuilder sb = new StringBuilder(); for (int i = 0; i < len; i++) { letterInt = rnd.Next(26); sb.Append(alpha[letterInt]); } return sb.ToString(); } static int count(int len, string s, string g) { //returns number of letters that match user input int same = 0; for (int i = 0; i < len; i++) { if(g[i] == s[i]) { same++; } } return same; } static void Main(string[] args) { Console.WriteLine("They say if you lock a monkey in a room with a typewriter and enough time,"); Console.WriteLine("the monkey would eventually type a work of Shakespeare."); Console.WriteLine("Let's see how well C# does..."); Console.WriteLine("Enter a word"); Console.WriteLine("(3 letters or less is recommended)"); string solution = userinput(); int size = solution.Length; bool success = false; string guess = null; int correct; int best = 0; Stopwatch watch = Stopwatch.StartNew(); while (!success) { guess = generate(size); correct = count(size, solution, guess); if (correct == size) { success = true; } else if (correct > best) { Console.Write("The best guess so far is: "); Console.WriteLine(guess); best = correct; } } watch.Stop(); TimeSpan ts = watch.Elapsed; Console.WriteLine("Success!"); Console.Write("It took " + ts.TotalSeconds + " seconds for the sharp C to type "); Console.WriteLine("\"" + guess + "\""); Console.ReadLine(); } } }  Python: import random import time #This program generates a string of random letters and matches it with the user's string #It does this until it's guess is the same as the user's string #It also displays closest guess so far and time it took to guess def generate(): # generate random letter for each char of string for c in range(size): guess[c] = random.choice(alpha) def count(): # count how many letters match same = 0 for c in range(size): if guess[c] == solution[c]: same += 1 return same print("They say if you lock a monkey in a room with a typewriter and enough time,") print("the monkey would eventually type a poem by Shakespeare") print("Let's see how well a python does...'") user = "" badinput = True while badinput: # Make sure user only inputs letters user = input("Enter a word\n(5 letters or less is recommended)\n") if user.isalpha(): badinput = False solution = list(user.lower()) size = len(solution) guess = [""] * size alpha = list("abcdefghijklmnopqrstuvwxyz") random.seed() success = False best = 0 # largest number of correct letters so far start = time.time() # start timer while not success: # if number of correct letters = length of word generate() correct = count() if correct == size: success = True elif correct > best: print("The best guess so far is: ", end="") print("".join(guess)) best = correct finish = time.time() # stop timer speed = finish - start print("Success!") print("It took " + str(speed) + " seconds for the python to type ", end="") print("\"" + "".join(guess) + "\"") input()  - I guess I had better get back to typing up some Macbeth! – rolfl Feb 25 '14 at 18:45 You may find this question on StackOverflow useful as well as it discusses pros and cons of instantiating a StringBuilder object: stackoverflow.com/questions/550702/… – scotru Feb 25 '14 at 22:50 Use a profiler to answer a performance question. Anything else is guessing. – Eric Lippert Feb 26 '14 at 7:13 @agentnega: You see what you're doing there, right? You are guessing. Your guesses are good, educated guesses that are probably right, but they are still guesses. For all we know the reason that the C# program is slow is because there's something wrong with the Console.WriteLine causing the output to block or some such thing. I have profiled a lot of C# programs in my day and very frequently -- well over 10% of the time -- my initial guess about the cause of a slowdown is utterly wrong. Engineers solve problems by reasoning about facts, not guesses. – Eric Lippert Feb 26 '14 at 16:12 You say "I wrote it on C#, because it's compiled"; Python is also normally compiled. – Russell Borogove Feb 27 '14 at 3:06 ## 6 Answers I don't know so I'll focus on the code. • Your program is coded upside down. One would expect void Main at the top, with the more specialized code below. • Method names in C# are expected to consistently follow PascalCasing convention. Only your Main method does that, and if you were to adopt a camelCasing convention, userinput would be better off called userInput. • It doesn't feel right that the Count method doesn't infer the number of iterations from the length of the string(s) it's given, and doesn't do anything to verify whether the index is legal, which at first glance seems like asking for an IndexOutOfRangeException. Performance-wise, I think you'll need to factor out the randomness from your tests for any benchmarking to mean anything. Using StringBuilder was a good call. - It is random, but if you run them both, the python is consistently much faster than the C#. Thanks for the tips. I put the methods at the bottom and changed the names. – bobpal Feb 25 '14 at 19:29 Same if you take the creation of the rnd and sb objects outside the loop as @vals as pointed out? I suspect a seeding issue with all the instances of Random you're creating. Possibly you run the program 10K times and it runs 10K times with the same "random" sequence. Also C# is Jit-compiled from IL code, so yeah it's compiled, but to an intermediate language - there's the CLR doing its job, too. Not sure how fair your comparison is. – Mat's Mug Feb 25 '14 at 19:35 YES! the random initializing inside the method was the problem. Thanks, for pointing that out. Stepping through it in the debugger wasn't catching it. And yes, I know about C# and the way it compiles. – bobpal Feb 25 '14 at 20:04 @user2180125 in all fairness, it's really vals' answer that caught the performance issue. If you're accepting my answer for the code review, I'll take it; but if you're accepting my answer for the advice about taking instantiation out of the loop, vals' answer should have the checkmark ;) – Mat's Mug Feb 25 '14 at 21:08 @Mat'sMug Never mind, I should have written a more thorough answer :-) – vals Feb 25 '14 at 21:34 If you want performance, don't create objects in the inner loop:  static string generate(int len) { Random rnd = new Random(); // creating a new object string alpha = "abcdefghijklmnopqrstuvwxyz"; int letterInt; StringBuilder sb = new StringBuilder(); // creating a new object .... }  create them once and reuse them - Ugh. How did I miss that! Good catch! – Mat's Mug Feb 25 '14 at 18:50 The objects are created once every user input, hardly a performance issue... – Uri Agassi Feb 25 '14 at 18:51 @UriAgassi they're not. Objects are created at each iteration of the while loop, which runs after the user input. – Mat's Mug Feb 25 '14 at 19:40 @Phoshi I think that my use of the plural reuse them make you believe that I was suggesting using a pool of objects. My suggestion was much easier; just create one object of class Random and one of class StringBuilder, and them meant the 2 objects. – vals Feb 26 '14 at 17:34 @Andris: "Don't object pool or reuse by default, only do it when there's actually an issue". Random has semantic issues, never mind speed issues, and should never be created in a tight loop. This does not hold for the vast majority of objects, though. – Phoshi Feb 27 '14 at 11:20 To answer the question of why your c# code is so slow. It's this line. According to a profiler ~90% of the execution time is being taken up by recreating the Random object. You'll notice your python code only uses the random rather than recreates it. Random rnd = new Random();  if you change the generate method to:  static Random rnd = new Random(); static string generate(int len) { //generates string of random letters, returns the random string string alpha = "abcdefghijklmnopqrstuvwxyz"; int letterInt; StringBuilder sb = new StringBuilder(); for (int i = 0; i < len; i++) { letterInt = rnd.Next(26); sb.Append(alpha[letterInt]); } return sb.ToString(); }  These changes will show similar perf for both languages. - In your python code you use a character array as your guess. In your C# code you build a StringBuffer instead. Try using a char[] instead. Since you are on Code Review - I'll also give some thoughts about your code: Naming Conventions - C# method naming is PascalCase, and python function naming in snake_case, so - UserInput() and user_input(): respectively. Meaningful names - generate and count do not convey well the meaning of the code in them GenerateRandomString and CountSimilarLetters is better. Same goes for alpha, len, g, s, etc. - You have camelCase and PascalCase confused, but at least you use them right. Though camelCase doesn't use underscores either - it just looks like a camel. – Magus Feb 25 '14 at 19:17 @Magus, fixed, thanks CamelCase can be used for both upper and lower first chars(en.wikipedia.org/wiki/CamelCase), and the pascal_case was a typo... – Uri Agassi Feb 25 '14 at 19:19 I'd look at compiling your regex and having it as a class-level member for optimal reuse. Also lift the random number generator out the same way, as it's never good practice to continually regenerate it. old code:  static string userinput() { //Takes user input, makes sure it is all lowercase letters, returns string string input; while(true) { input = Console.ReadLine(); if (Regex.IsMatch(input, @"^[a-z]+$"))
{
return input;
}
}
}

private static string generate(int len)
{
// generates string of random letters, returns the random string
Random rnd = new Random();
string alpha = "abcdefghijklmnopqrstuvwxyz";
StringBuilder sb = new StringBuilder();
int letterInt;

for (int i = 0; i < len; i++)
{
letterInt = rnd.Next(26);
sb.Append(alpha[letterInt]);
}

return sb.ToString();
}


new code:

    private static readonly Regex regex = new Regex(@"^[a-z]+\$", RegexOptions.Compiled);
private static readonly Random rnd = new Random();

static string userinput()
{
//Takes user input, makes sure it is all lowercase letters, returns string
string input;

while(true)
{
input = Console.ReadLine();

if (regex.IsMatch(input))
{
return input;
}
}
}

private static string generate(int len)
{
// generates string of random letters, returns the random string
const string alpha = "abcdefghijklmnopqrstuvwxyz";
StringBuilder sb = new StringBuilder();
int letterInt;

for (int i = 0; i < len; i++)
{
letterInt = rnd.Next(26);
sb.Append(alpha[letterInt]);
}

return sb.ToString();
}

-
If the strings are 123a56 and 123b56 then your count will be 3 and the OP's count will be 5. – ChrisW Feb 25 '14 at 23:43
@ChrisW dangit, it screws up the "best so far" display. Whoops. Correcting. – Jesse C. Slicer Feb 25 '14 at 23:55

Here's a late commentary on your Python program.

I know no C#. To be honest, though, I'm truly surprised that the C# isn't faster, because what you have written is not how to implement a fast variant in Python.

In Python, you'll want to use Numpy if things are getting slow. In fact, you'll want something like:

"""
This program generates a string of random letters and matches it with the user's string.
It does this until its guess is the same as the user's string.
It also displays closest guess so far and time it took to guess.
"""

import numpy
import time
from string import ascii_lowercase

# Everything is ASCII, which is what the "c" means.
letters = numpy.array(list(ascii_lowercase), dtype="c")

def brute_force(solution):
"""
BRRUUUUTTTEEE FFOOORRRCCCEEEE!!!!

Repeatedly guess at a solution until it matches.
"""

# Convert to char array
solution = numpy.array(list(solution.casefold()), dtype="c")

best = 0
while True:
# Do loads of guesses (100000) at once
guesses = numpy.random.choice(letters, (100000, len(solution)))

# Check all of the characters for equality, and count the number
# of correct for each row
corrects = (guesses == solution).sum(axis=1)

# Gets the highest-so-far at each point
maximums = numpy.maximum.accumulate(corrects)

# Gets how much the maximum increased
changes = numpy.diff(maximums)

# Indexes of the increases
# numpy.where returns a tuple of one element, so unpack it
[when_increased] = numpy.where(changes > 0)
# Need to increase by one, because these are indexes into
# the differences whilst we want indexes into the final array
# for the *increased* (not increasing) elements
when_increased += 1

for index in when_increased:
guess = guesses[index]
correct = corrects[index]

if correct > best:
yield str(guess, encoding="ascii")
best = correct

if correct == len(solution):
return

print("They say if you lock a monkey in a room with a typewriter and enough time,")
print("the monkey would eventually type a poem by Shakespeare")
print("Let's see how well a python does...'")

while True:
print("Enter a word")
print("(5 letters or less is recommended)")
user_input = input()

# Make sure user only inputs letters
if user_input.isalpha():
break

start = time.time()

for solution in brute_force(user_input):
print("The best guess so far is: ", solution)

elapsed_time = time.time() - start

print("Success!")
print("It took ", elapsed_time, " seconds for the python to type ", repr(solution))


It might look more intimidating but there are only ~30 lines of logic there, most of which are trivial.

The basic idea is to make loads of random choices in bulk:

guesses = numpy.random.choice(letters, (100000, len(solution)))


which is fast. This makes a 100000xN matrix, eg. for N=3:

h s l
w t x
a m e
i x t
⋮


Then you can calculate the number correct for each row by comparing each row to the solution (guesses == solution) giving a bool array, and you can sum each row (.sum(axis=1)) to get the number correct.

The extra parts from there (numpy.diff) serve to pretend we did this sequentially, although we did not. It's not relevant in most real-world circumstances, where one can just print the best answer from that bunch.

Overall this is much faster than the original (>10x), and most of the time is spent in numpy.random.choice, implying it's not possible to meaningfully speed up further without replacing the high-quality random numbers that Numpy generates.

So don't go thinking that Python is slow because it's interpreted and dynamic. It's perfectly possible to have a high-quality implementation run fast with these kinds of programs.

Since this is Code Review, I'll also point out some things that you should be improving on:

• Docstrings, not comments.

Write

"""
This program generates a string of random letters and matches it with the user's string.
It does this until its guess is the same as the user's string.
It also displays closest guess so far and time it took to guess.
"""


instead of

# This program generates a string of random letters and matches it with the user's string.
# It does this until its guess is the same as the user's string.
# It also displays closest guess so far and time it took to guess.


This might sound meaninglessly fussy, but it helps introspection.

• Reduce your usage of globals. Functions should (almost) never share state; it should be passed between them. Trust me on this. It means that you can reuse them and move them around without worrying about dependencies, for one. It also allows local changes to stay local.

• Try and clump IO in one place. If you look at my variant, all the printing is localized and the logic is separated. This modularizes the program, so you can move things around and mess with logic without having "things" in your way all of the time.

• random.seed() with no value given is pointless here. It should only be used after random.seed(some_value) to remove the seed.

• This code:

done = False
while not done:
if ...:
done = True


is much better written

while True:
if ...:
break


Some people disagree. They are wrong.

• Things like

for c in range(size):
guess[c] = random.choice(alpha)


where you're visiting each item in turn, are much better written without indexes, like:

guess[:] = [random.choice(alpha) for _ in range(size)]


although this really should be

def generate(size):
"""Generate random letter for each character of string."""
return [random.choice(alpha) for _ in range(size)]


if you use my prior advice.

The same goes for count, which can be

sum(g==s for g, s in zip(guess, solution))

• Don't meaninglessly preallocate values, like guess = [""] * size. It just hides bugs.

If you ever find you need to do that, you're probably not following my advice about not using globals.

-