задачка 2.
*как выяснилось, решение корректно на числах одного порядка
есть 10 миллиардов записей в файле, каждая запись это число типа double, требуется найти минимальное значение из 10% максимальных.
мое решение таково, создаем хеш ключом которого будет первые n символов числа, а значением, кол. вхождения этого ключа в файле. Сортируем по ключам и отсчитываем в каком ключе будет начало 10%, проходим еще раз массив значений и выбираем те которые соответствуют ключу, сортируем его, и вытаскиваем позицию соответствующую 10%.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | # запуск perl begin.pl FILE DL RESULT # , где # FILE файл который требуется обработать # DL длинна ключа для групп (1..n, для 100кк записей достаточно 5) # RESULT финальный шаг, 1 - включен, 2 - не включен, тогда после отработки begin.pl, нужно запустить result.pl (perl result.pl) - не актуально, скрипт выполняется полностью независимо от этого параметра. # если в программу не переданы параметры, скрипт запрашивает их сам. # Алгоритм: # ШАГ 1. # разбиваем весь массив на группы и заносим их в хеш массив, ключом будет уникальная последовательность первых символов строки длинной DL , значением количество совпадений этого ключа встреченное по проходу файла. # (Чем больше DL тем больше групп, и тем меньше в этих группах значений, сортируются как группы так и ключи, так что важен баланс, чтобы оба шага отрабатывали за оптимальное время.) # ШАГ2. # зная количество строк в файле, получаем длину искомых 10%, сортируем по ключу хеш, и определяем группу в которой будет находится начальное значение наших 10% # ШАГ3. # проходим еще раз файл и отбираем значения подходящие под ключ определенной ранее группы, записываем эту группу в файл, на всякий случай. # ШАГ4. # сортируем файл со значениями группы, зная позицию где должно находится начало 10% извлекаем нужное значение. # Итог. # приходится 2 раза обходить БОЛЬШОЙ файл, на 10^8 значениях вида хх.уууууууууу, где хх от 1 до 15, а у от 0 до 9, время работы скрипта при DL=5 было 3 минуты. # в папке group находится результат шага3 # begin.pl - шаги с 1 по 3. # result - шаг 4. my $file , $dl , $r ; if ( defined ( @ARGV )){ ( $file , $dl , $r )= @ARGV ; print "File: " . $file . "\n" ; if (! defined ( $dl ) || $dl ==0){ $dl =4;} print "Quantity of signs in a group key: " . $dl . "\n" ; if ( defined ( $r ) and $r !=0){ $rs = "yes" ;} else { $rs = "no" ;} print "To start 4 step? " . $rs . "\n\n" ; } else { ( $file , $dl , $r )=prepareToStart(); } sub prepareToStart{ print "Please, input path and filename (ex. /log/file.txt): " ; my $file =<>; $file =~s/\n//g; print "\nEnter length of a key (ex. 5): " ; my $dl =<>; $dl =~s/\n//g; if ( $dl <=0){ $dl =5;} print "The result press? - yes\n" ; my $r =1; return ( $file , $dl , $r ); } if (!-e $file ){ print "file \"$file\" not found, exit" ; exit ;} print "STEP 1\n" ; my ( $d10 , %group )=first( $file , $dl ); print "Quantity of values in 10 % (D10): " . $d10 . "\n" ; print "...ok\n" ; print "STEP 2\n" ; my ( $key , $position , $c )=&second(\ $d10 ,\ %group ); my $cGroup = keys ( %group ); print "Groups: $cGroup, Group: $key, Position: $position Elements: $c\n" ; print "...ok\n" ; print "STEP 3\n" ; my $tempFile =third( $key , $position , $file ); print "...ok\n" ; print "STEP 4\n" ; &analiz( $tempFile ); print "...ok\n" ; sub analiz{ my $file = shift ; if (-e $file ){ if ( $file =~m/^.+_(\d+)$/){ analizGroup( $file , $1 ); } } } sub analizGroup{ my ( $file , $position )= @_ ; open (F, "$file" ) || die ( "$file $!" ); my $fl = "" , @m =(); while ( $fl =<F>){ $fl =~s/\n//g; push ( @m , $fl ); } close F; sortGroup(\ @m ); print "The minimum value from 10 % is " . $m [ $position -1]. "\n" ; unlink ( $file ); } sub sortGroup{ my $ref = shift ; @ $ref = sort { $b <=> $a }(@ $ref ); } sub first{ my ( $file , $dl )= @_ ; open (FL, $file ) || die ( "$file $!" ); my $i =0, $fl , @keys , $d10 ; my %group ; my $regexp = ".{0,$dl}" ; while ( $fl =<FL>){ $i ++; if ( $fl =~m/(^(??{ $regexp }))/){ $group { $1 }++; } } close FL; # количество элементов в 10% $d10 = int ( $i *0.1); #возвращаем размер 10%, и хеш{группа}=кол элементов. return ( $d10 , %group ); } sub second{ my ( $r1 , $r2 )= @_ ; my @st = sort { $b <=> $a }( keys (%{ $r2 })); my $counter =0; foreach my $key ( @st ){ $counter +=${ $r2 }{ $key }; if ( $counter >=${ $r1 }){ my $position =${ $r2 }{ $key }-( $counter -${ $r1 }); #возвращаем ключ нужной группы, искомую позицию и количество элементов в группе. return ( $key , $position ,${ $r2 }{ $key }); } } } sub third{ my ( $key , $position , $file )= @_ ; open (FL, $file ) || die ; open (OUT, "> ${key}_${position}" ) || die ( "${key}_${position} $!" ); my $i , $fl , @keys , $c =0; while ( $fl =<FL>){ if ( $fl =~m/^(??{ $key })/o){ $i ++; $c ++; push ( @keys , $fl ); if ( $i >=100){ print OUT @keys ; undef ( @keys ); $i =0; } } } if ( defined ( @keys ) && $ #keys+1>0){ print OUT @keys ; undef ( @keys ); } close OUT; close FL; return ( "${key}_${position}" ); } |
Комментарии закрыты.