Естественный порядок сортировки в C #

Question

Кто-нибудь имеет хороший ресурс или предоставляет пример сортировки естественного порядка в C # для массива FileInfo? Я реализую интерфейс IComparer в своем роде.

Answer 1

Я на самом деле реализовал это как метод расширения на StringComparer, чтобы вы могли сделать, например:

• StringComparer.CurrentCulture.WithNaturalSort() или
• StringComparer.OrdinalIgnoreCase.WithNaturalSort().

Полученный IComparer<string> может использоваться во всех местах, таких как OrderBy, OrderByDescending, ThenBy, ThenByDescending, SortedSet<string> и т. Д. И вы все еще можете легко настроить чувствительность к регистру, культуру и т. Д.

Реализация довольно тривиальна, и она должна довольно хорошо работать даже на больших последовательностях.

---

Я также опубликовал его как крошечный пакет NuGet , так что вы можете просто сделать:

Install-Package NaturalSort.Extension

Код, включающий комментарии к документации XML и набор тестов , доступен в репозитории NaturalSort.Extension GitHub .

---

Весь код такой (если вы еще не можете использовать C # 7, просто установите пакет NuGet):

public static class StringComparerNaturalSortExtension
{
    public static IComparer<string> WithNaturalSort(this StringComparer stringComparer) => new NaturalSortComparer(stringComparer);

    private class NaturalSortComparer : IComparer<string>
    {
        public NaturalSortComparer(StringComparer stringComparer)
        {
            _stringComparer = stringComparer;
        }

        private readonly StringComparer _stringComparer;
        private static readonly Regex NumberSequenceRegex = new Regex(@"(\d+)", RegexOptions.Compiled | RegexOptions.CultureInvariant);
        private static string[] Tokenize(string s) => s == null ? new string[] { } : NumberSequenceRegex.Split(s);
        private static ulong ParseNumberOrZero(string s) => ulong.TryParse(s, NumberStyles.None, CultureInfo.InvariantCulture, out var result) ? result : 0;

        public int Compare(string s1, string s2)
        {
            var tokens1 = Tokenize(s1);
            var tokens2 = Tokenize(s2);

            var zipCompare = tokens1.Zip(tokens2, TokenCompare).FirstOrDefault(x => x != 0);
            if (zipCompare != 0)
                return zipCompare;

            var lengthCompare = tokens1.Length.CompareTo(tokens2.Length);
            return lengthCompare;
        }

        private int TokenCompare(string token1, string token2)
        {
            var number1 = ParseNumberOrZero(token1);
            var number2 = ParseNumberOrZero(token2);

            var numberCompare = number1.CompareTo(number2);
            if (numberCompare != 0)
                return numberCompare;

            var stringCompare = _stringComparer.Compare(token1, token2);
            return stringCompare;
        }
    }
}

Answer 2

Вот относительно простой пример, который не использует P / Invoke и избегает какого-либо выделения во время выполнения.

internal sealed class NumericStringComparer : IComparer<string>
{
    public static NumericStringComparer Instance { get; } = new NumericStringComparer();

    public int Compare(string x, string y)
    {
        // sort nulls to the start
        if (x == null)
            return y == null ? 0 : -1;
        if (y == null)
            return 1;

        var ix = 0;
        var iy = 0;

        while (true)
        {
            // sort shorter strings to the start
            if (ix >= x.Length)
                return iy >= y.Length ? 0 : -1;
            if (iy >= y.Length)
                return 1;

            var cx = x[ix];
            var cy = y[iy];

            int result;
            if (char.IsDigit(cx) && char.IsDigit(cy))
                result = CompareInteger(x, y, ref ix, ref iy);
            else
                result = cx.CompareTo(y[iy]);

            if (result != 0)
                return result;

            ix++;
            iy++;
        }
    }

    private static int CompareInteger(string x, string y, ref int ix, ref int iy)
    {
        var lx = GetNumLength(x, ix);
        var ly = GetNumLength(y, iy);

        // shorter number first (note, doesn't handle leading zeroes)
        if (lx != ly)
            return lx.CompareTo(ly);

        for (var i = 0; i < lx; i++)
        {
            var result = x[ix++].CompareTo(y[iy++]);
            if (result != 0)
                return result;
        }

        return 0;
    }

    private static int GetNumLength(string s, int i)
    {
        var length = 0;
        while (i < s.Length && char.IsDigit(s[i++]))
            length++;
        return length;
    }
}

Он не игнорирует ведущие нули, поэтому 01 следует после 2.

Соответствующий юнит-тест:

public class NumericStringComparerTests
{
    [Fact]
    public void OrdersCorrectly()
    {
        AssertEqual("", "");
        AssertEqual(null, null);
        AssertEqual("Hello", "Hello");
        AssertEqual("Hello123", "Hello123");
        AssertEqual("123", "123");
        AssertEqual("123Hello", "123Hello");

        AssertOrdered("", "Hello");
        AssertOrdered(null, "Hello");
        AssertOrdered("Hello", "Hello1");
        AssertOrdered("Hello123", "Hello124");
        AssertOrdered("Hello123", "Hello133");
        AssertOrdered("Hello123", "Hello223");
        AssertOrdered("123", "124");
        AssertOrdered("123", "133");
        AssertOrdered("123", "223");
        AssertOrdered("123", "1234");
        AssertOrdered("123", "2345");
        AssertOrdered("0", "1");
        AssertOrdered("123Hello", "124Hello");
        AssertOrdered("123Hello", "133Hello");
        AssertOrdered("123Hello", "223Hello");
        AssertOrdered("123Hello", "1234Hello");
    }

    private static void AssertEqual(string x, string y)
    {
        Assert.Equal(0, NumericStringComparer.Instance.Compare(x, y));
        Assert.Equal(0, NumericStringComparer.Instance.Compare(y, x));
    }

    private static void AssertOrdered(string x, string y)
    {
        Assert.Equal(-1, NumericStringComparer.Instance.Compare(x, y));
        Assert.Equal( 1, NumericStringComparer.Instance.Compare(y, x));
    }
}

Answer 3

Вдохновленный решением Майкла Паркера, вот реализация IComparer, которую вы можете использовать для любого из методов заказа linq:

private class NaturalStringComparer : IComparer<string>
{
    public int Compare(string left, string right)
    {
        int max = new[] { left, right }
            .SelectMany(x => Regex.Matches(x, @"\d+").Cast<Match>().Select(y => (int?)y.Value.Length))
            .Max() ?? 0;

        var leftPadded = Regex.Replace(left, @"\d+", m => m.Value.PadLeft(max, '0'));
        var rightPadded = Regex.Replace(right, @"\d+", m => m.Value.PadLeft(max, '0'));

        return string.Compare(leftPadded, rightPadded);
    }
}

Answer 4

Расширяя пару предыдущих ответов и используя методы расширения, я пришел к следующему, у которого нет предостережений от потенциального множественного перечислимого перечисления или проблем производительности, связанных с использованием нескольких объектов регулярных выражений или вызовом регулярных выражений Излишне, как говорится, он использует ToList (), который может свести на нет преимущества в больших коллекциях.

Селектор поддерживает универсальную типизацию, позволяющую назначать любому делегату, элементы в исходной коллекции изменяются селектором, а затем преобразуются в строки с помощью ToString ().

    private static readonly Regex _NaturalOrderExpr = new Regex(@"\d+", RegexOptions.Compiled);

    public static IEnumerable<TSource> OrderByNatural<TSource, TKey>(
        this IEnumerable<TSource> source, Func<TSource, TKey> selector)
    {
        int max = 0;

        var selection = source.Select(
            o =>
            {
                var v = selector(o);
                var s = v != null ? v.ToString() : String.Empty;

                if (!String.IsNullOrWhiteSpace(s))
                {
                    var mc = _NaturalOrderExpr.Matches(s);

                    if (mc.Count > 0)
                    {
                        max = Math.Max(max, mc.Cast<Match>().Max(m => m.Value.Length));
                    }
                }

                return new
                {
                    Key = o,
                    Value = s
                };
            }).ToList();

        return
            selection.OrderBy(
                o =>
                String.IsNullOrWhiteSpace(o.Value) ? o.Value : _NaturalOrderExpr.Replace(o.Value, m => m.Value.PadLeft(max, '0')))
                     .Select(o => o.Key);
    }

    public static IEnumerable<TSource> OrderByDescendingNatural<TSource, TKey>(
        this IEnumerable<TSource> source, Func<TSource, TKey> selector)
    {
        int max = 0;

        var selection = source.Select(
            o =>
            {
                var v = selector(o);
                var s = v != null ? v.ToString() : String.Empty;

                if (!String.IsNullOrWhiteSpace(s))
                {
                    var mc = _NaturalOrderExpr.Matches(s);

                    if (mc.Count > 0)
                    {
                        max = Math.Max(max, mc.Cast<Match>().Max(m => m.Value.Length));
                    }
                }

                return new
                {
                    Key = o,
                    Value = s
                };
            }).ToList();

        return
            selection.OrderByDescending(
                o =>
                String.IsNullOrWhiteSpace(o.Value) ? o.Value : _NaturalOrderExpr.Replace(o.Value, m => m.Value.PadLeft(max, '0')))
                     .Select(o => o.Key);
    }

Answer 5

Позвольте мне объяснить мою проблему и то, как я смог ее решить.

Проблема: - Сортировка файлов на основе FileName из объектов FileInfo, которые извлекаются из Справочника.

Решение: - Я выбрал имена файлов из FileInfo и обрезал ".png" часть имени файла. Теперь просто выполните List.Sort (), который сортирует имена файлов в порядке естественной сортировки. На основании моего тестирования я обнаружил, что наличие .png портит порядок сортировки. Посмотрите на приведенный ниже код

var imageNameList = new DirectoryInfo(@"C:\Temp\Images").GetFiles("*.png").Select(x =>x.Name.Substring(0, x.Name.Length - 4)).ToList();
imageNameList.Sort();

Answer 6

Если ваш конечный код предназначен для Интернета (ASP.NET и т. Д.), То естественную сортировку можно получить с помощью функции JavaScript localCampare

'10'.localeCompare('2', undefined, {numeric: true, sensitivity: 'base'})

https://stackoverflow.com/a/38641281/952018

Answer 7

Нам нужна была естественная сортировка для работы с текстом по следующей схеме:

"Test 1-1-1 something"
"Test 1-2-3 something"
...

Почему-то, когда я впервые посмотрел на SO, я не нашел этот пост и реализовал наш собственный. По сравнению с некоторыми из представленных здесь решений, хотя и схожими по концепции, оно может быть более простым и понятным. Тем не менее, хотя я и пытался взглянуть на узкие места в производительности, он все еще намного медленнее, чем стандартная OrderBy().

Вот метод расширения, который я реализую:

public static class EnumerableExtensions
{
    // set up the regex parser once and for all
    private static readonly Regex Regex = new Regex(@"\d+|\D+", RegexOptions.Compiled | RegexOptions.Singleline);

    // stateless comparer can be built once
    private static readonly AggregateComparer Comparer = new AggregateComparer();

    public static IEnumerable<T> OrderByNatural<T>(this IEnumerable<T> source, Func<T, string> selector)
    {
        // first extract string from object using selector
        // then extract digit and non-digit groups
        Func<T, IEnumerable<IComparable>> splitter =
            s => Regex.Matches(selector(s))
                      .Cast<Match>()
                      .Select(m => Char.IsDigit(m.Value[0]) ? (IComparable) int.Parse(m.Value) : m.Value);
        return source.OrderBy(splitter, Comparer);
    }

    /// <summary>
    /// This comparer will compare two lists of objects against each other
    /// </summary>
    /// <remarks>Objects in each list are compare to their corresponding elements in the other
    /// list until a difference is found.</remarks>
    private class AggregateComparer : IComparer<IEnumerable<IComparable>>
    {
        public int Compare(IEnumerable<IComparable> x, IEnumerable<IComparable> y)
        {
            return
                x.Zip(y, (a, b) => new {a, b})              // walk both lists
                 .Select(pair => pair.a.CompareTo(pair.b))  // compare each object
                 .FirstOrDefault(result => result != 0);    // until a difference is found
        }
    }
}

Идея состоит в том, чтобы разбить исходные строки на блоки из цифр и не цифр ("\d+|\D+"). Поскольку это потенциально дорогостоящая задача, она выполняется только один раз для каждой записи. Затем мы используем средство сравнения сопоставимых объектов (извините, я не могу найти более правильный способ сказать это). Он сравнивает каждый блок с соответствующим блоком в другой строке.

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