提高字符串数组的自定义排序性能

本文关键字：自定义 排序 性能 数组 字符串 | 更新日期: 2023-09-27 18:24:07

我正试图找到一种有效的方法，根据数组中每个字符串元素中的数值对字符串数组进行排序。我目前正在使用Array.Sort（Array，customComparer）静态方法（快速排序），我的自定义比较器类（按降序排序）为：

class StringComparer : IComparer<string>
{
    public int Compare(string a, string b)
    {
        string s1 = a;
        string s2 = b;
        Match matchA = Regex.Match(s1, @"'d+$");
        Match matchB = Regex.Match(s2, @"'d+$");
        long numberA = long.Parse(matchA.Value);
        long numberB = long.Parse(matchB.Value);
        if (numberB - numberA < 0)
        {
            return -1;
        }
        else 
        {
            return 1;
        }
    }
}

这工作得很好，但有时排序需要太多时间，在2.4Ghz处理器上，10万个字符串的数组需要一分钟以上的时间。我想知道是否有更有效的方法来实现这一点。例如，实现不同的排序算法或采用另一种方法，如使用字典并对值进行排序（值是字符串的数字部分）。有什么建议吗？提前感谢！

提高字符串数组的自定义排序性能

您正在分析每个比较的值。我建议您解析一次，以获得字符串/长对，对其进行排序，然后提取字符串部分。

请注意，您现有的代码有一个错误：如果两个字符串比较为相等，则永远不会返回0。

这里有一种使用LINQ的替代方法（它不是就地排序，但很简单。）

var sorted = unsorted.OrderBy(x => long.Parse(Regex.Match(x, @"'d+$").Value));
                     .ToList();

（OrderBy投影一次以获得密钥，然后比较密钥。）

您现在正在执行Regexes O（n log n）次。

考虑在所有字符串上循环一次，提取数值并将其添加到SortedDictionary<long, string>

这只需要Reg表达式的O（n）次执行。排序的其余部分应该是可比较的。

首先，您不必要地一次又一次地解析同一个字符串（既与正则表达式匹配，又解析匹配项）。相反，将您所拥有的封装到一个自定义类型中，这样您只需要解析一次。

public class FooString {
    private readonly string foo;
    private readonly long bar;
    public FooString(string foo) {
        this.foo = foo;
        Match match = Regex.Match(foo, @"'d+$");
        this.bar = Int64.Parse(match.Value);
    }
    public string Foo { get { return this.foo; } }
    public long Bar { get { return this.bar; } }
}

我甚至会在这个类中添加一个Contract.Requires，说明foo必须满足正则表达式。

其次，您有一个IComparer<T>，它依赖于T的某些值（在您的情况下，string与正则表达式不匹配，无法解析为long）。这通常是个坏主意。

因此，为FooString:制作比较器

public FooStringComparer : IComparer<FooString> {
    public int Compare(FooString a, FooString b) {
        Contract.Requires(a != null);
        Contract.Requires(b != null);
        return a.Bar.CompareTo(b.Bar);
    }
}

现在，您的排序将非常快，因为您已经停止了一次又一次地解析同一个字符串。

使用Compiled选项只创建一次Regex。这将提高速度。

class StringComparer : IComparer<string>
{
    private static Regex _regex = new Regex(@"'d+$", RegexOptions.Compiled);
    public int Compare(string a, string b)
    {
        long numberA = Int64.Parse(_regex.Match(a).Value);
        long numberB = Int64.Parse(_regex.Match(b).Value);
        return numberA.CompareTo(numberB);
    }
}
相关文章：