Естественный порядок сортировки в C#
-
05-07-2019 - |
Вопрос
У кого-нибудь есть хороший ресурс или предоставлен образец сортировки естественного порядка на C# для FileInfo
множество?Я реализую IComparer
интерфейс в моих родах.
Решение
Самое простое, что нужно сделать, это просто P / вызвать встроенную функцию в Windows и использовать ее в качестве функции сравнения в вашем IComparer
:
[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
private static extern int StrCmpLogicalW(string psz1, string psz2);
У Майкла Каплана есть несколько примеров того, как эта функция работает здесь , и изменения, которые были сделаны для Vista, чтобы сделать ее более интуитивно понятной. Плюсом этой функции является то, что она будет работать так же, как и версия Windows, на которой она работает, однако это означает, что она отличается в разных версиях Windows, поэтому вам нужно подумать, не является ли это проблемой для вас.
Таким образом, полная реализация будет выглядеть примерно так:
[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);
}
}
Другие советы
Просто подумал, что могу добавить к этому (самое краткое решение, которое я смог найти):
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')));
}
Приведенное выше добавление любых чисел в строке к максимальной длине всех чисел во всех строках и использование полученной строки для сортировки. Р>
Приведение к (int?
) должно разрешать коллекции строк без каких-либо чисел (.Max()
для пустого перечислимого символа InvalidOperationException
).
Ни одна из существующих реализаций не выглядела хорошо, поэтому я написал свою собственную.Результаты практически идентичны сортировке, используемой в современных версиях Проводника Windows (Windows 7/8).Единственные различия, которые я видел: 1) хотя раньше Windows (например,XP) обрабатывает числа любой длины, теперь они ограничены 19 цифрами - у меня неограничено, 2) Windows дает противоречивые результаты с определенными наборами цифр Юникода - у меня работает нормально (хотя он не сравнивает цифры из суррогатных пар численно;Windows тоже не делает этого), и 3) мой не может различать разные типы неосновных весов сортировки, если они встречаются в разных разделах (например,«e-1é» vs «é1e-» - разделы до и после номера имеют разницу в диакритическом и пунктуационном весе).
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;
}
Подпись соответствует Comparison<string>
делегат:
string[] files = Directory.GetFiles(@"C:\");
Array.Sort(files, CompareNatural);
Вот класс-оболочка для использования в качестве 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);
}
}
Пример:
string[] files = Directory.EnumerateFiles(@"C:\")
.OrderBy(f => f, new CustomComparer<string>(CompareNatural))
.ToArray();
Вот хороший набор имен файлов, которые я использую для тестирования:
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();
Pure C # решение для linq orderby:
http: //zootfroot.blogspot. ком / 2009/09 / природно-рода-сравнить-с-orderby.html LINQ
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;
}
}
Мое решение:
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);
}
}
Полученные результаты:
1
a2
a3
a4
a10
b4
b5
b400
C1d
c1d2
Ответ Мэтью Хорсли - самый быстрый метод, который не меняет поведение в зависимости от того, на какой версии Windows работает ваша программа. Тем не менее, это может быть еще быстрее, если создать регулярное выражение один раз и использовать RegexOptions.Compiled. Я также добавил опцию вставки сравнения строк, чтобы вы могли игнорировать регистр, если это необходимо, и немного улучшил читабельность.
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);
}
Использовать
var sortedEmployees = employees.OrderByNatural(emp => emp.Name);
Для сортировки 100 000 строк требуется 450 мс по сравнению с 300 мс для сравнения строк по умолчанию .net - довольно быстро!
Вы должны быть осторожны - я смутно припоминаю, что читал, что StrCmpLogicalW или что-то в этом роде не было строго транзитивным, и я наблюдал, как методы сортировки .NET иногда застревают в бесконечных циклах, если функция сравнения нарушает это правило . р>
Транзитивное сравнение всегда сообщает, что < c если < b и b < с. Существует функция, которая выполняет естественное сравнение порядка сортировки, которое не всегда соответствует этому критерию, но я не могу вспомнить, является ли это StrCmpLogicalW или чем-то еще.
Это мой код для сортировки строки, состоящей из букв и цифр.
Во-первых, этот метод расширения:
public static IEnumerable<string> AlphanumericSort(this IEnumerable<string> me)
{
return me.OrderBy(x => Regex.Replace(x, @"\d+", m => m.Value.PadLeft(50, '0')));
}
Затем просто используйте его в любом месте своего кода следующим образом:
List<string> test = new List<string>() { "The 1st", "The 12th", "The 2nd" };
test = test.AlphanumericSort();
Как это работает? Заменив на нули:
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"
Работает с кратными числами:
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"
Надеюсь, это поможет.
Добавление в ответ Грега Бича (потому что я только что искал это), если вы хотите использовать это из Linq, вы можете использовать OrderBy
, который занимает IComparer
. Например:.
var items = new List<MyItem>();
// fill items
var sorted = items.OrderBy(item => item.Name, new NaturalStringComparer());
Вот сравнительно простой пример, который не использует 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));
}
}
На самом деле я реализовал его как метод расширения в 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;
}
}
}
Вот наивный однострочный способ LINQ без регулярных выражений (заимствован из python):
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"]
Расширяя пару предыдущих ответов и используя методы расширения, я пришел к следующему, у которого нет предостережений от потенциального множественного перечислимого перечисления или проблем с производительностью, связанных с использованием нескольких объектов регулярных выражений или вызовом регулярных выражений. Излишне, как говорится, он использует 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);
}
Вдохновленный решением Майкла Паркера, вот реализация 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);
}
}
Нам нужна была естественная сортировка для работы с текстом по следующей схеме:
"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+"
). Поскольку это потенциально дорогостоящая задача, она выполняется только один раз для каждой записи. Затем мы используем средство сравнения сопоставимых объектов (извините, я не могу найти более правильный способ сказать это). Он сравнивает каждый блок с соответствующим блоком в другой строке.
Я хотел бы получить отзывы о том, как это можно улучшить и каковы основные недостатки. Обратите внимание, что на данный момент для нас важна ремонтопригодность, и в настоящее время мы не используем это в чрезвычайно больших наборах данных.
Если ваш конечный код предназначен для Интернета (ASP.NET и т. д.), то естественную сортировку можно получить с помощью функции javascript localCampare
'10'.localeCompare('2', undefined, {numeric: true, sensitivity: 'base'})
Позвольте мне объяснить мою проблему и то, как я смог ее решить. Р>
Проблема: - Сортировка файлов на основе 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();