Создать отсортированный список из n отсортированных подсписков (эффективно)

Question

Я сегодня играл с параллельной сортировкой.

creating sort file
naive-sort ...
1000000
23.61265496
partial-hyper-sort ...
4
7.4924575
simple-hyper-sort ...
1000000
141.7945921
naive-hyper-sort ...
1000000
23.5756172

Две вещи выделяются.

a) naive-hyper-sort так же быстро, как обычно sort b) Сортировка в partial-hyper-sort на 66% быстрее, чем в обычном sort.

Моя проблема: partial-hyper-sort именно такова: «частичная». Он возвращает (в моей системе) 4 подсписка, но вы хотите, конечно, один. Моя попытка объединить их в одну (simple-hyper-sort) на порядок медленнее, чем вся сортировка!

Так как мне получить это быстрее? И если кто-то может объяснить, почему naive-hyper-sort не быстрее, чем naive-sort, бонусные очки и печенье (серьезно, буквальное печенье).

create-sortfile
    unless "tosort.txt".IO.e;

my $start = DateTime.now;
say "naive-sort ...";
say naive-sort.elems;
say DateTime.now - $start;

$start = DateTime.now;
say "partial-hyper-sort ...";
say partial-hyper-sort.elems;
say DateTime.now - $start;

$start = DateTime.now;
say "simple-hyper-sort ...";
say simple-hyper-sort.elems;
say DateTime.now - $start;


$start = DateTime.now;
say "naive-hyper-sort ...";
say naive-hyper-sort.elems;
say DateTime.now - $start;

sub create-sortfile
{
    say "creating sort file";
    my $to-sort = "tosort.txt".IO.open(:w);
    $to-sort.say( ( 10_000 .. 99_999 ).pick )
        for ( 1 .. 1_000_000  );

    $to-sort.close;
}

sub simple-hyper-sort
{
    my $to-sort = "tosort.txt".IO.open( :r );
    my $lines   = $to-sort.lines;
    my $degrees = $*KERNEL.cpu-cores;
    my $batch   = $lines.elems div $degrees;
    my @parts   = $lines.batch( $batch ).hyper( :batch(1) ).map({ .sort });
    my @index   = 0 xx $degrees;

    return gather loop
    {
        my $smallest        = Inf;
        my $smallest-index  = -1;
        my $smallest-degree = -1;

        for ^$degrees -> $degree
        {
            my $index = @index[$degree];

            if ( $index < $batch )
            {
                my $value = @parts[$degree;$index];

                if $value < $smallest
                {
                    $smallest = $value;
                    $smallest-index = $index;
                    $smallest-degree = $degree;
                }
            }
        }

        last if $smallest-index < 0;
        @index[$smallest-degree]++;
        take $smallest;
    }
}


sub partial-hyper-sort
{
    my $to-sort = "tosort.txt".IO.open( :r );
    my $lines   = $to-sort.lines;
    my $degrees = $*KERNEL.cpu-cores;
    my $batch   = $lines.elems div $degrees;
    my @parts   = $lines.batch( $batch ).hyper( :batch(1) ).map({ .sort });
}

multi sub naive-hyper-sort
{
    my $to-sort = "tosort.txt".IO.open( :r );
    my $lines   = $to-sort.lines;
    my $degrees = $*KERNEL.cpu-cores;
    my $batch   = $lines.elems div $degrees;
    $lines.hyper( :$batch, :$degrees ).sort;
}

sub naive-sort {
    my $to-sort = "tosort.txt".IO.open( :r );
    $to-sort.lines.sort;
}

Answer 1

Использование .hyper и .race приводит к ускорению только при параллельной реализации следующей операции. На момент написания в Rakudo не было параллельной sort реализации, а это означает, что она вернется к использованию реализации обычной сортировки. Таким образом, это объясняет, почему native-hyper-sort не выходит быстрее в настоящее время (однако это почти наверняка произойдет в будущем).

Идея в simple-hyper-sort заключается в правильном направлении: разбить данные наподсписки, сортировать подсписки, а затем объединить их. Поэтому мы можем распараллелить сортировку подсписков. Как вы уже заметили, это достижение выигрыша зависит от того, что сама операция слияния является достаточно быстрой, и поэтому нам необходимо тщательно оптимизировать ее.

Намного проще написать сжатый текст (не говоря уже о правильном). !) операция слияния, если требуется объединить только два подсписка. Таким образом, нам нужно структурировать проблему таким образом, чтобы это нам давалось. Это указывает на другой подход:

1. Разбить список пополам
2. start задача сортировать каждую половину
3. await две задачи
4. Слияние результатов двух задач

Обратите внимание, что шаг 2 включает в себя рекурсию. Мы прекращаем повторение, когда размер раздела слишком мал, и используем встроенные sort на таких разделах. (Мы можем определить «слишком маленький», разделив размер входного списка на количество ядер ЦП, как показано в вашем примере.)

Таким образом, мы получаем решение, подобное этому:

sub parallel-merge-sort {
    my $to-sort = "tosort.txt".IO.open( :r );
    my $lines = $to-sort.lines;
    return do-sort $lines, ceiling($lines.elems / $*KERNEL.cpu-cores);

    sub do-sort(@in, $limit) {
        if @in.elems < $limit {
            @in.sort
        }
        else {
            my $pivot = @in.elems div 2;
            merge |await
                (start do-sort @in[0..$pivot], $limit),
                (start do-sort @in[$pivot^..@in.end], $limit)
        }
    }

    sub merge(@a, @b) {
        my @result;
        my int $a-idx = 0;
        my int $a-elems = +@a;
        my int $b-idx = 0;
        my int $b-elems = +@b;
        my int $r-idx = 0;
        while $a-idx < $a-elems && $b-idx < $b-elems {
            my $a := @a[$a-idx];
            my $b := @b[$b-idx];
            if $a before $b {
                $a-idx++;
                @result[$r-idx++] := $a;
            }
            else {
                $b-idx++;
                @result[$r-idx++] := $b;
            }
        }
        if $a-idx < $a-elems {
            @result[$r-idx++] := $_ for @a[$a-idx..*];
        }
        elsif $b-idx < $b-elems {
            @result[$r-idx++] := $_ for @b[$b-idx..*];
        }
        return @result;
    }
}

Я не потратил ужасно много времени на оптимизацию этого (не профилировал и т. Д.), Но позаботился об использовании нативов и привязок, чтобы уменьшить распределение. На Моей Машине, однако, это дает ускорение по сравнению с последовательной сортировкой.

Еще одно простое ускорение, которое мы можем получить - за счет чуть большей сложности в коде, - это от осознания того, что мы надеваемне нужно нарезать входные данные в do-sort до того момента, когда мы действительно должны отправить его во встроенный sort:

sub do-sort(@in, $limit, $from = 0, $to = @in.end) {
    my $elems = $to - $from;
    if $elems < $limit {
        @in[$from..$to].sort
    }
    else {
        my $pivot = $from + $elems div 2;
        merge |await
            (start do-sort @in, $limit, $from, $pivot),
            (start do-sort @in, $limit, $pivot + 1, $to)
    }
}

, что экономит некоторую работу;к этому моменту я измеряю коэффициент двухкратного ускорения на машине, на которой тестирую, что не удивительно, но, учитывая, что у нас есть принудительный последовательный шаг O (n), и куча более распараллеленных O (n)пошагово, по алгоритму последовательной сортировки, возможно, это не так разочаровывает.