Naturalny porządek sortowania w C #

131

Czy ktoś ma dobry zasób lub podaje próbkę naturalnego sortowania w języku C # dla FileInfotablicy? Implementuję IComparerinterfejs w moim stylu.

Michael Kniskern
źródło

Odpowiedzi:

150

Najłatwiej jest po prostu P / Wywołać wbudowaną funkcję w systemie Windows i użyć jej jako funkcji porównania w IComparer:

[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
private static extern int StrCmpLogicalW(string psz1, string psz2);

Michael Kaplan podaje tutaj kilka przykładów działania tej funkcji oraz zmian wprowadzonych w systemie Vista, aby działała bardziej intuicyjnie. Zaletą tej funkcji jest to, że będzie ona zachowywać się tak samo, jak wersja systemu Windows, na której działa, jednak oznacza to, że różni się ona między wersjami systemu Windows, więc musisz rozważyć, czy jest to dla Ciebie problem.

Tak więc pełna implementacja wyglądałaby tak:

[SuppressUnmanagedCodeSecurity]
internal static class SafeNativeMethods
{
    [DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
    public static extern int StrCmpLogicalW(string psz1, string psz2);
}

public sealed class NaturalStringComparer : IComparer<string>
{
    public int Compare(string a, string b)
    {
        return SafeNativeMethods.StrCmpLogicalW(a, b);
    }
}

public sealed class NaturalFileInfoNameComparer : IComparer<FileInfo>
{
    public int Compare(FileInfo a, FileInfo b)
    {
        return SafeNativeMethods.StrCmpLogicalW(a.Name, b.Name);
    }
}
Greg Beech
źródło
9
Świetna odpowiedź. Uwaga: to nie zadziała z Win2000, dla tych kilku osób, które nadal działają w tym systemie operacyjnym. Z drugiej strony jest wystarczająco dużo wskazówek między blogiem Kaplana a dokumentacją MSDN, aby utworzyć podobną funkcję.
Chris Charabaruk
10
To nie jest przenośne, działa tylko w Win32, ale nie działa w Linux / MacOS / Silverlight / Windows Phone / Metro
linquize
21
@linquize - powiedział, że .NET nie Mono, więc Linux / OSX nie jest tak naprawdę problemem. Windows Phone / Metro nie istniał w 2008 roku, kiedy opublikowano tę odpowiedź. Jak często wykonujesz operacje na plikach w Silverlight? Tak więc dla PO i prawdopodobnie większości innych osób była to odpowiednia odpowiedź. W każdym razie możesz udzielić lepszej odpowiedzi; tak właśnie działa ta strona.
Greg Beech
6
Nie oznacza to, że pierwotna odpowiedź była błędna. Po prostu dodaję dodatkowe informacje z aktualnymi informacjami
linquize
2
Do Twojej wiadomości, jeśli dziedziczysz z Comparer<T>zamiast implementować IComparer<T>, otrzymasz wbudowaną implementację IComparer(nieogólnego) interfejsu, który wywołuje twoją metodę ogólną, do użytku w interfejsach API, które zamiast tego używają. W zasadzie to też nic nie kosztuje: po prostu usuń „I” i zmień public int Compare(...)na public override int Compare(...). To samo dotyczy IEqualityComparer<T>i EqualityComparer<T>.
Joe Amenta
76

Pomyślałem, że dodam do tego (z najbardziej zwięzłym rozwiązaniem, jakie udało mi się znaleźć):

public static IOrderedEnumerable<T> OrderByAlphaNumeric<T>(this IEnumerable<T> source, Func<T, string> selector)
{
    int max = source
        .SelectMany(i => Regex.Matches(selector(i), @"\d+").Cast<Match>().Select(m => (int?)m.Value.Length))
        .Max() ?? 0;

    return source.OrderBy(i => Regex.Replace(selector(i), @"\d+", m => m.Value.PadLeft(max, '0')));
}

Powyższe dopełnia wszystkie liczby w ciągu do maksymalnej długości wszystkich liczb we wszystkich ciągach i wykorzystuje wynikowy ciąg do sortowania.

Rzutowanie do ( int?) ma umożliwić kolekcje ciągów bez żadnych liczb ( .Max()na pustym wyliczalnym wyrzuca InvalidOperationException).

Matthew Horsley
źródło
1
+1 Nie tylko jest najbardziej zwięzły, ale także najszybszy, jaki widziałem. z wyjątkiem zaakceptowanej odpowiedzi, ale nie mogę jej użyć z powodu zależności maszyny. Posortował ponad 4 miliony wartości w około 35 sekund.
Gene S
4
Jest to zarówno piękne, jak i niemożliwe do odczytania. Zakładam, że zalety Linqa będą oznaczały (przynajmniej) najlepszą średnią i najlepszą wydajność, więc myślę, że się na to zgodzę. Pomimo niejasności. Bardzo dziękuję @Matthew Horsley
Ian Grainger
1
To jest bardzo dobre, ale jest błąd dla niektórych liczb dziesiętnych, moim przykładem było sortowanie k8.11 vs k8.2. Aby to naprawić, zaimplementowałem następujące wyrażenie regularne: \ d + ([\.,] \ D)?
devzero
2
Musisz również wziąć pod uwagę długość drugiej grupy (kropka dziesiętna + dziesiętne), gdy wprowadzasz ten kod m.Value.PadLeft (max, '0')
devzero
4
Myślę, że możesz użyć .DefaultIfEmpty().Max()zamiast przesyłać do int?. Warto też zrobić, source.ToList()aby uniknąć ponownego wyliczania wyliczalnego.
Teejay
32

Żadna z istniejących implementacji nie wyglądała świetnie, więc napisałem własną. Wyniki są prawie identyczne z sortowaniem używanym we współczesnych wersjach Eksploratora Windows (Windows 7/8). Jedyne różnice, które widziałem, to 1) chociaż Windows (np. XP) obsługiwał liczby o dowolnej długości, teraz jest ograniczony do 19 cyfr - moja jest nieograniczona, 2) Windows daje niespójne wyniki z niektórymi zestawami cyfr Unicode - moje działa dobrze (chociaż nie porównuje liczbowo cyfr z par zastępczych; ani Windows), i 3) mój nie może rozróżnić różnych typów wag sortowania innych niż pierwotne, jeśli występują one w różnych sekcjach (np. „e-1é” vs ” é1e- ”- sekcje przed i po liczbie mają różnice w wadze znaków diakrytycznych i interpunkcyjnych).

public static int CompareNatural(string strA, string strB) {
    return CompareNatural(strA, strB, CultureInfo.CurrentCulture, CompareOptions.IgnoreCase);
}

public static int CompareNatural(string strA, string strB, CultureInfo culture, CompareOptions options) {
    CompareInfo cmp = culture.CompareInfo;
    int iA = 0;
    int iB = 0;
    int softResult = 0;
    int softResultWeight = 0;
    while (iA < strA.Length && iB < strB.Length) {
        bool isDigitA = Char.IsDigit(strA[iA]);
        bool isDigitB = Char.IsDigit(strB[iB]);
        if (isDigitA != isDigitB) {
            return cmp.Compare(strA, iA, strB, iB, options);
        }
        else if (!isDigitA && !isDigitB) {
            int jA = iA + 1;
            int jB = iB + 1;
            while (jA < strA.Length && !Char.IsDigit(strA[jA])) jA++;
            while (jB < strB.Length && !Char.IsDigit(strB[jB])) jB++;
            int cmpResult = cmp.Compare(strA, iA, jA - iA, strB, iB, jB - iB, options);
            if (cmpResult != 0) {
                // Certain strings may be considered different due to "soft" differences that are
                // ignored if more significant differences follow, e.g. a hyphen only affects the
                // comparison if no other differences follow
                string sectionA = strA.Substring(iA, jA - iA);
                string sectionB = strB.Substring(iB, jB - iB);
                if (cmp.Compare(sectionA + "1", sectionB + "2", options) ==
                    cmp.Compare(sectionA + "2", sectionB + "1", options))
                {
                    return cmp.Compare(strA, iA, strB, iB, options);
                }
                else if (softResultWeight < 1) {
                    softResult = cmpResult;
                    softResultWeight = 1;
                }
            }
            iA = jA;
            iB = jB;
        }
        else {
            char zeroA = (char)(strA[iA] - (int)Char.GetNumericValue(strA[iA]));
            char zeroB = (char)(strB[iB] - (int)Char.GetNumericValue(strB[iB]));
            int jA = iA;
            int jB = iB;
            while (jA < strA.Length && strA[jA] == zeroA) jA++;
            while (jB < strB.Length && strB[jB] == zeroB) jB++;
            int resultIfSameLength = 0;
            do {
                isDigitA = jA < strA.Length && Char.IsDigit(strA[jA]);
                isDigitB = jB < strB.Length && Char.IsDigit(strB[jB]);
                int numA = isDigitA ? (int)Char.GetNumericValue(strA[jA]) : 0;
                int numB = isDigitB ? (int)Char.GetNumericValue(strB[jB]) : 0;
                if (isDigitA && (char)(strA[jA] - numA) != zeroA) isDigitA = false;
                if (isDigitB && (char)(strB[jB] - numB) != zeroB) isDigitB = false;
                if (isDigitA && isDigitB) {
                    if (numA != numB && resultIfSameLength == 0) {
                        resultIfSameLength = numA < numB ? -1 : 1;
                    }
                    jA++;
                    jB++;
                }
            }
            while (isDigitA && isDigitB);
            if (isDigitA != isDigitB) {
                // One number has more digits than the other (ignoring leading zeros) - the longer
                // number must be larger
                return isDigitA ? 1 : -1;
            }
            else if (resultIfSameLength != 0) {
                // Both numbers are the same length (ignoring leading zeros) and at least one of
                // the digits differed - the first difference determines the result
                return resultIfSameLength;
            }
            int lA = jA - iA;
            int lB = jB - iB;
            if (lA != lB) {
                // Both numbers are equivalent but one has more leading zeros
                return lA > lB ? -1 : 1;
            }
            else if (zeroA != zeroB && softResultWeight < 2) {
                softResult = cmp.Compare(strA, iA, 1, strB, iB, 1, options);
                softResultWeight = 2;
            }
            iA = jA;
            iB = jB;
        }
    }
    if (iA < strA.Length || iB < strB.Length) {
        return iA < strA.Length ? 1 : -1;
    }
    else if (softResult != 0) {
        return softResult;
    }
    return 0;
}

Podpis pasuje do Comparison<string>delegata:

string[] files = Directory.GetFiles(@"C:\");
Array.Sort(files, CompareNatural);

Oto klasa opakowania do użycia jako IComparer<string>:

public class CustomComparer<T> : IComparer<T> {
    private Comparison<T> _comparison;

    public CustomComparer(Comparison<T> comparison) {
        _comparison = comparison;
    }

    public int Compare(T x, T y) {
        return _comparison(x, y);
    }
}

Przykład:

string[] files = Directory.EnumerateFiles(@"C:\")
    .OrderBy(f => f, new CustomComparer<string>(CompareNatural))
    .ToArray();

Oto dobry zestaw nazw plików, których używam do testowania:

Func<string, string> expand = (s) => { int o; while ((o = s.IndexOf('\\')) != -1) { int p = o + 1;
    int z = 1; while (s[p] == '0') { z++; p++; } int c = Int32.Parse(s.Substring(p, z));
    s = s.Substring(0, o) + new string(s[o - 1], c) + s.Substring(p + z); } return s; };
string encodedFileNames =
    "KDEqLW4xMiotbjEzKjAwMDFcMDY2KjAwMlwwMTcqMDA5XDAxNyowMlwwMTcqMDlcMDE3KjEhKjEtISox" +
    "LWEqMS4yNT8xLjI1KjEuNT8xLjUqMSoxXDAxNyoxXDAxOCoxXDAxOSoxXDA2NioxXDA2NyoxYSoyXDAx" +
    "NyoyXDAxOCo5XDAxNyo5XDAxOCo5XDA2Nio9MSphMDAxdGVzdDAxKmEwMDF0ZXN0aW5nYTBcMzEqYTAw" +
    "Mj9hMDAyIGE/YTAwMiBhKmEwMDIqYTAwMmE/YTAwMmEqYTAxdGVzdGluZ2EwMDEqYTAxdnNmcyphMSph" +
    "MWEqYTF6KmEyKmIwMDAzcTYqYjAwM3E0KmIwM3E1KmMtZSpjZCpjZipmIDEqZipnP2cgMT9oLW4qaG8t" +
    "bipJKmljZS1jcmVhbT9pY2VjcmVhbT9pY2VjcmVhbS0/ajBcNDE/ajAwMWE/ajAxP2shKmsnKmstKmsx" +
    "KmthKmxpc3QqbTAwMDNhMDA1YSptMDAzYTAwMDVhKm0wMDNhMDA1Km0wMDNhMDA1YSpuMTIqbjEzKm8t" +
    "bjAxMypvLW4xMipvLW40P28tbjQhP28tbjR6P28tbjlhLWI1Km8tbjlhYjUqb24wMTMqb24xMipvbjQ/" +
    "b240IT9vbjR6P29uOWEtYjUqb245YWI1Km/CrW4wMTMqb8KtbjEyKnAwMCpwMDEqcDAxwr0hKnAwMcK9" +
    "KnAwMcK9YSpwMDHCvcK+KnAwMipwMMK9KnEtbjAxMypxLW4xMipxbjAxMypxbjEyKnItMDAhKnItMDAh" +
    "NSpyLTAwIe+8lSpyLTAwYSpyLe+8kFwxIS01KnIt77yQXDEhLe+8lSpyLe+8kFwxISpyLe+8kFwxITUq" +
    "ci3vvJBcMSHvvJUqci3vvJBcMWEqci3vvJBcMyE1KnIwMCEqcjAwLTUqcjAwLjUqcjAwNSpyMDBhKnIw" +
    "NSpyMDYqcjQqcjUqctmg2aYqctmkKnLZpSpy27Dbtipy27Qqctu1KnLfgN+GKnLfhCpy34UqcuClpuCl" +
    "rCpy4KWqKnLgpasqcuCnpuCnrCpy4KeqKnLgp6sqcuCppuCprCpy4KmqKnLgqasqcuCrpuCrrCpy4Kuq" +
    "KnLgq6sqcuCtpuCtrCpy4K2qKnLgrasqcuCvpuCvrCpy4K+qKnLgr6sqcuCxpuCxrCpy4LGqKnLgsasq" +
    "cuCzpuCzrCpy4LOqKnLgs6sqcuC1puC1rCpy4LWqKnLgtasqcuC5kOC5lipy4LmUKnLguZUqcuC7kOC7" +
    "lipy4LuUKnLgu5UqcuC8oOC8pipy4LykKnLgvKUqcuGBgOGBhipy4YGEKnLhgYUqcuGCkOGClipy4YKU" +
    "KnLhgpUqcuGfoOGfpipy4Z+kKnLhn6UqcuGgkOGglipy4aCUKnLhoJUqcuGlhuGljCpy4aWKKnLhpYsq" +
    "cuGnkOGnlipy4aeUKnLhp5UqcuGtkOGtlipy4a2UKnLhrZUqcuGusOGutipy4a60KnLhrrUqcuGxgOGx" +
    "hipy4bGEKnLhsYUqcuGxkOGxlipy4bGUKnLhsZUqcuqYoFwx6pilKnLqmKDqmKUqcuqYoOqYpipy6pik" +
    "KnLqmKUqcuqjkOqjlipy6qOUKnLqo5UqcuqkgOqkhipy6qSEKnLqpIUqcuqpkOqplipy6qmUKnLqqZUq" +
    "cvCQkqAqcvCQkqUqcvCdn5gqcvCdn50qcu+8kFwxISpy77yQXDEt77yVKnLvvJBcMS7vvJUqcu+8kFwx" +
    "YSpy77yQXDHqmKUqcu+8kFwx77yO77yVKnLvvJBcMe+8lSpy77yQ77yVKnLvvJDvvJYqcu+8lCpy77yV" +
    "KnNpKnPEsSp0ZXN02aIqdGVzdNmi2aAqdGVzdNmjKnVBZS0qdWFlKnViZS0qdUJlKnVjZS0xw6kqdWNl" +
    "McOpLSp1Y2Uxw6kqdWPDqS0xZSp1Y8OpMWUtKnVjw6kxZSp3ZWlhMSp3ZWlhMip3ZWlzczEqd2Vpc3My" +
    "KndlaXoxKndlaXoyKndlacOfMSp3ZWnDnzIqeSBhMyp5IGE0KnknYTMqeSdhNCp5K2EzKnkrYTQqeS1h" +
    "Myp5LWE0KnlhMyp5YTQqej96IDA1MD96IDIxP3ohMjE/ejIwP3oyMj96YTIxP3rCqTIxP1sxKl8xKsKt" +
    "bjEyKsKtbjEzKsSwKg==";
string[] fileNames = Encoding.UTF8.GetString(Convert.FromBase64String(encodedFileNames))
    .Replace("*", ".txt?").Split(new[] { "?" }, StringSplitOptions.RemoveEmptyEntries)
    .Select(n => expand(n)).ToArray();
JD
źródło
1
Sekcje cyfr należy porównać według sekcji, tj. „Abc12b” powinno być mniejsze niż „abc123”.
SOUser
Możesz wypróbować następujące dane: public string [] filenames = {"-abc12.txt", " abc12.txt", "1abc_2.txt", "a0000012.txt", "a0000012c.txt", "a000012.txt" , „a000012b.txt”, „a012.txt”, „a0000102.txt”, „abc1_2.txt”, „abc12 .txt”, „abc12b.txt”, „abc123.txt”, „abccde.txt”, „ b0000.txt ”,„ b00001.txt ”,„ b0001.txt ”,„ b001.txt ”,„ c0000.txt ”,„ c0000c.txt ”,„ c00001.txt ”,„ c000b.txt ”,„ d0. 20.2b.txt ”,„ d0.1000c.txt ”,„ d0.2000y.txt ”,„ d0.20000.2b.txt ”,„
SOUser
@XichenLi Dzięki za dobry przypadek testowy. Jeśli pozwolisz Eksploratorowi Windows sortować te pliki, uzyskasz różne wyniki w zależności od używanej wersji systemu Windows. Mój kod sortuje te nazwy identycznie jak Server 2003 (i prawdopodobnie XP), ale różni się od Windows 8. Jeśli będę miał okazję, spróbuję dowiedzieć się, jak robi to Windows 8 i zaktualizować mój kod.
JD
3
Ma błąd. Indeks poza zakresem
linquize
3
Świetne rozwiązanie! Kiedy testowałem go w normalnym scenariuszu z około 10000 plików, był szybszy niż przykład wyrażenia regularnego Matthew i mniej więcej taką samą wydajność jak StrCmpLogicalW (). Powyższy kod zawiera drobny błąd: "while (strA [jA] == zeroA) jA ++;" i "while (strB [jB] == zeroB) jB ++;" powinno być "while (jA <strA.Length && strA [jA] == zeroA) jA ++;" i "while (jB <strB.Length && strB [jB] == zeroB) jB ++;". W przeciwnym razie ciągi zawierające tylko zera spowodują zgłoszenie wyjątku.
kuroki
23

Czyste rozwiązanie C # dla Linq Orderby:

http://zootfroot.blogspot.com/2009/09/natural-sort-compare-with-linq-orderby.html

public class NaturalSortComparer<T> : IComparer<string>, IDisposable
{
    private bool isAscending;

    public NaturalSortComparer(bool inAscendingOrder = true)
    {
        this.isAscending = inAscendingOrder;
    }

    #region IComparer<string> Members

    public int Compare(string x, string y)
    {
        throw new NotImplementedException();
    }

    #endregion

    #region IComparer<string> Members

    int IComparer<string>.Compare(string x, string y)
    {
        if (x == y)
            return 0;

        string[] x1, y1;

        if (!table.TryGetValue(x, out x1))
        {
            x1 = Regex.Split(x.Replace(" ", ""), "([0-9]+)");
            table.Add(x, x1);
        }

        if (!table.TryGetValue(y, out y1))
        {
            y1 = Regex.Split(y.Replace(" ", ""), "([0-9]+)");
            table.Add(y, y1);
        }

        int returnVal;

        for (int i = 0; i < x1.Length && i < y1.Length; i++)
        {
            if (x1[i] != y1[i])
            {
                returnVal = PartCompare(x1[i], y1[i]);
                return isAscending ? returnVal : -returnVal;
            }
        }

        if (y1.Length > x1.Length)
        {
            returnVal = 1;
        }
        else if (x1.Length > y1.Length)
        { 
            returnVal = -1; 
        }
        else
        {
            returnVal = 0;
        }

        return isAscending ? returnVal : -returnVal;
    }

    private static int PartCompare(string left, string right)
    {
        int x, y;
        if (!int.TryParse(left, out x))
            return left.CompareTo(right);

        if (!int.TryParse(right, out y))
            return left.CompareTo(right);

        return x.CompareTo(y);
    }

    #endregion

    private Dictionary<string, string[]> table = new Dictionary<string, string[]>();

    public void Dispose()
    {
        table.Clear();
        table = null;
    }
}
James McCormack
źródło
3
Ten kod pochodzi ostatecznie z codeproject.com/KB/recipes/NaturalComparer.aspx (który nie jest zorientowany na LINQ).
mhenry1384
3
We wpisie na blogu autorami jest Justin Jones ( codeproject.com/KB/string/NaturalSortComparer.aspx ) dla IComparer, a nie Pascal Ganaye.
James McCormack
1
Drobna uwaga, to rozwiązanie ignoruje spacje, co nie jest tym samym, co okna, i nie jest tak dobre, jak kod Matthew Horsleya poniżej. Możesz więc na przykład otrzymać „string01” „string 01” „string 02” „string02” (który wygląda brzydko). Usunięcie usuwania spacji powoduje, że ciągi są porządkowane wstecz, tj. „String01” występuje przed „string 01”, co może być dopuszczalne lub nie.
Michael Parker
To działało w przypadku adresów, tj. „1 Smith Rd”, „10 Smith Rd”, „2 Smith Rd” itp. - Posortowane naturalnie. Tak! Niezłe!
Piotr Kula
Nawiasem mówiąc, zauważyłem (a komentarze na tej połączonej stronie również wydają się wskazywać), że argument Type <T> jest całkowicie niepotrzebny.
jv-dev
18

Odpowiedź Matthewsa Horsleysa to najszybsza metoda, która nie zmienia zachowania w zależności od wersji systemu Windows, na której działa Twój program. Można to jednak zrobić jeszcze szybciej, tworząc raz wyrażenie regularne i używając RegexOptions.Compiled. Dodałem również opcję wstawiania funkcji porównującej ciągi, aby w razie potrzeby można było zignorować wielkość liter i poprawiłem nieco czytelność.

    public static IEnumerable<T> OrderByNatural<T>(this IEnumerable<T> items, Func<T, string> selector, StringComparer stringComparer = null)
    {
        var regex = new Regex(@"\d+", RegexOptions.Compiled);

        int maxDigits = items
                      .SelectMany(i => regex.Matches(selector(i)).Cast<Match>().Select(digitChunk => (int?)digitChunk.Value.Length))
                      .Max() ?? 0;

        return items.OrderBy(i => regex.Replace(selector(i), match => match.Value.PadLeft(maxDigits, '0')), stringComparer ?? StringComparer.CurrentCulture);
    }

Używany przez

var sortedEmployees = employees.OrderByNatural(emp => emp.Name);

Sortowanie 100 000 ciągów zajmuje 450 ms w porównaniu do 300 ms przy domyślnym porównaniu ciągów .net - całkiem szybko!

Michael Parker
źródło
2
Warto przeczytać powyższe - Kompilacja i
ponowne
16

Moje rozwiązanie:

void Main()
{
    new[] {"a4","a3","a2","a10","b5","b4","b400","1","C1d","c1d2"}.OrderBy(x => x, new NaturalStringComparer()).Dump();
}

public class NaturalStringComparer : IComparer<string>
{
    private static readonly Regex _re = new Regex(@"(?<=\D)(?=\d)|(?<=\d)(?=\D)", RegexOptions.Compiled);

    public int Compare(string x, string y)
    {
        x = x.ToLower();
        y = y.ToLower();
        if(string.Compare(x, 0, y, 0, Math.Min(x.Length, y.Length)) == 0)
        {
            if(x.Length == y.Length) return 0;
            return x.Length < y.Length ? -1 : 1;
        }
        var a = _re.Split(x);
        var b = _re.Split(y);
        int i = 0;
        while(true)
        {
            int r = PartCompare(a[i], b[i]);
            if(r != 0) return r;
            ++i;
        }
    }

    private static int PartCompare(string x, string y)
    {
        int a, b;
        if(int.TryParse(x, out a) && int.TryParse(y, out b))
            return a.CompareTo(b);
        return x.CompareTo(y);
    }
}

Wyniki:

1
a2
a3
a4
a10
b4
b5
b400
C1d
c1d2
mpen
źródło
Lubię to. Jest łatwy do zrozumienia i nie wymaga Linq.
12

Musisz być ostrożny - niejasno przypominam sobie, że czytałem, że StrCmpLogicalW lub coś podobnego nie było ściśle przechodnie i zauważyłem, że metody sortowania .NET czasami utknęły w nieskończonych pętlach, jeśli funkcja porównawcza złamie tę regułę.

Porównanie przechodnie zawsze wykaże, że a <c, jeśli a <b i b <c. Istnieje funkcja, która dokonuje naturalnego porównania kolejności sortowania, która nie zawsze spełnia to kryterium, ale nie mogę sobie przypomnieć, czy jest to StrCmpLogicalW, czy coś innego.

Jonathan Gilbert
źródło
Czy masz jakiś dowód na to stwierdzenie? Po wygooglowaniu nie mogę znaleźć żadnej wskazówki, że to prawda.
mhenry1384
2
Doświadczyłem nieskończonych pętli z StrCmpLogicalW.
thd
Element opinii programu Visual Studio 236900 już nie istnieje, ale tutaj jest bardziej aktualny, który potwierdza problem: connect.microsoft.com/VisualStudio/feedback/details/774540/ ... Zapewnia również obejście: CultureInfoma właściwość CompareInfo, a obiekt, który zwraca, może dostarczyć ci SortKeyobiektów. Te z kolei można porównać i zagwarantować przechodniość.
Jonathan Gilbert
10

To jest mój kod do sortowania ciągu zawierającego zarówno znaki alfanumeryczne, jak i numeryczne.

Po pierwsze, ta metoda rozszerzenia:

public static IEnumerable<string> AlphanumericSort(this IEnumerable<string> me)
{
    return me.OrderBy(x => Regex.Replace(x, @"\d+", m => m.Value.PadLeft(50, '0')));
}

Następnie po prostu użyj go w dowolnym miejscu w kodzie, tak jak to:

List<string> test = new List<string>() { "The 1st", "The 12th", "The 2nd" };
test = test.AlphanumericSort();

Jak to działa ? Zamieniając na zera:

  Original  | Regex Replace |      The      |   Returned
    List    | Apply PadLeft |    Sorting    |     List
            |               |               |
 "The 1st"  |  "The 001st"  |  "The 001st"  |  "The 1st"
 "The 12th" |  "The 012th"  |  "The 002nd"  |  "The 2nd"
 "The 2nd"  |  "The 002nd"  |  "The 012th"  |  "The 12th"

Działa z liczbami wielokrotnymi:

 Alphabetical Sorting | Alphanumeric Sorting
                      |
 "Page 21, Line 42"   | "Page 3, Line 7"
 "Page 21, Line 5"    | "Page 3, Line 32"
 "Page 3, Line 32"    | "Page 21, Line 5"
 "Page 3, Line 7"     | "Page 21, Line 42"

Mam nadzieję, że to pomoże.

Picsonald
źródło
6

Dodając do odpowiedzi Grega Beecha (ponieważ właśnie tego szukałem), jeśli chcesz użyć tego z Linq, możesz użyć tego, OrderByktóry zajmuje plik IComparer. Na przykład:

var items = new List<MyItem>();

// fill items

var sorted = items.OrderBy(item => item.Name, new NaturalStringComparer());
Wilka
źródło
2

Oto stosunkowo prosty przykład, który nie używa P / Invoke i unika alokacji podczas wykonywania.

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

Nie ignoruje wiodących zer, więc 01następuje po2 .

Odpowiedni test jednostkowy:

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));
    }
}
Drew Noakes
źródło
2

Właściwie zaimplementowałem to jako metodę rozszerzającą na stronie, StringComparerdzięki czemu możesz na przykład:

  • StringComparer.CurrentCulture.WithNaturalSort() lub
  • StringComparer.OrdinalIgnoreCase.WithNaturalSort().

Otrzymana IComparer<string>może być stosowany we wszystkich miejscach, jak OrderBy, OrderByDescending, ThenBy, ThenByDescending, SortedSet<string>, itd. I można nadal łatwo uszczypnąć czułość przypadek, kultura, itp

Implementacja jest dość trywialna i powinna działać całkiem dobrze nawet na dużych sekwencjach.


Opublikowałem go również jako mały pakiet NuGet , więc możesz po prostu:

Install-Package NaturalSort.Extension

Kod zawierający komentarze do dokumentacji XML i zestaw testów jest dostępny w repozytorium NaturalSort.Extension GitHub .


Cały kod jest taki (jeśli nie możesz jeszcze używać C # 7, po prostu zainstaluj pakiet 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;
        }
    }
}
Tom Pažourek
źródło
2

Oto naiwny, jednowierszowy sposób LINQ bez wyrażeń regularnych (zapożyczony z Pythona):

var alphaStrings = new List<string>() { "10","2","3","4","50","11","100","a12","b12" };
var orderedString = alphaStrings.OrderBy(g => new Tuple<int, string>(g.ToCharArray().All(char.IsDigit)? int.Parse(g) : int.MaxValue, g));
// Order Now: ["2","3","4","10","11","50","100","a12","b12"]
mshsayem
źródło
Usunięto Dump () i przypisano do var, a to działa jak urok!
Arne S
@ArneS: Został napisany w LinQPad; i zapomniałem usunąć Dump(). Dzięki za wskazanie.
mshsayem
1

Rozwijając kilka poprzednich odpowiedzi i korzystając z metod rozszerzających, wymyśliłem następujące, które nie mają zastrzeżeń związanych z potencjalnymi wielokrotnymi wyliczeniami lub problemami z wydajnością związanymi z używaniem wielu obiektów regex lub niepotrzebnym wywoływaniem wyrażenia regularnego, że Mówi się, że używa ToList (), co może negować korzyści w większych kolekcjach.

Selektor obsługuje typowanie ogólne, aby umożliwić przypisanie dowolnego delegata, elementy w kolekcji źródłowej są modyfikowane przez selektor, a następnie konwertowane na ciągi za pomocą 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);
    }
Vorspire
źródło
1

Zainspirowana rozwiązaniem Michaela Parkera, oto IComparerimplementacja, którą możesz odwiedzić dowolną z metod zamawiania 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);
    }
}
Oliver
źródło
0

Potrzebowaliśmy naturalnego sortowania, aby poradzić sobie z tekstem o następującym wzorcu:

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

Z jakiegoś powodu, kiedy pierwszy raz spojrzałem na SO, nie znalazłem tego postu i nie zaimplementowałem własnego. W porównaniu z niektórymi przedstawionymi tutaj rozwiązaniami, choć podobnymi koncepcyjnie, mogłoby to być może być prostsze i łatwiejsze do zrozumienia. Jednak chociaż próbowałem przyjrzeć się wąskim gardłom wydajności, nadal jest to znacznie wolniejsza implementacja niż domyślnaOrderBy() .

Oto metoda rozszerzenia, którą implementuję:

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

Pomysł polega na podzieleniu oryginalnych ciągów na bloki cyfr i niecyfrowe ( "\d+|\D+"). Ponieważ jest to potencjalnie kosztowne zadanie, wykonuje się je tylko raz na wpis. Następnie używamy modułu porównującego porównywalne obiekty (przepraszam, nie mogę znaleźć bardziej właściwego sposobu, aby to powiedzieć). Porównuje każdy blok z odpowiadającym mu blokiem w drugim ciągu.

Chciałbym otrzymać informację zwrotną, jak można to poprawić i jakie są główne wady. Zauważ, że łatwość konserwacji jest dla nas w tym momencie ważna i obecnie nie używamy jej w bardzo dużych zestawach danych.

Eric Liprandi
źródło
1
To ulega awarii, gdy próbuje porównać ciągi, które są strukturalnie różne - np. Porównywanie „a-1” z „a-2” działa dobrze, ale porównywanie „a” z „1” nie działa, ponieważ „a” .CompareTo (1) zgłasza wyjątek.
jimrandomh
@jimrandomh, masz rację. To podejście było specyficzne dla naszych wzorców.
Eric Liprandi
0

Wersja łatwiejsza do odczytania / utrzymania.

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

    public int Compare(string x, string y) {
        const int LeftIsSmaller = -1;
        const int RightIsSmaller = 1;
        const int Equal = 0;

        var leftString = x;
        var rightString = y;

        var stringComparer = CultureInfo.CurrentCulture.CompareInfo;

        int rightIndex;
        int leftIndex;

        for (leftIndex = 0, rightIndex = 0;
             leftIndex < leftString.Length && rightIndex < rightString.Length;
             leftIndex++, rightIndex++) {
            var leftChar = leftString[leftIndex];
            var rightChar = rightString[leftIndex];

            var leftIsNumber = char.IsNumber(leftChar);
            var rightIsNumber = char.IsNumber(rightChar);

            if (!leftIsNumber && !rightIsNumber) {
                var result = stringComparer.Compare(leftString, leftIndex, 1, rightString, leftIndex, 1);
                if (result != 0) return result;
            } else if (leftIsNumber && !rightIsNumber) {
                return LeftIsSmaller;
            } else if (!leftIsNumber && rightIsNumber) {
                return RightIsSmaller;
            } else {
                var leftNumberLength = NumberLength(leftString, leftIndex, out var leftNumber);
                var rightNumberLength = NumberLength(rightString, rightIndex, out var rightNumber);

                if (leftNumberLength < rightNumberLength) {
                    return LeftIsSmaller;
                } else if (leftNumberLength > rightNumberLength) {
                    return RightIsSmaller;
                } else {
                    if(leftNumber < rightNumber) {
                        return LeftIsSmaller;
                    } else if(leftNumber > rightNumber) {
                        return RightIsSmaller;
                    }
                }
            }
        }

        if (leftString.Length < rightString.Length) {
            return LeftIsSmaller;
        } else if(leftString.Length > rightString.Length) {
            return RightIsSmaller;
        }

        return Equal;
    }

    public int NumberLength(string str, int offset, out int number) {
        if (string.IsNullOrWhiteSpace(str)) throw new ArgumentNullException(nameof(str));
        if (offset >= str.Length) throw new ArgumentOutOfRangeException(nameof(offset), offset, "Offset must be less than the length of the string.");

        var currentOffset = offset;

        var curChar = str[currentOffset];

        if (!char.IsNumber(curChar))
            throw new ArgumentException($"'{curChar}' is not a number.", nameof(offset));

        int length = 1;

        var numberString = string.Empty;

        for (currentOffset = offset + 1;
            currentOffset < str.Length;
            currentOffset++, length++) {

            curChar = str[currentOffset];
            numberString += curChar;

            if (!char.IsNumber(curChar)) {
                number = int.Parse(numberString);

                return length;
            }
        }

        number = int.Parse(numberString);

        return length;
    }
}
Kelly Elton
źródło
-2

Pozwólcie, że wyjaśnię mój problem i jak udało mi się go rozwiązać.

Problem: - Sortuj pliki na podstawie nazwy pliku z obiektów FileInfo, które są pobierane z katalogu.

Rozwiązanie: - Wybrałem nazwy plików z FileInfo i przyciąłem część „.png” nazwy pliku. Teraz po prostu wykonaj List.Sort (), która sortuje nazwy plików w naturalnej kolejności sortowania. Na podstawie moich testów stwierdziłem, że plik .png psuje porządek sortowania. Spójrz na poniższy kod

var imageNameList = new DirectoryInfo(@"C:\Temp\Images").GetFiles("*.png").Select(x =>x.Name.Substring(0, x.Name.Length - 4)).ToList();
imageNameList.Sort();
girishkatta9
źródło
Czy mogę poznać przyczynę -1 w tej odpowiedzi?
girishkatta9