Perl: Самый эффективный способ вычисления процентиля

Question

У меня есть скрипт perl, который проходит через пару файлов с достоинством и генерирует отчет.

Для того, чтобы вычислить процентиль я делаю следующее

my @values = 0; 
while (my $line = <INPUTFILE>){ 
    ..... 
    push(@values, $line); 

} 
# Sort 
@values = sort {$a <=> $b} @values; 

# Print 95% percentile 
print $values[sprintf("%.0f",(0.95*($#values)))]; 

Это, очевидно, сохраняет все значения авансовых в массиве, а затем вычисляет процентиль, который может быть тяжелым на памяти (предполагая, что миллионы значений), есть ли более эффективный способ памяти сделать это?

Answer 1

Вы можете обрабатывать файл дважды: первый запуск подсчитывает количество строк ($.). Из этого числа вы можете подсчитать размер скользящего окна, которое будет содержать только самые высокие числа, необходимые для поиска процентиля (для процентилей < 50, вы должны инвертировать логику).

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

my $percentile = 95; 

my $file = shift; 
open my $IN, '<', $file or die $!; 

1 while <$IN>;    # Just count the number of lines. 
my $line_count = $.; 
seek $IN, 0, 0;   # Rewind. 

# Calculate the size of the sliding window. 
my $remember_count = 1 + (100 - $percentile) * $line_count/100; 

# Initialize the window with the first lines. 
my @window = sort { $a <=> $b } 
      map scalar <$IN>, 
      1 .. $remember_count; 
chomp @window; 

while (<$IN>) { 
    chomp; 
    next if $_ < $window[0]; 
    shift @window; 
    my $i = 0; 
    $i++ while $i <= $#window and $window[$i] <= $_; 
    splice @window, $i, 0, $_; 
} 
print "$window[0]\n";