1

我需要对大量任意长度的文本字符串进行排序。我想基数排序是这里最好的选择。列表真的很大，所以将字符串填充到相同的长度是完全不可能的。
这个任务是否有现成的实现，最好是在 C# 中？

4

5 回答 5

2

根据您的需要，您可能会发现将所有字符串插入某种形式的 Trie 是最佳解决方案。即使是基本的三元搜索 Trie 也将比字符串数组/列表具有更小的内存占用，并将按排序顺序存储字符串。

插入、查找和删除都是字母表O(k * log(a))的a大小（一个字符的可能值的数量）。由于a是恒定的，log(a)所以你最终得到了一个O(n * k)排序算法。

编辑：如果您不熟悉 Tries，它们基本上是 n 叉树，其中每条边代表键的单个字符。插入时，您检查根节点是否包含与键的第一个字符匹配的边（或子节点，等等）。如果是这样，您按照该路径并重复第二个字符，依此类推。如果没有，则添加新边缘。在三元搜索树中，边/子节点存储在二叉树中，因此字符按排序顺序排列并且可以及时搜索log(a)。如果你想浪费内存，你可以将边/子元素存储在一个大小数组中，a这样你就可以在每个步骤中不断查找。

于 2010-09-10T15:33:24.753 回答
1

多少是多少，一百万？

内置的List<string>.Sort()平均需要 O(n * log(n))。

log2(10^6) ~=20，对于 10^6 个元素，这并不比 O(n) 慢很多。如果您的字符串长度超过 20 个字符，则基数排序 O(n * k) 将“更慢”。

我怀疑基数排序会比内置排序快得多。但是测量和比较会很有趣。

于 2010-09-10T14:37:34.957 回答
1

看到这个线程。基数排序 或这个基数排序实现

于 2010-09-10T14:25:08.273 回答
1

编辑：我之前所做的这些陈述是有道理的，但总体而言，这一点是错误的。

基数排序是对大量字符串使用的错误排序。对于像这样的事情

I really like squirrels. Yay, yay, yay!
I really like blue jays. Yay, yay, yay!
I really like registers. Yay, yay, yay!

您将有一堆条目落在同一个桶中。你可以通过散列来避免这种情况，但是对散列码进行排序有什么用呢？

使用快速排序或合并排序等。（快速排序通常性能更好，占用的内存更少，但许多示例的最坏情况性能为 O(N^2)，这在实践中几乎从未发生过；合并排序的性能不太好，但通常实现为稳定，而且它是容易做部分在内存和部分在磁盘上。）即使用内置的排序功能。

编辑：好吧，事实证明，至少在非常大的文件中，开始时重复很长（例如源代码）并且许多行完全相同（实际上是 100 次重复），基数排序确实开始与快速排序竞争。我很惊讶！但是，无论如何，这是我用来实现基数排序的代码。它是在 Scala 中，而不是 C# 中，但我已经以相当迭代的风格编写了它，所以它应该是相当明显的事情是如何工作的。唯一的两个棘手的位是(a(i)(ch) & 0xFF)从字节数组（字节有符号）中提取一个 0-255 字节，这counts.scanLeft(0)(_ + _)形成计数的累积和，从零开始（然后indices.clone.take(257)接受除最后一个之外的所有参数），并且 Scala 允许多个参数列表（因此我将始终提供的参数与具有递归使用的默认值的参数分开）。这里是：

def radixSort(a: Array[Array[Byte]])(i0: Int = 0, i1: Int = a.length, ch: Int = 0) {
  val counts = new Array[Int](257)
  var i = i0
  while (i < i1) {
    if (a(i).length <= ch) counts(0) += 1
    else { counts((a(i)(ch)&0xFF)+1) += 1 }
    i += 1
  }
  val indices = counts.scanLeft(0)(_ + _)
  val starts = indices.clone.take(257)
  i = i0
  while (i < i1) {
    val bucket = if (a(i).length <= ch) 0 else (a(i)(ch)&0xFF)+1
    if (starts(bucket)+i0 <= i && i < starts(bucket)+i0+counts(bucket)) {
      if (indices(bucket) <= i) indices(bucket) = i+1
      i += 1
    }
    else {
      val temp = a(indices(bucket)+i0)
      a(indices(bucket)+i0) = a(i)
      a(i) = temp
      indices(bucket) += 1
    }
  }
  i = 1
  while (i < counts.length) {
    if (counts(i)>1) {
      radixSort(a)(i0+starts(i),i0+starts(i)+counts(i),ch+1)
    }
    i += 1
  }
}

时间是 7M 行源代码（70k 行的 100 倍重复），基数排序与内置库排序并列，然后获胜。

于 2010-09-10T15:17:54.897 回答
-2

String.Compare() 重载正在使用这种字符串比较。看看你需要的是把它提供给你的排序算法。

更新

这是实现：

[MethodImpl(MethodImplOptions.InternalCall)]
internal static extern int nativeCompareString(int lcid, string string1, int offset1, int length1, string string2, int offset2, int length2, int flags);

用您自己的实现很难击败这个原生的非托管实现。

于 2010-09-10T14:10:10.923 回答