如何在不解析的情况下对数字字符串列表进行排序？

Question

我有一个高值(大于int 32)的字符串列表,如何在不解析的情况下按升序对它们进行排序？

List = {"4852154879","2652154879","9852154879","1952154879","0652154879"}

我尝试解析如下,但寻找替代和更好的方法,而无需解析

Sorted List = List.OrderBy(x => long.Parse(x.serialNumber)).ToList();

Answer 1

首先,我几乎肯定不会采取以下方法.我要么将输入转换为a List<long>,要么只使用你已经获得的代码,至少在我完全证明它不够好之前.

但是,由于这是一个非常有趣的问题,让我们试着写一个快速的IComparer<T>.这取决于:

• 没有负面价值
• 可能零填充,但没有其他填充
• 假设所有值都有效

比较两个值时,如果值的长度相同,我们可以使用序数字符串比较.除此以外:

• 找出每个字符串中前导零的数量,以计算出每个字符串的"逻辑"长度
• 如果得到的逻辑长度不同,则较长者中的较大者
• 否则,比较前导零之后的字符串

这设法在没有对象分配的情况下执行每次比较.

像(完全未经测试)的东西:

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

    private NumericComparer() {}

    public int Compare(string x, string y)
    {
        if (x.Length == y.Length)
        {
            return string.Compare(x, y, StringComparison.Ordinal);
        }
        int xIndex = FindFirstNonZeroIndex(x);
        int yIndex = FindFirstNonZeroIndex(y);
        int lengthComparison = (x.Length - xIndex).CompareTo(y.Length - yIndex);
        if (lengthComparison != 0)
        {
            return lengthComparison;
        }
        return string.Compare(x, xIndex, y, yIndex, x.Length, StringComparison.Ordinal);
    }

    private static int FindFirstNonZeroIndex(string text)
    {
        for (int i = 0; i < text.Length; i++)
        {
            if (text[i] != '0')
            {
                return i;
            }
        }
        // All zeroes? Return text.Length - 1, so that we treat this as
        // "0".
        return text.Length - 1;
    }
}

然后,您可以使用以下内容对列表进行排序:

list.Sort(NumericComparer.Instance);

现在我刚刚对此进行了基准测试......就我所知,它看起来与解析的性能大致相同.实际上非常差 - 但比填充形式要好得多.

基准代码:

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

public class Program
{
    private readonly List<string> list;

    public Program()
    {
        list = Enumerable.Range(0, 100000)
            .Select(_ => GenerateValue())
            .ToList();
    }

    // Just to test the impact of copying...
    [Benchmark]
    public List<string> NoSorting()
    {
        var copy = new List<string>(list);
        return copy;
    }

    [Benchmark]
    public List<string> NoParsing()
    {
        var copy = new List<string>(list);
        copy.Sort(NumericComparer.Instance);
        return copy;
    }

    [Benchmark]
    public List<string> WithParsing() => list.OrderBy(x => long.Parse(x)).ToList();

    static void Main(string[] args)
    {
        BenchmarkRunner.Run<Program>();
    }

    [Benchmark]
    public List<string> WithPadding()
    {
        int maxLength = list.Max(y => y.Length);
        return list.OrderBy(x => x.PadLeft(maxLength, '0')).ToList();
    }        

    // Use the same seed on all tests
    static readonly Random random = new Random(1);
    static string GenerateValue()
    {
        // Up to 11 digits...
        long leading = random.Next(100000);
        long trailing = random.Next(1000000);
        long value = leading * 1000000 + trailing;
        // Pad to 9, 10 or 11 randomly
        int width = random.Next(3) + 9;
        return value.ToString().PadLeft(width, '0');
    }
}
// NumericComparer as per post

结果:

      Method |         Mean |        Error |      StdDev |
------------ |-------------:|-------------:|------------:|
   NoSorting |     473.3 us |     9.359 us |    25.62 us |
   NoParsing |  46,684.7 us |   932.466 us | 1,366.80 us |
 WithParsing |  43,149.8 us |   790.116 us |   700.42 us |
 WithPadding | 275,843.4 us | 3,083.376 us | 2,733.33 us |

另类想法,这绝对更简单:

• 如果字符串长度相同,则按顺序进行比较
• 否则,只需解析两者

(我还没有对此进行基准测试.)