7
\$\begingroup\$

Inspired by Sam's question (Brute-force string generator) and rolfl's really short version of the algorithm I started to experiment with a different approach and created one that seems to run a little bit faster (about 40-50ms for a string of length 4). As it doesn't really optimize the orginal algorithm but is a complete different one I thought I let you review it.

Actually it's really simple although it requires signifficantly more code then the original example and expecially the opmizided one.

To generate the permutations I wrote an Odometer class with a RolloverCounter that works like an odometer in a car. Each odometer gear-value is an index in the charSet array so based on these indexes I create a string.

It doesn't run in parallel yet but I made some preparations to implement it later. The RolloverCounter and the Odometer can start at some random number and continue from there so the whole range of possible permutations can be devided into sub-odometers and run on different threads.

I also shortened the char array to be generated from ascii codes and allowed the user to specify which character set he would like to use.


CharSets

[Flags]
public enum CharSets
{
    Lowercase,
    Uppercase,
    Numbers,
    Special
}

RolloverCounter

public class RolloverCounter
{
    private readonly int _min;
    private readonly int _max;
    private int _value;

    public RolloverCounter(int min, int max, int value)
    {
        _min = min;
        _max = max;
        _value = value;
    }

    public RolloverCounter(int min, int max) : this(min, max, min)
    {
    }

    public int Value { get { return _value; } }

    // increases the counter and returns true if rolledover
    public bool Increase()
    {
        if (++_value < _max)
        {
            return false;
        }
        _value = _min;
        return true;
    }

    // makes things easier
    public static explicit operator int (RolloverCounter rolloverCounter)
    {
        return rolloverCounter._value;
    }
}

Odometer

public class Odometer
{
    private readonly int _gearCount;
    private readonly int _min;
    private readonly int _max;

    public Odometer(int gearCount, int min, int max, params int[] gearValues)
    {
        _gearCount = gearCount;
        _min = min;
        _max = max;
        Gears =
            gearValues.Length > 0
            // start at the specified state - for multithreading
            ? gearValues.Select(x => new RolloverCounter(min, max, x)).ToList()
            // start at min
            : new List<RolloverCounter>(gearCount) { new RolloverCounter(min, max) };
        Max = max;
    }

    public int Max { get; private set; }

    public List<RolloverCounter> Gears { get; private set; }

    // increases the odometer and returns true if rolledover
    public bool Increase()
    {
        var gear = 0;
        while (gear < Gears.Count && Gears[gear].Increase())
        {
            gear++;

            // add new gear
            if (Gears.Count - 1 < gear)
            {
                Gears.Add(new RolloverCounter(_min, _max, _min));
                break;
            }
        };

        // rollover
        return gear == _gearCount;
    }
}

StringGenerator

public class StringGenerator
{
    private readonly char[] _charSet;

    public StringGenerator(CharSets charSets = CharSets.Lowercase)
    {
        var chars = Enumerable.Empty<char>();

        if (charSets.HasFlag(CharSets.Lowercase))
        {
            chars = chars.Concat(Enumerable.Range(97, 122 - 97 + 1).Select(c => (char)c));
        }

        if (charSets.HasFlag(CharSets.Uppercase))
        {
            chars = chars.Concat(Enumerable.Range(65, 90 - 65 + 1).Select(c => (char)c));
        }

        if (charSets.HasFlag(CharSets.Numbers))
        {
            chars = chars.Concat(Enumerable.Range(48, 57 - 48 + 1).Select(c => (char)c));
        }

        _charSet = chars.ToArray();

        // shorter char set for debugging
        //charSet = Enumerable.Range(97, 99 - 97 + 1).Select(c => (char)c).ToArray();
    }

    public IEnumerable<string> GenerateStrings(int count)
    {
        // todo: here I'll need to calc the number of permutations and split the
        // the odometer into ranges


        var odometer = new Odometer(count, 0, _charSet.Length);
        do
        {                
            // this loop seems to be the fastest ways to generate a string
            // I tested a few other options like:
            // new string(odometer.Gears.Select(x => _charSet[(int)x]).ToArray())
            // but they were all much slower

            var result = new StringBuilder(odometer.Gears.Count);
            foreach (var gear in odometer.Gears)
            {
                result.Append(_charSet[(int)gear]);
            }
            yield return result.ToString();
        } while (!odometer.Increase());
    }
}

Test code

var stringCount = 0;
StopwatchHelper.Measure(() =>
{
    var stringGenerator = new StringGenerator(CharSets.Lowercase | CharSets.Numbers);
    var maxStringLength = 4;
    var strings = stringGenerator.GenerateStrings(maxStringLength).ToList();
    stringCount = strings.Count;
},
sw => Console.WriteLine($"       My: {sw.ElapsedMilliseconds} ms"));

// measures @rolfl's optimized version
StopwatchHelper.Measure(() =>
{
    var strings2 = new List<string>();
    var bruteForce3 = new BruteForce3();
    for (var i = 0; i < stringCount; i++)
    {
        var generatedString = bruteForce3.GenerateString();
        strings2.Add(generatedString);
    }
},
sw => Console.WriteLine($"Optimized: {sw.ElapsedMilliseconds} ms"));

Console.ReadKey();

Helper

public static Stopwatch Measure(Action measureAction, Action<Stopwatch> resultAction = null)
{
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    measureAction();
    stopwatch.Stop();
    resultAction?.Invoke(stopwatch);
    return stopwatch;
}
\$\endgroup\$
4
\$\begingroup\$

someone suggested we should deal with the growing number of Zombies...

Easy Performance Win

The performance measurement is wholly inadequate, and when I run your code as provided it tells me that your code is slower than that provided by Rolfl.

Using BenchmarkDotNet to get sensible measurements (with the proviso that they are running on my machine, at the same time as it is doing a lot of other work), I can agree your method is faster than that provided by Rolfl, running in ~1.8 s rather than ~1.5 s for the 4-length string test.

There is, however, an easy way to do better: you shouldn't be initialising a new StringBuilder for each word: create one and clear it as you need. This tiny change halves the runtime for strings of length 4, giving ~700 ms.

// this loop seems to be the fastest ways to generate a string

You must have missed the most obvious option: fill an array! There are 2 obvious ways to do this: create a big array and use the appropriate overload of String..ctor (1), or create an array of the right length when we need it (2). Neither seems to give any real improvement over the StringBuilder for these short strings, certainly not enough to accept the reduction in readability and reusability (the StringBuilder method can be easily adapted to work with strings rather than chars, which will be important if non-ASCII-characters are needed) without better measurements.

Table of measurements:

|        Method | StringLength |        Mean |      Error |     StdDev |
|-------------- |------------- |------------:|-----------:|-----------:|
|         Rolfl |            3 |    36.57 ms |  0.7292 ms |  1.9590 ms |
|       T3chb0t |            3 |    32.51 ms |  0.6764 ms |  1.9732 ms |
| StringBuilder |            3 |    12.51 ms |  0.2493 ms |  0.7154 ms |
|        Array1 |            3 |    11.20 ms |  0.2233 ms |  0.5882 ms |
|        Array2 |            3 |    10.65 ms |  0.2538 ms |  0.7444 ms |
|         Rolfl |            4 | 1,849.73 ms | 36.1277 ms | 56.2465 ms |
|       T3chb0t |            4 | 1,472.04 ms | 28.1790 ms | 68.0553 ms |
| StringBuilder |            4 |   682.75 ms | 16.3137 ms | 48.1013 ms |
|        Array1 |            4 |   623.12 ms | 14.8381 ms | 43.2836 ms |
|        Array2 |            4 |   679.26 ms | 23.1619 ms | 67.5642 ms |

Test code: gist.

Char Sets Ranges

The StringGerator(CharSets) constructor could be made much tidier by using a List<T> to accumulate the results (rather than shuffling IEnumerables), and using a helper method to create Ascii Ranges:

private static IEnumerable<char> AsciiRange(char start, char end)
{
    if (end < start)
        throw new ArgumentException("The end character must not occur before the start character");
    // TODO: bounds checks are probably in order

    return Enumerable.Range(start, end - start + 1).Select(c => (char)c);
}

public StringGenerator(CharSets charSets = CharSets.Lowercase)
{
    var chars = new List<char>();

    if (charSets.HasFlag(CharSets.Lowercase))
    {
        chars.AddRange(AsciiRange('a', 'z'));
    }

    if (charSets.HasFlag(CharSets.Uppercase))
    {
        chars.AddRange(AsciiRange('A', 'Z'));
    }

    if (charSets.HasFlag(CharSets.Numbers))
    {
        chars.AddRange(AsciiRange('0', '9'));
    }

    _charSet = chars.ToArray();
}

This is much more maintainable, as there is reduced repetition, and you don't need an ASCII table at hand to make modifications.

Odometer is not reusable

I also don't like that Increase creates a another RolloverCounter at the very end of the enumeration: it is basically ignoring _gearCount. It has the consequence that when you 'reuse' the odometer, you end up with another gear on the end, and if you use it a few more times, you end up with another gear on the end...

For example, using just var _charSet = new char[] { 'a', 'b', 'c' };, the time you get the correct output:

a, b, c, aa, ab, etc.

using it again, you get:

aaaa, baaa, caaa, etc.

And again, the last a becomes a b... it's a total nightmare. It needs something like this on the end:

if (gear == _gearCount)
{
    // rollover
    Gears.RemoveRange(1, Gears.Count - 1);
    return true;
}
else
{
    return false;
}

A check to avoid the last gear being added in the first place would avoid an allocation which takes the list over its initial capacity:

if (gear < _gearCount)
    Gears.Add(new RolloverCounter(_min, _max, _min));

I don't know if reusability is a goal, but if it isn't then it should be documented. Honestly, the behaviour seems a bit weird from the outset, having gears introduced over-time.

Misc

  • I would be strongly inclined to specify the values for the CharSets enum since you are using them as default parameters (their values become part of the API, and so changing them becomes a breaking change).

  • The constructors for RolloverCounter could obvious do with some bounds checking and documentation (e.g. explaining that the 'default' value is the min, and the max is an exclusive upper-bound).

  • I don't like that Odometer.Gears is public, given it is mutable. I'd be strongly inclined to provide a readonly-view of it; however, unfortunately, this does seem to degrade performance.

  • Odometer.Max is redundant with Odometer._max; I can't see any reason not to make it Max => _max. It doesn't make much sense to me to provide Value and Max but not Min.

  • I'd feel compelled to rename RolloverCounter.Increase to Increment or Advance, but that's pretty subjective. Increase feels like it should have a parameter to determine how much by which to increase (which would be a fun extension).

\$\endgroup\$
  • \$\begingroup\$ your code is slower than that provided by Rolfl - but yours is the only review so far... are you sure you wanted to post this answer here? It looks like it's partially on- and off-topic haha \$\endgroup\$ – t3chb0t Jul 24 at 12:26
  • 1
    \$\begingroup\$ @t3chb0t I'm sorry, I don't follow! I believe your code is faster that Rolfl's, it's just that when I first ran it with your basic measurement, I got the opposite result! (presumably because it runs yours first, and rather than swap them around I just went straight to BenchmarkDotNet) \$\endgroup\$ – VisualMelon Jul 24 at 12:30
  • \$\begingroup\$ oh, my bad... I now see that I've linked his answer in my question and you are referring to that, sorry, I fogot that ;-) I like the AsciiRange thing. \$\endgroup\$ – t3chb0t Jul 24 at 12:31
  • \$\begingroup\$ Did you check the link about the Zombies? \$\endgroup\$ – Heslacher Jul 26 at 10:36
  • \$\begingroup\$ @Heslacher yes; I'm not sure I follow? \$\endgroup\$ – VisualMelon Jul 26 at 10:56

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.