0

我正在尝试对一个太大而无法放入内存的文件进行排序。选项 -m 下的 gnu sort 说明：merge already sorted files; do not sort. 我正在努力理解这一点的含义，以确保排序完成我想要的。这篇文章（在 Pandas 中对大型数据集进行排序) 建议结合使用 gnu split 和 gnu sort 来完成这样的任务，方法是首先将文件分成适合内存的较小部分，分别对它们进行排序，然后重新组合。到目前为止，我的实验似乎表明这个程序确实有效。尽管如此，我对手册中合并选项的描述感到困扰，该描述说它没有排序。出于我的目的，有必要对大文件进行完全排序，而不仅仅是本地排序的较小部分的串联。虽然我已经在小例子上测试过这个过程并且它似乎有效，但是手册让我对将它应用到我的实际情况缺乏信心，

要给出 MWE，请考虑我要排序的这个制表符分隔文件：

3   4
2   5
3   1
1   3

我尝试了以下操作：

SortDir="/Users/aireties/Desktop/Sort_Experiments"
## sort document as a whole (in practice, this would be infeasible due to document size)
sort --field-separator=$'\t' -k 1,1 -k 2,2 "$SortDir/To_Be_Sorted.txt" -o "$SortDir/Sorted_as_Whole.txt"  ## sort first by the first column values, then by the second

1   3
2   5
3   1
3   4

这是一次对整个文件进行排序时的“正确”解决方案（这在我的实际用例中是不可行的）。

如果我尝试将文件分成几部分，然后立即使用 -m 选项，则会得到不正确的结果：

## Break file into pieces
MaxLines=2
mkdir "$SortDir/Pieces/"
split -l $MaxLines "$SortDir/To_Be_Sorted.txt" "$SortDir/Pieces/"
## Try merge sort on pieces without first sorting them
sort -m --field-separator=$'\t' -k 1,1 -k 2,2 "$SortDir/Pieces/"* -o "$SortDir/Sorted_in_Pieces1.txt"

3   1
1   3
3   4
2   5

看起来已经发生的是，gnu sort 刚刚考虑了两个单独的部分，并根据彼此的第一个值对它们进行了排序。因此，它在这个成品中将第二块放在了第一位，但没有进行其他排序。

或者，如果我遵循此处提倡的程序（在 pandas 中对大型数据集进行排序），即首先对各个部分进行排序然后合并，我似乎确实得到了正确的结果：

for file in "$SortDir/Pieces/"*  ## sorts all text files in pwd
do
  sort --field-separator=$'\t' -k 1,1 -k 2,2 "$file" -o "$file"
done    

sort -m --field-separator=$'\t' -k 1,1 -k 2,2 "$SortDir/Pieces/"* -o "$SortDir/Sorted_in_Pieces2.txt"    

1   3
2   5
3   1
3   4


cmp --silent "$SortDir/Sorted_in_Pieces1.txt" "$SortDir/Sorted_as_Whole.txt" || echo "files are different"
# file are different
cmp --silent "$SortDir/Sorted_in_Pieces2.txt" "$SortDir/Sorted_as_Whole.txt" || echo "files are different"

对我来说，症结在于，如果片段文件很大，仍然需要进行大量计算才能将它们合并到一个正确排序的文件中。因此，我很难理解如何将如此重要的排序数量描述为声称它“不排序”的操作的结果。

谁能告诉我为什么手册会这样写？为什么以及如何确信 gnu sort 在使用 merge 选项时会可靠地执行它所声称的操作？手册文本是否以某种方式暗示了此过程无法达到预期结果的某些情况？

4

4 回答 4

1

-m就像mergemergesort 的操作一样，简单地将文件合并在一起。它要求两个文件按照相同的顺序排序。

因此，对于一个非常大的文件进行排序，您所做的确实有效：将其拆分为几个较小的文件，在本地对它们进行排序。在这一点上，如果你只是将每个文件附加到另一个文件，你最终会得到类似的东西0 1 2 3 ... 0 1 2 3

该-m选项确实将它们正确合并。

例如，对于那些：

a  b
1  3
2  2
3  1

sort -m a b
# 1 2 3 3 2 1
sort -m a a
# 1 1 2 2 3 3
sort -m b b
# 3 2 1 3 2 1
sort -r -m b a
# 3 2 1 1 2 3
于 2016-05-26T21:25:16.400 回答
1

我怀疑概念问题是关于“合并”的含义。在排序算法的上下文中，“合并”具有特定的含义。有关讨论，请参见https://en.wikipedia.org/wiki/Merge_algorithm。一个关键点是，虽然合并操作确实需要多个文件作为输入，但任何单个输入文件中的项目都必须按正确的排序顺序进行合并才能完成它应该做的事情——这与排序不同手术。从这个意义上说，“合并不排序”。

还有一种称为“合并排序”的排序算法，它使用合并操作作为其组件之一。

于 2020-03-05T04:19:07.653 回答
1

Gnu sort（至少是我查看源代码的版本），将对内存中的文件块进行排序并创建一组临时文件（每个块一个临时文件）。它还在内存排序阶段使用多线程（命令行参数可以设置要使用的最大线程数）。创建所有临时文件后，它会对临时文件进行 16 次合并（除非您覆盖它），直到生成单个排序文件。

这里的要点是您不必先将文件拆分为单独的文件，因为 gnu sort 会自动处理一个大文件，根据需要创建排序的临时文件以合并到单个排序文件中。

-m 选项用于合并多个已排序文件的特殊情况。

于 2016-05-26T23:35:37.273 回答
0

只是为了澄清一下，因为对我来说并不是很明显：如果我们想要一个完全排序的结果-m / --merge，您提供的用于排序的不同文件必须预先排序。sort如果我们提供标志，则不排序-m（inman sort表示-m 不排序，而是合并）。如果我们提供未排序的文件，sort只是会尝试将它们合并，依次读取文件以查找提供的文件的最小数量和每个文件的当前行。

示例（具有垂直值的文件）：

一个 b C d e
1 2 1 8 3
3 4 5 3 2
5 6 9 5 1

文件a、b、c排序；d 和 e 未排序。所以：

sort -m a b: 1 2 3 4 5 6 
sort -m b c: 1 2 4 5 6 9
sort -m b d: 2 4 6 8 3 5
sort -m c d: 1 5 8 3 5 9
sort -m a e: 1 3 3 2 1 5

文件 c 和 d 的情况：

sort -m logic:

  c d
  ---
->1 8<-
  5 3
  9 5

min(1, 8)? -> 1 and point to the next row in the file c
Result: 1

  c d
  ---
  1 8<-
->5 3
  9 5

min(5, 8)? -> 5 and point to the next row in the file c
Result: 1 5

  c d
  ---
  1 8<-
  5 3
->9 5

min(9, 8)? -> 8 and point to the next row in the file d
Result: 1 5 8

  c d
  ---
  1 8
  5 3<-
->9 5

min(9, 3)? -> 3 and point to the next row in the file d
Result: 1 5 8 3

  c d
  ---
  1 8
  5 3
->9 5<-

min(9, 5)? -> 5 and point to the next row in the file d
Result: 1 5 8 3 5

  c d
  ---
  1 8
  5 3
->9 5

min(9, inf)? -> 9 and point to the next row in the file c
Result: 1 5 8 3 5 9

  c d
  ---
  1 8
  5 3
  9 5

min(inf, inf)? -> we have finished
Result: 1 5 8 3 5 9

注意：cat a b | sort -m将不起作用，因为sort确实需要其他人解释的文件描述符。

于 2022-01-19T11:53:40.840 回答