Как я могу улучшить производительность Perl с помощью массивных данных?

Question

Я ищу для улучшения моего алгоритма для загадки массива данных.Если кто-нибудь может придумать хорошую идею, которая заставит его работать быстрее, я буду признателен.

У меня есть 8 файлов, содержащих 2 параметра:

1) начальная точка

2) конечная точка

Эти типы данных повторяются с разными номерами в файле.означает, что у меня может быть файл с 200 начальными точками + 200 конечными точками или файл с 50000 начальными точками + 50000 конечными точками.

ОК, эти случайные данные отражают точки данных оси X.каждая точка начала / конца будет отсортирована в X_sort_array.

Проблема начинается с точек данных оси Y.

Чтобы создать точки данных оси Y, я разработал некоторый алгоритм, которыйпробегать все точки X_sort_array и проверять каждую точку, находится ли она между всеми индивидуальностями начальных и конечных точек.если это добавить один для Y_array [x_point] и так далее ...

Я вставлю здесь большую часть своего кода, если есть синтаксис / способ сделать его более эффективным, я буду радзнать.

когда sort_all_legth больше, чем 50000 - началось медленное движение:

    my $sort_all_length = @{$values{"$tasks_name[$i]\_sort\_allvals"}};
    my $core_count = 0;
    my $m=0;

    for my $k(0 .. $sort_all_length-1){



    if (($values{"$tasks_name[$i]\_sort\_allvals"}->[$k] eq $values{"$tasks_name[$i]\_sort\_allvals"}->[$k-1])
& ($k != 0) ) {
}

    else {
    my $pre_point_flag;
    # CHEACK PREVIUES POINT:
    for my $inst_num(0 .. $sort_all_length/2-1){
     $pre_point_flag=1;
     if ( ($values{"TID$i\_$tasks_name[$i]\_SHL"}->[$inst_num] <=    $values{"$tasks_name[$i]\_sort\_allvals"}->[$k]-1) 
   & ($values{"$tasks_name[$i]\_sort\_allvals"}->[$k]-1 <= $values{"TID$i\_$tasks_name[$i]\_EHL"}->[$inst_num]) )  {
    $pre_point_flag=0;
    last;
 }
}
if ($pre_point_flag eq 1){
 push(@{$values{"$tasks_name[$i]\_Y"}},0);
 push(@{$values{"$tasks_name[$i]\_X"}},$values{"$tasks_name[$i]\_sort\_allvals"}->[$k]-1);
}

# CHEACK DEFINE POINT:
for my $inst_num(0 .. $sort_all_length/2-1){
 if ( ($values{"TID$i\_$tasks_name[$i]\_SHL"}->[$inst_num] <= $values{"$tasks_name[$i]\_sort\_allvals"}->[$k]) 
   & ($values{"$tasks_name[$i]\_sort\_allvals"}->[$k] <= $values{"TID$i\_$tasks_name[$i]\_EHL"}->[$inst_num]) )  {
    $core_count++;
 }

}
push(@{$values{"$tasks_name[$i]\_Y"}},$core_count);
push(@{$values{"$tasks_name[$i]\_X"}},$values{"$tasks_name[$i]\_sort\_allvals"}->[$k]);

# CHEACK LATER POINT:
for my $inst_num(0 .. $sort_all_length/2-1){
 $pre_point_flag=1;
 if ( ($values{"TID$i\_$tasks_name[$i]\_SHL"}->[$inst_num] <= $values{"$tasks_name[$i]\_sort\_allvals"}->[$k]+1) 
   & ($values{"$tasks_name[$i]\_sort\_allvals"}->[$k]+1 <= $values{"TID$i\_$tasks_name[$i]\_EHL"}->[$inst_num]) )  {
    $pre_point_flag=0;
    last;
 }
}
if ($pre_point_flag eq 1){
 push(@{$values{"$tasks_name[$i]\_Y"}},0);
 push(@{$values{"$tasks_name[$i]\_X"}},$values{"$tasks_name[$i]\_sort\_allvals"}->[$k]+1);
}

if ($y_max_val < $core_count){
 $y_max_val = $core_count;
}

$core_count = 0;
$m++;
}



}

небольшой пример данных с хорошей производительностью:

(плохая производительность связана с IPразмер 50000!)

база данных: задача: byte_position

база данных: размер двоичного файла: 3216

база данных: число начальных / конечных значений = 804

база данных: подсчет активных ядер в отсортированном массиве IP (размер: 1608) ...

база данных: значение массива IP:

375127997,375135023,375177121,375177978,375225484,375226331, 375273745,375274563,375320063,375325255,375372479,375377085, 375422115,375422896,375473198,375474058,375517412,375518169, 375561967,375562760,375606301,375607092 ...

* *1038* 1040 *

входами являются начальная и конечная точки на оси X:

16,255

16,255

16,255

100,355

200,455

база данных: задача: TEST

база данных: размер двоичного файла: 20

база данных: количество начальных / конечных значений = 5

база данных: отсортированный массив IP (ось X):

16,16,16,100,200,255,255,255,355,455

каждая из этих точек называется интересной точкой (по оси X).

для вычисления значений Y я рисую вертикальную линию с каждым IP

затем я подсчитываю, сколько входных линий (начальная / конечная точка) проходит через первую вертикальную линию.

результат - первая точка Y для первой базы данных X IP

: подсчет активных ядер в отсортированном массиве IP (размер: 10) ...

выходной вектор:

база данных: массив отсортированных ядер (ось Y):

0,3,4,5,5,2,1,0

В моем алгоритме я добавил еще одну точку до и после каждого IP, который начинает / заканчивает блок.

так вы можете видеть ноль аt начало / конец!

3 - означает, что в точке X есть 3 линии среза 16

4 - означает, что в точке X есть 4 линии среза 100

5 -(1) означает, что в точке X имеется 5 линий среза 200

5 - (2) означает, что в точке X имеется 5 линий среза 255

2 - означает, что в точке X имеется 2 линии срезаточка 355

1 - означает, что в точке X есть 1 линия среза 455

Надеюсь, что этот расширенный пример поможет вам лучше понять алгоритм.:)

Я восстановлю код для удобства чтения.

Спасибо, Yodar.

Answer 1

У меня небольшие проблемы с отслеживанием этого, но звучит так, будто вы ищете (удобно предварительно отсортированный) массив точек-файлов-данных из начала for my $var (0..whatever) { ... last if $done; } несколько раз для каждой точки оси-Х.

Итого Алгоритм Шлемиэля Художника . Это, вероятно, источник проблемы с производительностью. Вам следует избегать тех частей поиска, которые вам больше не нужны.

Answer 2

Очень простой способ улучшить свою производительность - это просто изучить лучшие практики кодирования.

Один принцип, который вы игнорируете, таков: не повторяйте себя.

Вы часто повторяете определенные фрагменты кода, заставляя Perl снова и снова вычислять одно и то же выражение. Примером этого является эта строка:

"$tasks_name[$i]\_sort\_allvals"

Он используется там примерно 10 раз. Это означает, что каждый раз, когда вы используете его, perl ссылается на массив, в случае его изменения, и собирает эту строку. Это может показаться не очень много, но в итоге это складывается.

Другой пример:

$values{"$tasks_name[$i]\_sort\_allvals"}->[$k]

Он также используется 10 раз, и хотя $ k фактически меняет каждый цикл, для каждого прохода цикла значение этого целого выражения одинаково. Было бы быстрее сохранить его в одном скаляре в начале цикла, а затем использовать этот скаляр во всем остальном, так как вы не будете вынуждать perl разрешать ссылку 10 раз за цикл.

Answer 3

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

#!/usr/bin/env perl

use strict;
use warnings;

my (@starts, @ends);

while(<>) {
    chomp;
    my($start, $end) = split',';
    push @starts, $start;
    push @ends, $end;
}

@starts = sort { $a <=> $b } @starts;
@ends = sort { $a <=> $b } @ends;

my $y = 0;
my ($x, @y, @x);
while (@starts) {
    my $x = $starts[0] <= $ends[0] ? $starts[0] : $ends[0];
    while ($starts[0] == $x) {
        $y++;
        shift @starts;
        last unless @starts;
    }
    push @x, $x;
    push @y, $y;
    while ($ends[0] == $x) {
        $y--;
        shift @ends;
        last unless @ends;
    }
}

while (@ends) {
    my $x = $ends[0];
    push @x, $x;
    push @y, $y;
    while ($ends[0] == $x) {
        $y--;
        shift @ends;
        last unless @ends;
    }
}

die "Unbalanced!" if $y;

$" = ',';
print "0,@y,0\n";

Answer 4

Я пытался понять вашу программу, но мой мозг немного задохнулся. Можете ли вы предоставить нам пример ввода, некоторые объяснения того, что вы хотите сделать, и хороший пример вывода? Из твоего примера я не могу сделать голову или хвост.

Вы говорите, что это верный ввод:

database: task: TEST

database: binary file size: 20

database: numbers of start/end values = 5

database: sorted I.P array (X axis):

16,16,16,100,200,255,255,255,355,455

database: counting active cores in sorted I.P array (size: 10)...

и это действительный вывод:

database: sorted cores array (Y axis):

0,3,4,5,5,2,1,0

но я не понимаю этого. Не хочешь объяснить, чего ты хочешь достичь?

Answer 5

Может быть, лучший способ - загрузить данные в BD, создать индексы на их полях и запустить SQL как ВЫБЕРИТЕ начало, остановка ОТ X ГДЕ Y между началом, остановкой;

BD имеет хорошие алгоритмы бинарного поиска. Наверное, лучше, чем ваш.

Другой подход - преобразовать ваши данные из строки в двоичный и может использовать статический массив C для управления им. как

struct point {
   int start, int stop      
}  

point array[8000];
read array form file;
for (int i=0; i<8000; i++)
{
}

Вы будете удивляться, насколько быстро

Answer 6

Исходя из того, что вы говорите здесь:

Чтобы создать точки данных оси Y, я разработал некоторый алгоритм, который работает по всем точкам X_sort_array, и проверяю для каждой точки, находится ли она между всеми индивидуальностями начальных и конечных точек. если это добавить один для Y_array [x_point] и так далее ...

и, предположив, что это ваша проблема, тогда модифицированный алгоритм двоичного поиска будет работать в O (log n), или приблизительно 6 шагов для n = 1_000_000:

sub binary_range_search {
    my ( $range, $ranges ) = @_;
    my ( $low, $high ) = ( 0, @{$ranges} - 1 );
    while ( $low <= $high ) {

        my $try = int( ( $low + $high ) / 2 );

        $low  = $try + 1, next if $ranges->[$try][1] < $range->[0];
        $high = $try - 1, next if $ranges->[$try][0] > $range->[1];

        return $ranges->[$try];
    }
    return;
}

В этой версии вы ищете, перекрывает ли диапазон @$range какой-либо из диапазонов в @$ranges. Вы можете изменить его, чтобы искать перекрытия одной точки во всех диапазонах. Это то, что вы ищете?