[C#] 文字列を数値の大きさで並び替える自然ソートを行う
Windows エクスプローラーのファイル順と同じように、文字列中の数字を値の大きさでソートします。OS に依存しない実装も対応します。
環境
- .NET 6.0.10 (SDK 6.0.402)
- C# 10.0
- Visual Studio 2022 Version 17.3.6
- Windows 10 Pro 64bit 22H2 19045.2251
結果
1. Windows 用: エクスプローラーと同じ並び順 (Win32 API)
Win32 API StrCmpLogicalW()
を使用します。数値部分を値比較するように自然ソートになりますが、仕様が特殊のようです (後述)。
using System.Runtime.InteropServices;
public class NaturalStringComparer : IComparer<string?>
{
public static IComparer<string?> Windows { get; } = new NaturalStringComparer();
[DllImport("shlwapi.dll", CharSet = CharSet.Unicode, ExactSpelling = true)]
private static extern int StrCmpLogicalW(string x, string y);
private NaturalStringComparer()
{
}
public int Compare(string? x, string? y)
{
if (ReferenceEquals(x, y)) return 0;
if (x is null) return -1;
if (y is null) return 1;
return StrCmpLogicalW(x, y);
}
}
使用例
// Array
var array = new[] { "name1", "name2", "name01" };
Array.Sort(array, NaturalStringComparer.Windows);
// List
var list = new List<string> { "name1", "name2", "name01" };
list.Sort(NaturalStringComparer.Windows);
// LINQ
var enumerable = new[] { "name1", "name2", "name01" };
var sortedArray = enumerable.OrderBy(x => x, NaturalStringComparer.Windows).ToArray();
2. Win32 API を使用しない版 (仮実装)
1 の StrCmpLogicalW()
は
- Windows 限定 (Win32 API)
- 大文字と小文字を区別しない
のような課題があるので、依存しない形で実装してみます。
使用例
var array = new[] { "name1", "name2", "name01" };
Array.Sort(array, NaturalStringComparer.Ordinal);
特徴
StrCmpLogicalW()
と同じような並び順になるように努力。null
を正しく比較する (後述1)。- 大文字と小文字も区別して並び替え (後述2)。
string.Substrings()
などは使用せず、文字列のアロケーションなし。NaturalStringComparer.Ordinal
などで static インスタンスを共有可能。
⚠️ ただし、中途半端な実装コードなので、全く同じ並び順にはならないことに注意してください。
public static class NaturalStringComparer
{
public static IComparer<string?> Windows { get; } = new WindowsComparer();
public static IComparer<string?> Ordinal { get; } = new DefaultComparer(StringComparison.Ordinal);
public static IComparer<string?> OrdinalIgnoreCase { get; } = new DefaultComparer(StringComparison.OrdinalIgnoreCase);
private class WindowsComparer : IComparer<string?>
{
[DllImport("shlwapi.dll", CharSet = CharSet.Unicode, ExactSpelling = true)]
private static extern int StrCmpLogicalW(string x, string y);
public int Compare(string? x, string? y)
{
if (ReferenceEquals(x, y)) return 0;
if (x is null) return -1;
if (y is null) return 1;
return StrCmpLogicalW(x, y);
}
}
private class DefaultComparer : IComparer<string?>
{
private const char IgnoreChar = '-';
// Token values (not an enum as a performance micro-optimization)
private static class Token
{
internal const byte None = 0;
internal const byte Ignore = 1;
internal const byte OtherPunctuation = 2;
internal const byte MathSymbol = 3;
internal const byte Other = 2;
internal const byte Digits = 4;
internal const byte Number = 5;
internal const byte Letters = 6;
}
private readonly StringComparison _stringComparison;
internal DefaultComparer(StringComparison stringComparison)
{
_stringComparison = stringComparison;
}
public int Compare(string? str1, string? str2)
{
if (ReferenceEquals(str1, str2)) return 0;
if (str1 is null) return -1;
if (str2 is null) return 1;
var nextStartIndex1 = 0;
var nextStartIndex2 = 0;
while (true)
{
// token
var (token1, startIndex1, length1) = GetNextToken(str1, nextStartIndex1);
var (token2, startIndex2, length2) = GetNextToken(str2, nextStartIndex2);
var tokenCompare = token1.CompareTo(token2);
if (tokenCompare != 0)
return tokenCompare;
if (token1 == Token.None)
return str1.Length.CompareTo(str2.Length);
if (token1 == Token.Digits)
{
// '0' pad left
var maxLength = Math.Max(length1, length2);
var paddingLength1 = maxLength - length1;
var paddingLength2 = maxLength - length2;
for (var i = 0; i < maxLength; i++)
{
var digit1 = i < paddingLength1 || str1[startIndex1 + i - paddingLength1] == IgnoreChar ? 0 : CharUnicodeInfo.GetNumericValue(str1[startIndex1 + i - paddingLength1]);
var digit2 = i < paddingLength2 || str2[startIndex2 + i - paddingLength2] == IgnoreChar ? 0 : CharUnicodeInfo.GetNumericValue(str2[startIndex2 + i - paddingLength2]);
var digitCompare = digit1.CompareTo(digit2);
if (digitCompare != 0)
return digitCompare;
}
var paddingCompare = paddingLength1.CompareTo(paddingLength2);
if (paddingCompare != 0)
return paddingCompare;
}
else
{
var minLength = Math.Min(length1, length2);
var compare = string.Compare(str1, startIndex1, str2, startIndex2, minLength, _stringComparison);
if (compare == 0)
{
compare = length1 - length2;
}
if (compare != 0)
return compare;
}
nextStartIndex1 += length1;
nextStartIndex2 += length2;
}
}
private static (byte token, int startIndex, int length) GetNextToken(string str, int startIndex)
{
if (startIndex >= str.Length)
{
return (Token.None, -1, 0);
}
// - があれば無視して、次の文字を採用する
// ただし、文末まで - の場合は、- としてソート先頭にする
if (str[startIndex] == IgnoreChar)
{
for (var i = startIndex + 1; i < str.Length; i++)
{
if (str[i] != IgnoreChar)
{
// - 以外の文字があったので、- を無視して次の文字で判定する
return GetNextToken(str, i);
}
}
// 全て - で構成されていた場合
return (Token.Ignore, startIndex, str.Length - startIndex);
}
// 次の文字が - で始まらない場合
var token = GetTokenFromChar(str[startIndex]);
var length = 1;
for (var i = startIndex + 1; i < str.Length; i++)
{
var charToken = GetTokenFromChar(str[i]);
if (token != charToken)
{
break;
}
length++;
}
// 半角/全角は数値として比較する
// ただし、半角/全角が異なるところを区切りにして比較するので、Token は Digits と TokenNumber で分けている
if (token == Token.Number)
token = Token.Digits;
return (token, startIndex, length);
}
// 仮実装 (カスタマイズの余地あり)
private static byte GetTokenFromChar(char c)
{
if (c is >= '0' and <= '9') return Token.Digits;
if (char.IsNumber(c)) return Token.Number;
if (char.IsLetter(c)) return Token.Letters;
return CharUnicodeInfo.GetUnicodeCategory(c) switch
{
UnicodeCategory.MathSymbol => Token.MathSymbol,
UnicodeCategory.OtherPunctuation => Token.OtherPunctuation,
_ => Token.Other,
};
}
}
}
3. NaturalSort.Extension (NuGet)
NuGet にある中で一番良さそうです。
- https://www.nuget.org/packages/NaturalSort.Extension
- https://github.com/tompazourek/NaturalSort.Extension
特徴
- ✅
.NET 6.0
,.NET Standard 1.3
対応 - ✅
TryParse()
などのパース処理なし。 - ✅ 数字が大量に連続していても比較可能 (
long.MaxValue
を超えた数値でも1文字ずつ比較するので問題なし)。 - ✅
StringComparison
を指定すれば、文字列のアロケーション無し。 - ⚠️
StringComparer
(StringComparer.Ordinal
も含む) を指定した場合は、string.Substrings()
によるアロケーションが発生する。 - ⚠️
WithNaturalSort()
を使用すると、NaturalSortComparer
のアロケーションが発生する。
4. 日本語を考慮した自然ソート
漢数字、ローマ数字、半角全角、前中後・上中下などの並び順まで対応されています。
さらに、バグが修正されているコードのようです。
StrCmpLogicalW の不具合
Windows のバージョンにより結果が異なり、古い Windows (XP, Vista あたり) の時代だとバグがあったらしい。
- 拡張子が考慮されていなかったらしい。
- 古い Windows (Vista, 7あたり?)では無限ループするバグがあったらしい。
- Vista では別の並べ替えアルゴリズムだったらしい。
StrCmpLogicalW の注意点と特徴
StrCmpLogicalW()
を使用していて、気付いた特徴と注意点を記載しておきます。
色々と複雑な判定を行っていそうなソートに見えます。
1. null 比較は正しくない
まず、一番大事と思われる注意点です。
null
を比較対象に含むと、常に -2
が返されてしまいます。
// "" は正しく 0 になる
StrCmpLogicalW("", ""); // 0
// どちらかに null を含むと、常に -2 になってしまう
StrCmpLogicalW(null, null); // -2
StrCmpLogicalW(null, ""); // -2
StrCmpLogicalW("", null); // -2
本来 C# の判定では、null
同士なら等しく、片方が null
の場合は null
の方が小さい値としてみなされます。
string.CompareOrdinal() の注釈を参考。
// null 同士でも同じ値なら正しく 0 になる
string.CompareOrdinal.Compare("", ""); // 0
string.CompareOrdinal.Compare(null, null); // 0
// どちらかが null だと null の方が小さい値と判定される
string.CompareOrdinal.Compare(null, ""); // -1
string.CompareOrdinal.Compare("", null); // 1
null
を考慮した比較にしたいので、以下のように実装しました。
public int Compare(string? x, string? y)
{
// null を考慮した正しい比較をする
if (ReferenceEquals(x, y)) return 0;
if (x is null) return -1;
if (y is null) return 1;
// 両方が null ではない場合の比較をする
return StrCmpLogicalW(x, y);
}
ただ、StrCmpLogicalW()
をファイル名のソートで使用するなら問題ありません。
ファイル名が null
のファイルは作成自体できないため、存在すらありえないためです。
2. 大文字、小文字は区別しない
StrCmpLogicalW()
は OrdinalIgnoreCase
と同様に、大文字と小文字を区別せずに等しいと判定されてしまいます。
// 大文字と小文字を区別しないので、等しいと判定されるので 0 となる
StrCmpLogicalW("a", "A"); // 0
StringComparer.OrdinalIgnoreCase.Compare("a", "A"); // 0
// Ordinal では、大文字と小文字を区別するので 0 ではない
StringComparer.Ordinal.Compare("a", "A"); // 32
例えば、大文字と小文字の違いで同じ名前を含む場合のソートは以下のようになります。
// 大文字と小文字の違いで、同じ名前がある場合のソート
var array = new[] { "name", "NAME", "name" };
// 1. StrCmpLogicalW
Array.Sort(array, NaturalStringComparer.Windows);
// 2. OrdinalIgnoreCase
Array.Sort(array, StringComparer.OrdinalIgnoreCase);
// 3. Ordinal
Array.Sort(array, StringComparer.Ordinal);
StrCmpLogicalW()
は、name
が1番目と3番目に並んでしまいます。Ordinal
は、小文字の name
が連続で並びます。
入力文字列 | 1. StrCmpLogicalW | 2. OrdinalIgnoreCase | 3. Ordinal |
---|---|---|---|
name | name | name | NAME |
NAME | NAME | NAME | name |
name | name | name | name |
ただ、StrCmpLogicalW()
をファイル名のソートで使用するなら問題ありません。
ファイルは大文字と小文字を区別しないため、そもそも大文字と小文字の違いで同名のファイルは作成できないためです。
3. 数値は整数として比較され、小数点は考慮されない
まずは、整数でソートした場合です。
var array = new[] { "02", "01", "10", "2", "1" };
Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
StrCmpLogicalW()
では、整数の大きさで並び替わります。Ordinal
は、文字列順です。
入力文字列 | 1. StrCmpLogicalW() | 2. Ordinal |
---|---|---|
02 | 01 | 01 |
01 | 1 | 02 |
10 | 02 | 1 |
2 | 2 | 10 |
1 | 10 | 2 |
次に、小数点を含めてソートした場合です。
var array = new[] { "1.02", "1.01", "1.10", "1.2", "1.1" };
Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列 | 1. StrCmpLogicalW() | 2. Ordinal |
---|---|---|
1.02 | 1.01 | 1.01 |
1.01 | 1.1 | 1.02 |
1.10 | 1.02 | 1.1 |
1.2 | 1.2 | 1.10 |
1.1 | 1.10 | 1.2 |
StrCmpLogicalW()
は .
で区切り、小数点以下の部分のみを整数として比較しています。
小数点以下の部分のソート結果は 01, 1, 02, 2, 10
の順になります。
IP アドレスのように ###.###.###.###
の形式でソートした場合、.
で区切り、それぞれの数値の大きさでソートされるようになります。
4. 連続のハイフンは1文字として扱われる
1文字のハイフンで検証
小数点の例と同じコードを、.
ではなく -
区切りでソートした場合です。
var array = new[] { "1-02", "1-01", "1-10", "1-2", "1-1" };
Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列 | 1. StrCmpLogicalW() | 2. Ordinal |
---|---|---|
1-02 | 1-01 | 1-01 |
1-01 | 1-1 | 1-02 |
1-10 | 1-02 | 1-1 |
1-2 | 1-2 | 1-10 |
1-1 | 1-10 | 1-2 |
-
区切りでも、.
区切りの時と同じ結果です。
複数のハイフンで検証
ここで -
の数を増やしてみます。
var array = new[] { "1-02", "1----01", "1--10", "1-----2", "1---1" };
Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列 | 1. StrCmpLogicalW() | 2. Ordinal |
---|---|---|
1-02 | 1----01 | 1-----2 |
1----01 | 1---1 | 1----01 |
1--10 | 1-02 | 1---1 |
1-----2 | 1-----2 | 1--10 |
1---1 | 1--10 | 1-02 |
StrCmpLogicalW()
は、.
区切りの時と同じ結果です。-
が複数個あっても、-
1個の時と同じ結果です。
Ordinal
は、-
の数が多い方が先にソートされます。
数字(0
-9
)より -
の方が小さい文字と判定されるため、先にソートされます。
感謝
Issue
Wiki
NuGet (.NET 6 対応)
- NuGet Gallery | NaturalSort.Extension 3.2.0
- tompazourek/NaturalSort.Extension: 🔀 Extension method for StringComparison that adds support for natural sorting (e.g. “abc1”, “abc2”, “abc10” instead of “abc1”, “abc10”, “abc2”).
NuGet (.NET 5 対応) unsafe
使用, int
で数値比較
- NuGet Gallery | GihanSoft.String.NaturalComparer 2.1.1
- GihanSoft/NaturalStringComparer: LINQ like method and Comparer
that can be used to sort strings by number in them (like what windows explorer do {“text1”, “text2”, “text10”} instead of {“text1”, “text10”, “text2”}). pure C# with .NET Standard. Fast because of internal unmanaged code.
NuGet (割当なしの比較、0パディングなしで比較)
- NuGet Gallery | NaturalSort 0.2.0
- drewnoakes/natural-sort: A .NET string comparer that orders integers within strings correctly.
GitHub
Regex
,decimal.ParseTry()
,DateTime.TryParse()
使用,IComparer<object>
実装char.ToString()
,Convert.ToDouble()
,Boxing
発生あり, 小数点考慮あり
日本語記事
StrCmpLogicalW()
使用- Windows C#で自然順ソート(Natural Sort Order in C#) - 物理の駅 by 現役研究者
- Windowsのファイル名順と同じ順にソート その4(補足) | アニメとか好きだから
- 拡張子の除いて比較することの注意点あり
- UNICODE にならん | Paepoi Blog
- 無限ループする問題が解決したと記載あり
string.Substring()
,ulong.TryParse()
使用StrCmpLogicalW()
,Regex
,double.TryParse()
使用
日本語に対応した実装
StrCmpLogicalW()
使用
StrCmpLogicalW()
を使用しない実装
- extern - C#: Implementation of, or alternative to, StrCmpLogicalW in shlwapi.dll - Stack Overflow
Regex
使用Regex
,double.TryParse()
使用
Win32
- StrCmpLogicalW function (shlwapi.h) - Win32 apps | Microsoft Docs
- Handling Sorting in Your Applications - Win32 apps | Microsoft Docs
Stack Overflow
sorting - Natural Sort Order in C# - Stack Overflow
StrCmpLogicalW()
XP, Vista の並び替え変更点string.Substring()
,decimal.TryParse()
使用Regex
,int.TryParse()
使用int.TryParse()
使用、ReadOnlySpan<char> の Enumerator
実装ありStrCmpLogicalW()
,int.Parse()
使用
Unity
- Unity - Scripting API: EditorUtility.NaturalCompare
- UnityCsReference/EditorUtility.bindings.cs at master · Unity-Technologies/UnityCsReference
- UnityCsReference/EditorUtility.bindings.cs at master · Unity-Technologies/UnityCsReference
- Sorting Numerical List - Unity Forum
他言語
関連記事
新着記事