Алгоритм VersionString (например, "1.0.2") интерфейса icomparer


Для проекта, Я работаю, мне нужно сравнить строки версии, где:

  • версия строки состоят только из цифр и сроков
  • версия строки состоят из произвольного количества сегментов (крупных.незначительные, manjor.незначительные.строительство и т. д.)
  • 1.0 эквивалентно 1.0.0, и т. д.

Пожалуйста, обеспечить обратную связь по вопросам производительности и стиля.

Вот мой выстрел:

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;
    }
}

И два быстрых модульных тестов (с использованием должна.Владеет библиотеки:

    [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);
    }


5211
4
задан 18 ноября 2011 в 05:11 Источник Поделиться
Комментарии
3 ответа

Я слегка изменил метод сравнения, делая его более читабельным (ИМО) с помощью анонимного типа с именованными свойствами и извлекать два вспомогательных метода.

Я не проверяю результат метод tryparse больше, поскольку результатом является 0 для неудачных преобразований.
По поводу производительности: на моей машине, ваша версия работает десять тысяч итераций в ~400ms, а мой, мне кажется, сбрить приблизительно четверть, выполнив одинаковое количество итераций в ~300мс.

Это должно быть потому, что я перенес разбор версий из петли.
Я измерил это с помощью системы.Диагностика.Секундомер.

Редактировать: также, обратите внимание на производительность... микро-оптимизаций, таких как те, что я сделала это бессмысленно , если вы на самом деле определили реальное узкое место в вашем коде. Мне показалось, что эти упрощенные критерии, чтобы убедиться, что я не делал свою реализацию медленнее при получении его в более выразительной форме.

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;
}

Эта адаптированная конвертер возвращает те же результаты тестов, как ваш оригинальный одного, хотя я не пытался проверить его более тщательно - может, кто-то может увидеть крайний случай? ;-)

2
ответ дан 26 декабря 2011 в 07:12 Источник Поделиться

Вопросы производительности для своей реализации незначительны, и я думаю, что это, вероятно, будет пустой тратой времени и принесет в жертву читабельности, чтобы попытаться оптимизировать его дальше, но ради дискуссии я указываю на то, что я думаю, что вещи в настоящем Кодексе, которые влияют на производительность больше всего.


  1. Вы можете использовать математику.Макс(xparts.Длина, yparts.Длина) с целью определения максимальной длины между двумя массивами. Реализация неоправданно выделяет массив, так что вы можете вызвать максимум метод расширения для IEnumerable в.

  2. Для каждой строки (X и y) вы выделить массив для того, чтобы хранить каждую часть строки при вызове х.Сплит('.') и г.Сплит('.'). Я не вижу в этом проблемы, потому что это очень простой подход. Однако, если вы почувствовали, что вам нужно, чтобы избежать этого, то вы могли бы написать более сложная реализация с помощью вызовов метода indexOf и подстроки. Единственное преимущество это дало бы вам, что это позволило бы избежать выделения массива, но каждый вызов подстроке бы еще выделить новый строковый объект для каждой строки. Я предполагаю, что супер-производительным реализация предполагает какой-то типа int32.Метод tryparse метод, который принимает строковый параметр вместе с startindex и длина параметра; этот метод теоретически разобрать значение int32 из подстроки без необходимости создавать дополнительную строку объект.

Альтернативная реализация, которая использует метод indexOf и подстроки методов приведен ниже. Хотя некоторые сырой бенчмаркинга показывает, что эта реализация работает быстрее, я не уверен, что я хотел бы использовать его, потому что это сложнее.

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;
}

1
ответ дан 27 декабря 2011 в 05:12 Источник Поделиться

Две заметки о тестах:

1, я бы извлечь следующие две строки в метод:

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

Они одинаковы в обоих испытаниях. В assertSortedEquals(exptectedArray, inputArray) тоже будет хорошо. Это было сделано методы тестов одна-вкладыши, которые было бы легче читать.

2, имеющие эти тесты-это хорошо, но если у вас есть только эти два теста это не поможет локализация дефекта слишком много. Это было бы более эффективным, если вы напишите несколько тестов:


  • testDifferentMinorVersion: 1.0 < 1.1

  • testDifferentMinorVersionWithZerobuildnumber: 1.0 == 1.0.0

  • testDifferentMinorVersionWithMoredecimals: 1.9 < 1.10

  • testDifferentMajorVersion: 1.0 < 2.0

Я вижу, что некоторые из них покрываются вашего текущего тесты, но если есть ошибка в логике вам не будет знать, какая часть сломана, вы просто получите сообщение об ошибке с двух разных списка. В противном случае, вы могли бы получить более подробное сообщение об ошибке, которое говорит, например, 1.9 должна быть не менее 1.10, но в настоящее время он не работает. Несколько пользовательских утверждение методов может помочь много для этих тестов: assertBigger(версия1, версия2), assertSameVersion(версия1, версия2)`.

0
ответ дан 27 декабря 2011 в 07:12 Источник Поделиться