Оптимальная сортировка набора данных из N ключей, когда первый ключ уже заказан

Question

Я часто сталкиваюсь с ситуацией, когда частично упорядоченные данные должны быть отсортированы. Первый столбец уже отсортирован, позже нет. Как этот пример с двумя столбцами:

1 5
1 3
2 10
2 -1
2 3
3 11
3 -200
3 20

Желаемый результат - это результат

sort -k 1,1g -k 2,2g

который работает, но имеет проблему, что ничего не выйдет из сортировки, пока все входные данные не будут прочитаны. Когда ввод занимает несколько гигабайт текста, это может занять некоторое время, в течение которого ничего не может выполнить ни один нисходящий поток по сравнению с сортировкой в конвейере. Это также не очень эффективно с точки зрения использования памяти, так как весь набор данных должен находиться там одновременно, даже если для достижения желаемой сортировки действительно требуется только небольшая часть.

С помощью сценария было бы нетрудно разбить это на куски, а затем отсортировать каждый кусочек. Есть ли у команды sort где-то опция для уведомления, что данные в этом столбце уже упорядочены? Я не вижу это в виде 8.4, но, возможно, я просто пропустил это?

Если сортировка встречает неупорядоченное значение в столбце, о котором было сказано, что он уже упорядочен, она должна выйти. Это указывает на ошибку в восходящей обработке.

Answer 1

Я не могу сделать это с единственным sort . Это может быть невозможно.

В моем решении awk обрабатывает первый столбец и выполняет sort столько раз, сколько необходимо. Сценарий принимает входные данные от стандартного ввода, печатает на стандартный вывод).

#!/usr/bin/awk -f

BEGIN { command = "sort -k 2,2g" }

{
if ( NR==1 ) {
   val=$1
   buf=$0
}
else
if ( $1 < val ) {
   print "Unsorted 1st column detected. Processing last valid chunk and aborting." > "/dev/stderr"
   exit 1
   }
else {
if ( $1 == val )
   buf=buf"\n"$0
else
   {
   print buf | command
   close(command)
   buf=$0
   val=$1
   }
   }
}

END { print buf | command }

Заметки:

• close(command) имеет решающее значение. Без этого все каналы для command пошли бы в один sort .
• По моему мнению операторы сравнения awk обрабатывают числа достаточно хорошо. Чтобы быть действительно уверен , что решение работает так , как - sort будет работать, вам нужно получить статус выхода своего sort -c -k 1,1g для val"\n"$1 и отдельно за $1"\n"val а затем построить логику сценария на что. Это будет запускать два процесса sort на входную строку, я ожидаю огромного снижения производительности

Answer 2

Камил Цук разместил этот ответ в другой ветке. Сейчас я попытаюсь удалить эту ветку, поскольку, очевидно, наличие этого в двух местах - нет, нет, и я хотел бы сохранить этот ответ здесь.

Следующий скрипт печатает строки с тем же первым столбцом во временный файл и сортирует его.

file=$1
# create temporary file
temp=$(mktemp)
trap 'rm "$temp"' EXIT
i_last=""
while read -r i j; do
    if [ "$i" != "$i_last" ]; then
        # output sorted temporary file
        sort -n $temp
        # and truncate temporary file
        > $temp
        # increment first column pointer
        i_last=$i
    fi
    # print all lines into temporary file
    echo "$i" "$j" >>$temp
done <"$file"
# dont forget leftovers
sort -n "$temp"

Answer 3

Perl на помощь!

Он делает именно то, что вы просили, он направляет куски ввода, начинающиеся с того же номера, для сортировки, которая работает только во втором столбце.

#!/usr/bin/perl
use warnings;
use strict;

my $sort;

my $first = -1;
while (<>) {
    my ($x, $y) = split;
    if ($first != $x) {
        die "Unsorted line $." if $first > $x;
        $first = $x;
        open $sort, '|-', 'sort -k2,2n' or die $!;
    }
    print {$sort} $_;
}

Единственной проблемой может быть начальное значение $first: если ваш ввод начинается с отрицательного числа в 1-м столбце, вам нужно указать меньшее значение.

Я использовал сортировку n вместо g поскольку на моей машине это выглядит немного быстрее.