Skip to content

Instantly share code, notes, and snippets.

@mstum
Last active April 17, 2023 15:02
Show Gist options
  • Save mstum/63a6e3e8cf54e8ae55b6aa28ca6f20c5 to your computer and use it in GitHub Desktop.
Save mstum/63a6e3e8cf54e8ae55b6aa28ca6f20c5 to your computer and use it in GitHub Desktop.
Fully Managed alternative to StrCmpLogicalW
BenchmarkDotNet=v0.10.13, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.309)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical cores and 4 physical cores
Frequency=2531253 Hz, Resolution=395.0613 ns, Timer=TSC
[Host] : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
Clr : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
Job=Clr Runtime=Clr
Method | Mean | Error | StdDev | Allocated |
---------------------------- |---------:|---------:|---------:|----------:|
LexicographicStringComparer | 276.0 us | 5.419 us | 8.595 us | 28 B |
StrCmpLogicalW | 295.2 us | 5.897 us | 9.181 us | 28 B |
BenchmarkDotNet=v0.10.13, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.309)
Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical cores and 4 physical cores
Frequency=2531253 Hz, Resolution=395.0613 ns, Timer=TSC
.NET Core SDK=2.1.101
[Host] : .NET Core 2.0.6 (CoreCLR 4.6.26212.01, CoreFX 4.6.26212.01), 64bit RyuJIT
Core : .NET Core 2.0.6 (CoreCLR 4.6.26212.01, CoreFX 4.6.26212.01), 64bit RyuJIT
Job=Core Runtime=Core
Method | Mean | Error | StdDev | Allocated |
---------------------------- |---------:|---------:|---------:|----------:|
LexicographicStringComparer | 124.5 us | 1.617 us | 1.512 us | 88 B |
StrCmpLogicalW | 119.0 us | 2.215 us | 1.849 us | 88 B |
using System;
using System.Collections.Generic;
namespace stuff
{
/// <summary>
/// A string comparer that behaves like StrCmpLogicalW
/// https://msdn.microsoft.com/en-us/library/windows/desktop/bb759947
///
/// This means:
/// * case insensitive (ZA == za)
/// * numbers are treated as numbers (z20 &gt; z3) and assumed positive
/// (-100 comes AFTER 10 and 100, because the minus is seen
/// as a char, not as part of the number)
/// * leading zeroes come before anything else (z001 &lt; z01 &lt; z1)
///
/// Note: Instead of instantiating this, you can also use
/// <see cref="Comparison(string, string)"/>
/// if you don't need an <see cref="IComparer{string}"/> but can
/// use a <see cref="Comparison{string}"/> delegate instead.
/// </summary>
/// <remarks>
/// NOTE: This behaves slightly different than StrCmpLogicalW because
/// it handles large numbers.
///
/// At some point, StrCmpLogicalW just gives up trying to parse
/// something as a number (see the Test cases), while we keep going.
/// Since we want to sort lexicographily as much as possible,
/// that difference makes sense.
/// </remarks>
public class LexicographicStringComparer : IComparer<string>
{
/// <summary>
/// A <see cref="Comparison{string}"/> delegate.
/// </summary>
public static int Comparison(string x, string y)
{
// 1 = x > y, -1 = y > x, 0 = x == y
// Rules: Numbers < Letters. Space < everything
if (x == y) return 0;
if (string.IsNullOrEmpty(x) && !string.IsNullOrEmpty(y)) return -1;
if (!string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 1;
if (string.IsNullOrEmpty(x) && string.IsNullOrEmpty(y)) return 0; // "" and null are the same for the purposes of this
var yl = y.Length;
for (int i = 0; i < x.Length; i++)
{
if (yl <= i) return 1;
var cx = x[i];
var cy = y[i];
if (Char.IsWhiteSpace(cx) && !Char.IsWhiteSpace(cy)) return -1;
if (!Char.IsWhiteSpace(cx) && Char.IsWhiteSpace(cy)) return 1;
if (IsDigit(cx))
{
if (!IsDigit(cy))
{
return -1;
}
// Both are digits, but now we need to look at them as a whole, since
// 10 > 2, but 10 > 002 > 02 > 2
var numCmp = CompareNumbers(x, y, i, out int numChars);
if (numCmp != 0) return numCmp;
i += numChars; // We might have looked at more than one char, e.g., "10" is 2 chars
}
else if (IsDigit(cy))
{
return 1;
}
else
{
// Do this after the digit check
// Case insensitive
// Normalize to Uppercase:
// https://docs.microsoft.com/en-US/visualstudio/code-quality/ca1308-normalize-strings-to-uppercase
var cmp = Char.ToUpper(cx).CompareTo(Char.ToUpper(cy));
if (cmp != 0) return cmp;
}
}
// Strings are equal to that point, and y is at least as large as x
if (y.Length > x.Length) return -1;
return 0;
}
/// <see cref="IComparer{T}.Compare(T, T)"/>
public int Compare(string x, string y)
=> Comparison(x, y);
private static int CompareNumbers(string x, string y, int ix, out int numChars)
{
var xParsed = ParseNumber(x, ix);
var yParsed = ParseNumber(y, ix);
numChars = yParsed.NumCharsRead > xParsed.NumCharsRead
? xParsed.NumCharsRead
: yParsed.NumCharsRead;
return xParsed.CompareTo(yParsed);
}
private unsafe static ParsedNumber ParseNumber(string str, int offset)
{
var result = 0;
var numChars = 0;
var leadingZeroes = 0;
var numOverflows = 0;
bool countZeroes = true;
fixed (char* strPtr = str)
{
for (int j = offset; j < str.Length; j++)
{
char c = *(strPtr + j);
if (IsDigit(c))
{
var cInt = (c - 48); // 48/0x30 is '0'
checked
{
long tmp = (result * 10L) + cInt;
if (tmp > int.MaxValue)
{
numOverflows++;
tmp = tmp % int.MaxValue;
}
result = (int)tmp;
numChars++;
}
if (cInt == 0 && countZeroes)
{
leadingZeroes++;
}
else
{
countZeroes = false;
}
}
else
{
break;
}
}
}
return new ParsedNumber(result, numOverflows, leadingZeroes, numChars);
}
private static bool IsDigit(char c) => (c >= '0' && c <= '9');
/// <summary>
/// Note that the ParsedNumber is not very useful as a number,
/// but purely as a way to compare two numbers that are stored in a string.
/// </summary>
private struct ParsedNumber : IComparable<ParsedNumber>, IComparer<ParsedNumber>
{
/// <summary>
/// The remainder, that is, the part of the number that
/// didn't overflow int.MaxValue.
/// </summary>
public int Remainder;
/// <summary>
/// How often did the number overflow int.MaxValue during parsing?
/// </summary>
public int Overflows;
/// <summary>
/// How many leading zeroes were there in the string during parsing?
/// "001" has a LeadingZeroesCount of 2.
/// "100" has a LeadingZeroesCount of 0.
/// "010" has a LeadingZeroesCount of 1.
///
/// This is important, because 001 comes before 01 comes before 1.
/// </summary>
public int LeadingZeroesCount;
/// <summary>
/// How many characters were read from the input during parsing?
/// </summary>
public int NumCharsRead;
public ParsedNumber(int remainder, int overflows, int leadingZeroes, int numChars)
{
Remainder = remainder;
Overflows = overflows;
LeadingZeroesCount = leadingZeroes;
NumCharsRead = numChars;
}
public int Compare(ParsedNumber x, ParsedNumber y)
{
// Note: if numCharsX and Y aren't equal, this doesn't matter
// as the return value will be either -1 or 1 anyway
if (x.Overflows > y.Overflows) return 1;
if (x.Overflows < y.Overflows) return -1;
// 001 > 01 > 1
if (x.Remainder == y.Remainder)
{
if (x.LeadingZeroesCount > y.LeadingZeroesCount) return -1;
if (x.LeadingZeroesCount < y.LeadingZeroesCount) return 1;
}
if (x.Remainder > y.Remainder) return 1;
if (x.Remainder < y.Remainder) return -1;
return 0;
}
public int CompareTo(ParsedNumber other)
=> Compare(this, other);
}
}
}
using System.Collections.Generic;
using System.Linq;
using Xunit;
namespace stuff.Tests
{
public class LexicographicStringComparerTests
{
[Fact]
public void SortsLexicopgrahicly()
{
List<string> testItems = new[]{"👾", "z24", "a1", "z2", "z2", "z15", "z1", "🤑",
"z3", "z20", "z5", "", "z1a", "za1", "z11", "z 21", "z22", "z a", "za0",
"za05", "za01", "za10", "za001", "za005", "ZA7",
"za100vx100", "za200vx100","za100vx200","za200vx200",
"za100vx20", "za10vx200","za20vx100","za200vx10"
}.ToList();
var expectedOrder = new[] { "",
"a1", "z 21", "z a", "z1", "z1a", "z2", "z2", "z3", "z5",
"z11", "z15", "z20", "z22", "z24", "za0", "za001", "za01", "za1",
"za005", "za05", "ZA7", "za10",
"za10vx200", "za20vx100", "za100vx20", "za100vx100",
"za100vx200", "za200vx10", "za200vx100","za200vx200",
"👾", "🤑"};
testItems.Sort(LexicographicStringComparer.Comparison);
Assert.Equal(expectedOrder, testItems);
}
[Fact]
public void DealsWithOverflow()
{
List<string> testItems = new[]{"a2147483648z",
"a2147483647z",
"a2147483646z",
"a2147483649z",
}.ToList();
var expectedOrder = new[] { "a2147483646z", "a2147483647z",
"a2147483648z","a2147483649z",};
testItems.Sort(LexicographicStringComparer.Comparison);
Assert.Equal(expectedOrder, testItems);
}
[Fact]
public void DealsWithHugeOverflow()
{
// NOTE: This behaves slightly different than StrCmpLogicalW because
// it handles large numbers.
//
// Here, 5 comes first and 401 comes last (before the really long ones)
// 5, 39, 40, 41, 401
//
// Windows however sorts them like this:
// 39, 40, 401, 41, 5
//
// So Windows just gives up parsing them as a number at some point.
// Since we want to sort lexicographily as much as possible,
// we keep on treating them as numbers.
List<string> testItems = new[]{"340282366920938463444927863358058659839",
"340282366920938463444927863358058659840",
"3402823669209384634449278633580586598401",
"340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401",
"340282366920938463444927863358058659841",
"abc340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
"ab340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
"bcd340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
"34028236692093846344492786335805865985"
}.ToList();
var expectedOrder = new[] { "34028236692093846344492786335805865985",
"340282366920938463444927863358058659839",
"340282366920938463444927863358058659840",
"340282366920938463444927863358058659841",
"3402823669209384634449278633580586598401",
"340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401",
"ab340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
"abc340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz",
"bcd340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401340282366920938463444927863358058659840134028236692093846344492786335805865984013402823669209384634449278633580586598401xyz" };
testItems.Sort(LexicographicStringComparer.Comparison);
Assert.Equal(expectedOrder, testItems);
}
[Fact]
public void LeadingZeroes()
{
List<string> testItems = new[] { "1", "0002", "002", "02", "001", "01", "0030", "2", "003", "03", "3", "0031" }.ToList();
var expectedOrder = new[] { "001", "01", "1", "0002", "002", "02", "2", "003", "03", "3", "0030", "0031" };
testItems.Sort(LexicographicStringComparer.Comparison);
Assert.Equal(expectedOrder, testItems);
}
}
}
@lwchkg
Copy link

lwchkg commented Jul 12, 2020

BTW, to test it: just go to https://rextester.com/, start a new C# program, and copy the following there:

            string s = "1234";
            Console.WriteLine(s[0]);
            Console.WriteLine(s[1]);
            Console.WriteLine(s[2]);
            Console.WriteLine(s[3]);

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment