как команда сортировки unix может отсортировать очень большой файл?

<p>команда unix <code>sort</code> может отсортировать очень большой файл следующим образом:</p><pre><code>sort large\_file </code></pre><p>как реализован алгоритм сортировки?</p><p>почему это не вызывает чрезмерного потребления памяти?</p>

<p> <a href="http://vkundeti.blogspot.com/2008/03/tech-algorithmic-details-of-unix-sort.html">алгоритмические подробности команды сортировки unix</a> говорит, что сортировка unix использует алгоритм сортировки слиянием по внешнему r-образному пути. ссылка углубляется в детали, но по сути она делит входные данные на более мелкие части (которые помещаются в память), а затем объединяет каждую часть вместе в конце.</p>

<p>команда <code>sort</code> сохраняет рабочие данные во временных дисковых файлах (обычно в <code>/tmp</code>).</p>

<p><strong> предупреждение: </strong> этот скрипт запускает одну оболочку на чанк, для действительно больших файлов это может быть сотни.</p><hr><p>вот сценарий, который я написал для этой цели. на 4-х процессорной машине это улучшило производительность сортировки на 100%!</p><pre><code>#! /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 смотрите также: " <a href="http://bashcurescancer.com/sorting-large-files-faster-with-a-shell-script.html">сортировка больших файлов быстрее с помощью скрипта shell "

я не знаком с программой, но думаю, что это делается с помощью внешней сортировки (большая часть проблемы хранится во временных файлах, тогда как относительно небольшая часть проблемы хранится в памяти одновременно). смотрите donald knuth's <a href="http://www-cs-faculty.stanford.edu/~uno/taocp.html">искусство компьютерного программирования, том 3, сортировка и поиск, раздел 5.4 для очень глубокого обсуждения предмета.

<pre class="lang-bsh prettyprint-override">#!/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 </code></pre>

<p>внимательно изучите параметры сортировки для ускорения производительности и поймите, как это влияет на вашу машину и проблемы. основные параметры в ubuntu:</p><ul> <li>расположение временных файлов -t directory\_name</li> <li>объем используемой памяти -sn% (n% всей используемой памяти, чем больше, тем лучше, но избегайте чрезмерной подписки, которая приводит к подкачке на диск. вы можете использовать ее как "-s 80%", чтобы использовать 80% доступной оперативной памяти, или "-s 2g" для 2 гб озу.)</li> </ul><p>спрашивающий спрашивает: "почему нет высокого использования памяти?" ответ на этот вопрос приходит из истории, старые машины с unix были маленькими, а размер памяти по умолчанию был небольшим. отрегулируйте это как можно больше для своей рабочей нагрузки, чтобы значительно повысить производительность сортировки. установите рабочий каталог на место на вашем самом быстром устройстве, на котором достаточно места для хранения не менее 1,25 * размера сортируемого файла.</p>