UNIX排序命令如何排序一个非常大的文件？

Question

UNIX sort命令可以像这样对一个非常大的文件进行排序:

sort large_file

排序算法是如何实现的？

为什么它不会导致过多的内存消耗？

Answer 1

UNIX Sort命令的算法细节说Unix Sort使用外部R-Way合并排序算法.链接进入更多细节,但实质上它将输入分成较小的部分(适合内存),然后在结尾处将每个部分合并在一起.

Answer 2

该sort命令将工作数据存储在临时磁盘文件中(通常在/tmp).

Answer 3

警告:此脚本为每个块启动一个shell,对于非常大的文件,这可能是数百个.

这是我为此目的编写的脚本.在4处理器的机器上,它将分拣性能提高了100%!

#! /bin/ksh

MAX_LINES_PER_CHUNK=1000000
ORIGINAL_FILE=$1
SORTED_FILE=$2
CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split.
SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted

usage ()
{
     echo Parallel sort
     echo usage: psort file1 file2
     echo Sorts text file file1 and stores the output in file2
     echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines
     echo  and each chunk will be sorted in parallel
}

# test if we have two arguments on the command line
if [ $# != 2 ]
then
    usage
    exit
fi

#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES > /dev/null
rm -f $CHUNK_FILE_PREFIX* > /dev/null
rm -f $SORTED_FILE

#Splitting $ORIGINAL_FILE into chunks ...
split -l $MAX_LINES_PER_CHUNK $ORIGINAL_FILE $CHUNK_FILE_PREFIX

for file in $CHUNK_FILE_PREFIX*
do
    sort $file > $file.sorted &
done
wait

#Merging chunks to $SORTED_FILE ...
sort -m $SORTED_CHUNK_FILES > $SORTED_FILE

#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES > /dev/null
rm -f $CHUNK_FILE_PREFIX* > /dev/null

另请参阅:" 使用shell脚本更快地对大文件进行排序 "

Answer 4

我不熟悉该程序,但我想这是通过外部排序完成的(大部分问题都保存在临时文件中,而问题的相对较小部分一次保存在内存中).参见唐纳德克努特的"计算机编程艺术",第一卷.3排序和搜索,第5.4节,对该主题进行了非常深入的讨论.

Answer 5

#!/bin/bash

usage ()
{
    echo Parallel sort
    echo usage: psort file1 file2
    echo Sorts text file file1 and stores the output in file2
}

# test if we have two arguments on the command line
if [ $# != 2 ]
then
    usage
    exit
fi

pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {} ';' rm {} > $2

Answer 6

仔细查看排序选项以加快性能并了解它对您的计算机和问题的影响.Ubuntu的关键参数是

• 临时文件的位置-T directory_name
• 要使用的内存量-SN%(所有内存使用的N%,越多越好但避免过度订阅导致交换到磁盘.您可以像"-80%"一样使用它来使用80%的可用内存,或"-S 2G"用于2 GB RAM.)

提问者问"为什么没有高内存使用率？" 答案来自历史,旧的unix机器很小,默认的内存大小设置得很小.为您的工作负载调整尽可能大的数量,以大大提高排序性能.将工作目录设置为最快设备上的某个位置,该位置具有足够的空间来容纳至少1.25*正在排序的文件的大小.