4
\$\begingroup\$

For a project I'm working on, I need to compare version strings where:

  • version strings are composed only of numbers and periods
  • version strings are made up of an arbitrary number of segments (major.minor, manjor.minor.build, etc)
  • 1.0 is equivalent to 1.0.0, etc.

Please provide feedback on performance considerations or style.

Here's my shot at it:

public class VersionStringComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == y) return 0;

        var xparts = x.Split('.');
        var yparts = y.Split('.');

        var length = new[] {xparts.Length, yparts.Length}.Max();

        for (var i = 0; i < length; i++)
        {
            int xint;
            int yint;

            if (!Int32.TryParse(xparts.ElementAtOrDefault(i), out xint)) xint = 0;
            if (!Int32.TryParse(yparts.ElementAtOrDefault(i), out yint)) yint = 0;

            if (xint > yint) return 1;
            if (yint > xint) return -1;
        }

        //they're equal value but not equal strings, eg 1 and 1.0
        return 0;
    }
}

And two quick unit tests (using the Should.Fluent library:

    [TestMethod]
    public void VersionStringComparerSortsMajorAndMinorVersionString()
    {
        var versions = new[]{"1.5","1.0","2.0","1.0"};
        var versionStringComparer = new ReleaseGateway.Util.VersionStringComparer();

        var sorted = versions.OrderBy(x => x, versionStringComparer).ToArray();

        var expected = new[] {"1.0", "1.0", "1.5", "2.0"};
        sorted.Should().Equal(expected);
    }

    [TestMethod]
    public void VersionStringComparerSortsArbitraryRadixVersionStrings()
    {
        var versions = new[] { "1.5.4", "1.7", "1.0", "1","1.4" };
        var versionStringComparer = new ReleaseGateway.Util.VersionStringComparer();

        var sorted = versions.OrderBy(x => x, versionStringComparer).ToArray();

        var expected = new[] { "1.0", "1", "1.4", "1.5.4", "1.7" };
        sorted.Should().Equal(expected);
    }
\$\endgroup\$
  • 10
    \$\begingroup\$ Uhh, what's wrong with using Version.Parse to parse it and comparing Version instances? \$\endgroup\$ – Jeff Mercado Nov 19 '11 at 7:55
2
\$\begingroup\$

I adjusted the compare method slightly, making it more readable (IMO) through the use of an Anonymous type with named properties and by extracting two helper methods.

I'm not checking the result of TryParse anymore since the result is 0 for failed conversions.
Regarding performance: on my machine, your version runs ten thousand iterations in ~400ms, while mine seems to shave off around one fourth, running the same amount of iterations at ~300ms.

This should be because I moved the parsing of the versions out of the loop.
I measured this using a System.Diagnostics.Stopwatch.

EDIT: A note on performance... micro-optimizations such as the ones I've done are meaningless unless you have actually identified a real bottleneck in your code. I only ran these simplified benchmarks to make sure I wasn't making your implementation slower while getting it into a more expressive form.

public int Compare(string x, string y)
{
    if (x == y) return 0;
    var version = new { First = GetVersion(x), Second = GetVersion(y) };
    int limit = Math.Max(version.First.Length, version.Second.Length);
    for (int i = 0; i < limit; i++)
    {
        int first = version.First.ElementAtOrDefault(i);
        int second = version.Second.ElementAtOrDefault(i);
        if (first > second) return 1;
        if (second > first) return -1;
    }
    return 0;
}

private int[] GetVersion(string version)
{
    return (from part in version.Split('.')
            select Parse(part)).ToArray();
}

private int Parse(string version)
{
    int result;
    int.TryParse(version, out result);
    return result;
}

This adapted converter returns the same test results as your original one - though I haven't tried to test it more thoroughly - maybe someone can spot an edge case? ;-)

\$\endgroup\$
1
\$\begingroup\$

The performance considerations for your implementation are negligible, and I think it would probably be a waste of time and would sacrifice readability to try to optimize it any further, but for the sake of discussion I'll point out what I think are the things in this code that affect performance the most.

  1. You can use Math.Max(xparts.Length, yparts.Length) in order to determine the max length between the two arrays. Your implementation unnecessarily allocates an array so that you can call the Max extension method for IEnumerable<int>.

  2. For each string (x and y) you are allocating an array in order to store each part of the string when you call x.Split('.') and y.Split('.'). I don't see this as a problem, because it is a very straightforward approach. However, if you felt that you needed to avoid that, then you could write a more complicated implementation using calls to IndexOf and Substring. The only benefit this would give you is that it would avoid allocating the array, but each call to Substring would still allocate a new string object for each part of the string. I suppose a super-performant implementation would involve some kind of Int32.TryParse method that accepts a string parameter along with a startIndex and length parameter; this method would theoretically parse an Int32 value from a substring without having to create an additional string object.

An alternative implementation that utilizes the IndexOf and Substring methods is shown below. Although some crude benchmarking indicates that this implementation is faster, I'm not sure that I would use it because it is more complicated.

public static class StringExtensions
{
    public static bool TryParseSubstringInt32(this string input, int startIndex, int length, out int value)
    {
        // TODO: replace this code with a more efficient version that parses an Int32 value from a substring without allocating a new string
        string s = input.Substring(startIndex, length);
        return int.TryParse(s, out value);
    }
}

public class VersionStringComparer : IComparer<string>
{
    static int GetPart(string version, ref int currentIndex, ref int indexOfDot)
    {
        int part;

        if (indexOfDot < 0)
        {
            if (!version.TryParseSubstringInt32(currentIndex, version.Length - currentIndex, out part))
                part = 0;

            currentIndex = version.Length;
        }
        else
        {
            if (!version.TryParseSubstringInt32(currentIndex, indexOfDot - currentIndex, out part))
                part = 0;

            currentIndex = indexOfDot + 1;
            indexOfDot = version.IndexOf('.', currentIndex);
        }

        return part;
    }

    public int Compare(string x, string y)
    {
        if (x == y) return 0;

        int xCurrentIndex = 0;
        int yCurrentIndex = 0;

        int xIndexOfDot = x.IndexOf('.', xCurrentIndex);
        int yIndexOfDot = y.IndexOf('.', yCurrentIndex);

        int xPart;
        int yPart;

        int xLength = x.Length;
        int yLength = y.Length;

        while (xCurrentIndex < x.Length && yCurrentIndex < y.Length)
        {
            xPart = GetPart(x, ref xCurrentIndex, ref xIndexOfDot);
            yPart = GetPart(y, ref yCurrentIndex, ref yIndexOfDot);

            if (xPart > yPart) return 1;
            if (xPart < yPart) return -1;
        }

        if (xCurrentIndex < x.Length)
        {
            do
            {
                xPart = GetPart(x, ref xCurrentIndex, ref xIndexOfDot);

                if (xPart > 0) return 1;
                if (xPart < 0) return -1;

            } while (xCurrentIndex < x.Length);
        }
        else if (yCurrentIndex < y.Length)
        {
            do
            {
                yPart = GetPart(y, ref yCurrentIndex, ref yIndexOfDot);

                if (yPart > 0) return -1;
                if (yPart < 0) return 1;

            } while (yCurrentIndex < y.Length);
        }

        return 0;
    }
\$\endgroup\$
  • \$\begingroup\$ I'll stress it here, again. It makes absolutely no sense to do such optimizations before you have determined for a fact whether comparing two versions really is the bottleneck in your system (hint: it isn't.) It is seldom a good idea to sacrifice readability for a micro-optimization. Such measures will lead to an utterly unmaintainable code-base. \$\endgroup\$ – Adam Dec 27 '11 at 20:48
  • \$\begingroup\$ Agreed. The first sentence of my answer says that it would probably be a waste of time to optimize this code. \$\endgroup\$ – Dr. Wily's Apprentice Dec 27 '11 at 22:37
  • \$\begingroup\$ Sorry if this sounded as if I hadn't read your answer, of course I have; and I was very grateful that you included the warning, but I wanted to but a bit more emphasis on it for other readers. \$\endgroup\$ – Adam Dec 27 '11 at 22:39
  • \$\begingroup\$ @codesparkle - my apologies as well for the terseness of my comment; I wanted to clarify my position as well that I am in agreement. Appreciate your comment stressing the importance of addressing performance issues by identifying actual bottlenecks. \$\endgroup\$ – Dr. Wily's Apprentice Dec 28 '11 at 14:07
0
\$\begingroup\$

Two notes about the tests:

1, I'd extract out the following two lines to a method:

var versionStringComparer = 
    new ReleaseGateway.Util.VersionStringComparer();
var sorted = 
    versions.OrderBy(x => x, versionStringComparer).ToArray();

They're the same in both tests. An assertSortedEquals(exptectedArray, inputArray) also would be fine. It would made your test methods one-liners which would be easier to read.

2, Having these tests is good, but if you have only these two tests it doesn't help defect localization too much. It would be more effective if you write a few more tests:

  • testDifferentMinorVersion: 1.0 < 1.1
  • testDifferentMinorVersionWithZeroBuildNumber: 1.0 == 1.0.0
  • testDifferentMinorVersionWithMoreDecimals: 1.9 < 1.10
  • testDifferentMajorVersion: 1.0 < 2.0

I see that some of these are covered by your current tests but if there was a bug in the logic you would not know which part is broken, you just get an error with two different list. Otherwise, you could get a more detailed error message which says, for example, 1.9 should be less than 1.10, but currently it doesn't work. A few custom assertion methods could help a lot for these tests: assertBigger(version1, version2), assertSameVersion(version1, version2)`.

\$\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.