Calculate String Min Max Effectively

Jan 14, 2023 | 286 Words | 2 min |  #csharp #performance

Problem

Calculate minimum and maximum values of a Span<string> effectively

Solution

string min = span.IsEmpty ? default(string) : span[0];
string max = min;
foreach (string s in span) {
    int cmp = string.Compare(s, min);
    if (cmp < 0)
        min = s;

    cmp = string.Compare(s, max);
    if (cmp > 0)
        max = s;
}

Optimisation

string.Compare is not the fastest and should be used with caution. string.CompareOrdinal is about 6 times faster!. Proof with a benchmark:

[ShortRunJob]
[MinColumn, MaxColumn, MeanColumn, MedianColumn]
[MemoryDiagnoser]
[MarkdownExporter]
public class ArrayOps
{
    private static Random random = new Random();
    public static string RandomString(int length) {
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        return new string(Enumerable.Repeat(chars, length)
          .Select(s => s[random.Next(s.Length)]).ToArray());
    }
    
    private string[] _input;

	[GlobalSetup]
	public void Setup()
	{
        const int count = 1000000;
		_input = Enumerable.Range(0, count).Select(i => RandomString(100)).ToArray();
	}


	[Benchmark]
	public void Normal() {
        var span = _input.AsSpan();
        string min = span.IsEmpty ? default(string) : span[0];
        string max = min;
        foreach (string s in span) {
            int cmp = string.Compare(s, min);
            if (cmp < 0)
                min = s;
                
            cmp = string.Compare(s, max);
            if (cmp > 0)
                max = s;
        }
    }

    [Benchmark(Baseline=true)]
    public void Ordinal() {
        var span = _input.AsSpan();
        string min = span.IsEmpty ? default(string) : span[0];
        string max = min;
        foreach (string s in span) {
            int cmp = string.CompareOrdinal(s, min);
            if (cmp < 0)
                min = s;
            
            cmp = string.CompareOrdinal(s, min);
            if (cmp > 0)
                max = s;
        }
    }
}

Results:

Method Mean Error StdDev Min Max Median Ratio RatioSD Allocated Alloc Ratio
Normal 103.24 ms 42.108 ms 2.308 ms 101.13 ms 105.71 ms 102.89 ms 5.97 0.15 326 B 6.39
Ordinal 17.30 ms 5.440 ms 0.298 ms 17.03 ms 17.62 ms 17.25 ms 1.00 0.00 51 B 1.00

To contact me, send an email anytime or leave a comment below.

See Also