C# 中快速 List<String> 排序

• 下载 SortTests.zip - 289.2 KB

引言

在搜索如何在 .NET 集合中加速字符串排序时，我偶然发现了这篇文章：C# 和 F# 中的快速字符串排序 

我从文章中下载了 StringSort 类，测试了速度，发现它对 50,000 个字符串进行排序的时间比通用的 IEnumerable 对象排序方法少约 40% 到 50%。 当比较方法与 Ordinal 选项一起使用时，情况就是这样。 否则，对于标准快速排序字符串排序，结果会差很多。

使用代码 

对于您的 List<string> 对象，您只需使用 sfList 代替。 唯一不同的是它用于排序字符串的方法。

using System;
using System.Collections.Generic;
using Sorting.CSharpStringSort;

namespace SortTests.Sorting
{
  public class sfList : List<string>
  {
    public sfList() : base() { }

    public sfList(int size) : base(size) { }

    public sfList(IEnumerable<String> aArray) : base(aArray) { }

    public new void Sort()
    {
      //StringSort.Sort(this);
      string[] a = this.ToArray();
      this.Clear();
      //sort array and refill contents of this (faster than directly sorting List)
      StringSort.Sort(ref a);
      this.AddRange(a);
    }
  }
}

从我的初步测试中，我可以看到将 List 复制到 string[]、清除列表、使用 StringSort.Sort 对数组进行排序并使用结果重新填充列表更快。 这就是通过用我对 StringSort.Sort 的调用替换 List.Sort 方法来完成的。 与排序时间相比，用于执行两个额外复制的时间非常少。

已更改 StringSort 类的 Sort 方法，以便对 string[] 执行就地 Sort。

还有一个 Sort 的重载版本，它接受一个未排序的 List<string> 参数并返回一个排序列表的副本。

public static void Sort(string[] inout)
{
    InPlaceSort(inout, 0, 0, inout.Length);
}

public static List<string> Sort(List<string> sList)
{
  string[] aCopy = sList.ToArray();
  InPlaceSort(aCopy, 0, 0, aCopy.Length);
  return new List<string>(aCopy);
}

我的原始发布版本中已删除其他实验性重载和未使用的私有方法。

首次运行 SortTests.exe 时，它会通过多次读取 dic.txt 来生成一个随机值列表以进行排序。 随机数也会附加到原始字符串值。

更多泛型集合

我包含了一个从 List<T> 派生的 KeyedList<TKey, TValue> 类。

我使用快速字符串排序算法实现了该类的 Sort 方法，效果很好。

例如，将 KeyedList 填充值然后对其进行排序的总时间比将相同的值添加到 SortedList<string, string> 集合中要快得多。

这是使用 Sort 方法重载对字符串键上的 KeyValuePair 数组进行排序的排序方法： 

    /// <summary>
    /// Use for default sorting on int or string keys
    /// </summary>
    public new void Sort()
    {
      if (typeof(TKey) == typeof(String))
      {
        KeyValuePair<TKey, TValue>[] kvpArray = this.ToArray();
        this.Clear();
        this.Sort(kvpArray); //sort String key type
        this.AddRange(kvpArray);
        if (!this.SortAscd)
        {
          this.Reverse();
        }
      }
      else
      {
        this.Sort(CompareKey);
      }
      //this.Sort(CompareKey);
      _IsSorted = true;
    }

public void Sort(KeyValuePair<TKey, TValue>[] sList)
{
  InPlaceSort(sList, 0, 0, sList.Length);
}

void InPlaceSort(KeyValuePair<TKey, TValue>[] input, int depth, int st, int ed)
{
   //this is all the same as StringSort except that input[indx].Key.ToString() is the sort key
}

有关 KeyedList 的更多信息，请参阅我的代码示例：派生 KeyedList<TKey, Tvalue> 泛型类

秒表测试 

我通过从中派生一个名为 TimeCounter 的新类来改进了 .NET 中的秒表类。 总的 Ticks 被转换为毫秒并四舍五入到最接近的 10 毫秒。 这给出了更一致的结果。 秒表的实际分辨率不超过 10 毫秒，所以我不想显示一堆不添加任何实际信息的额外数字。 我在这些测试中感兴趣的实际上是不同排序测试之间的相对差异。

Sort test with 397540 elements		
                                          Milliseconds	  Relative Differences
#Array.Sort<string>(string[], CompareFun)  980            1.0000
#List<string>.Sort(CompareFun)	           860	          0.8776
*StringSort.Sort(List<string>)	           550	          0.5612
sfList.Sort()	                           540	          0.5510
StringSort.Sort(string[])	           530	          0.5408
Sedgewick.Sort(string[])	           450	          0.4592

# Without CompareFun with Ordinal option this method is slower by about 3x		
* Returns a new copy of List<string>		


 

因此，从这些经过的毫秒测试中，您可以看到 Array.Sort() 和 List.Sort()（原始 Microsoft 排序方法）都比 StringSort 慢大约 45%。 通过我改进的计时方法，我发现 Sedgewick 比 StringSort 稍快（比标准 Array.Sort 快 50% 以上）。 使用 Microsoft 快速排序实现对字符串进行排序似乎有很大的开销。 在派生类中替换 List.Sort() 或使用 StringSort.Sort(List<string>) 重载会产生明显更快的解决方案。

我还对 64 位 Windows 7 系统进行了测试，以查看相对差异结果是否不同。 这些测试结果在下载的 SortTest.xsl 中。

历史

首次发布于 2012 年 7 月 4 日

添加了 Windows 7 64 位系统的秒表测试结果 - 2012 年 7 月 7 日

改进了秒表计时方法并添加了相对差异计算。 在派生的 KeyedList 类中实现了一个 StringSort 版本 - 2012 年 7 月 17 日