c# - 对具有相同长度的大量字符串进行排序

Question

我有一个非常大的字符串序列。每个字符串的长度为 50。每个字符串仅包含来自英语 ABC 的字符。对该序列进行排序的最佳(最快)方法是什么？

Answer 1

如果我必须编写代码，我可能会根据前几个字符左右将输入分成许多输出文件；目标是使每个输出文件足够小以适合主内存。然后我会按顺序打开每个文件，在内存中对其进行排序，并将其附加到输出中。第一遍是 O(n)，第二遍或多或少是 O(n log n)，并且每个记录必须执行四次磁盘 I/O。使用一些神秘的算法可能会做得更好，但可能不会好很多，而且这很容易理解和编写代码。

如果系统限制您一次可以打开的文件数量，您可能不得不拆分第一遍。如果字符串分布不均，一些中间文件可能会太大。

在伪代码中:

open input file (r)
for i in ['aa', 'ab', 'ac', ..., 'zz']:
    open output file[i] (w)
for record in input file:
    write record to output file[record[0:2]]
close all files
open main output file (w)
for i in ['aa', 'ab', 'ac', ..., 'zz']:
    open input file[i] (r)
    slurp whole file into memory
    close input file
    sort data
    append whole sorted file to main output file

编辑:等等，你是说记录只包含字符 A、B 和 C？没有其他字母？在这种情况下，您可能必须根据长度超过 2 的初始子字符串进行拆分。根据前 3 个字符进行拆分会将其分成 27 个文件，每个文件的平均大小为 370 MB。