Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > разделение

Автор: gcc 22.1.2009, 12:55

есть файл Код qq1\tuu1\x0Aqq2\tuu2\x0Aqq3\tuu3\x0A как мне сделать хєши? Код open F, "parse.txt" or die "can open: $!\n"; @data=<F>; close F; for $loopindex (O..$#data) {   for $element(split '$\x0A', $data[$loopindex]){     ($key, $value) = split '\t', $element;     $array[$loopindex]{$key} = $value;   }   } use Data::Dumper;      print Dumper(@array); вывод Код $VAR1 = {           'qq1\\tuu1\\x0Aqq2\\tuu2\\x0Aqq3\\tuu3\\x0A' => undef         };

Автор: gcc 22.1.2009, 13:38

фай подправил сделал не бинарный Код qq1 uu1 qq2 uu2 qq3 uu3 хотя не знаю...может быть файл такой как я написал в первом посте так работает Код   for $element(split '\0xa', $data[$loopindex]){     ($key, $value) = split ' ', $element; можите подсказать еще пожалуйста: при бинарном поиске в таком файле, по ключю найти значение, только такой файл занимает 20Гбт, нужно использовать массив хєшей или через свзяку встроенных функций seek, rindex, index, read, tell?

Автор: amg 22.1.2009, 14:16

gcc, на больших файлах нельзя делать @data=<F>; -- памяти может не хватить, да и медленнее это, чем while (<F>) {push @data, $_} (если все же нужно зачитать файл целиком). Насколько я вижу -- у Вас обычный текстовый файл. Зачем с ним обращаться, как с бинарным? Хэш или массив хэшей из файла размером 20Гбт -- памяти может не хватить (если только ключи не будут часто повторяться). Если нужно многократно искать по ключу найти значение (из одного и того же файла), то лучший выход, наверное, создать хэш, связанный со специальным дисковым файлом (модули для этого есть). Тогда создание хэша потребует много времени (и диска), зато поиск значений по ключам будет сравнительно быстр.

Автор: gcc 22.1.2009, 14:21

amg, сказали нужно сделать "бинарный поиск" можно ли тут сделать? это реализуемо? тут нужен массив или не объязательно?

Автор: KSURi 22.1.2009, 14:44

gcc, может вы про какой-то другой "бинарный поиск" подумали? Вообще это http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA.

Автор: gcc 22.1.2009, 14:49

именно про этот поиск он будет работать? там массив, а тут можно? тогда не массив? и нужно чтобы было не более 10 сек.

Автор: amg 22.1.2009, 14:59

Цитата(gcc @  22.1.2009,  14:21 ) нужно сделать "бинарный поиск" Что означает "бинарный поиск"? Значений по ключам? Если пары ключ-значение разделены символом "\0xa", а ключ и значение -- символом "\t" (как в вашем примере), то с таким файлом можно обращаться как с текстовым.  Код open F, "parse.txt" or die "can open: $!\n"; @data=<F>;  while (<F>) {   push @array, {split /\t/}; } close F;  (Вроде, такой массив хэшей Вы хотели сделать? Если да, то какой в нем толк?)

Автор: gcc 22.1.2009, 15:10

я не знаю что это значит, но данные не в MySQL по ссылке которую написал, Уважаемый KSURi, написано, оно быстрее должно быть? можно ли быстрый поиск сделать по такому файлу или нет?

Автор: amg 22.1.2009, 16:24

Цитата(gcc @  22.1.2009,  15:10 ) можно ли быстрый поиск сделать по такому файлу или нет? Именно по файлу -- нет. Скорость современных жестких дисков -- до 100 Мбт/с, 20Гбт -- 200 с (если не супер-рейд какой-нибудь). Можно пробовать создать БД (тот же MySQL, или tie %hash, 'DB_File'). Создание базы -- долго, зато поиск будет быстр.  Если же поиск нужно вести каждый раз в новом 20Гбт файле, то, IMHO, в 10 с никак не уложиться.

Автор: gcc 22.1.2009, 16:34

но вот мне сказали что такой код работает, только я не знаю какой файл на самом деле с какми разделителями, и что за 1Гбт - 1 сек. выполняется я запускаю у меня ничего нету выводиться, т оесть значения - нету Код #!/usr/bin/perl -w my $read_block_size = 256; sub rec_shift {     my ( $file, $dir ) = @_;     my ( $buf, $ofs );     while (1) {         $ofs = tell($file);         if ( !$dir ) {             read( $file, $buf, $read_block_size );             my $o = index( $buf, "\x0a" );             if ( $o >= 0 ) {                 seek( $file, $ofs + $o + 1, 0 );                 return;             }             elsif ( eof($file) ) {                 return;             }         }         else {             my $r = $ofs > $read_block_size ? $read_block_size : $ofs;             seek( $file, -$r, 1 );             read( $file, $buf, $r );             seek( $file, -$r, 1 );             my $o = rindex( $buf, "\x0a" );             if ( $o >= 0 ) {                 seek( $file, $o + 1, 1 );                 return;             }             elsif ( $r == $ofs ) {                 seek( $file, 0, 0 );                 return;             }         }     } } sub rec_read {     my ($file) = @_;     my $ln = '';     my $buf;     while (1) {         my $ofs = tell($file);         read( $file, $buf, $read_block_size );         my $o = index( $buf, "\x0a" );         if ( $o >= 0 ) {             seek( $file, $ofs + $o + 1, 0 );             $ln .= substr( $buf, 0, $o );             return split( /\t/, $ln );         }         $ln .= $buf;     } } sub filebinsearch {     my ( $file, $fkey, $beg, $end ) = @_;     return undef if $beg == $end;     my $oc = int( ( $beg + $end ) / 2 );    # ( $beg + $end ) >> 1 -- 32bit :-(     seek( $file, $oc, 0 );     rec_shift( $file, 1 );     $oc = tell($file);     my ( $key, $value ) = rec_read($file);     return $value if $key eq $fkey;     if ( $key lt $fkey ) {         filebinsearch( $file, $fkey, tell($file), $end );     }     else {         filebinsearch( $file, $fkey, $beg, $oc );     } } sub findinfile {     my ( $filename, $key ) = @_;     my $value    = undef;     my $filesize = 0;     return undef if !-f $filename;     return undef if !-r $filename;     return undef if !( $filesize = -s $filename );     return undef if !open( $file, '<', $filename );     return filebinsearch( $file, $key, 0, $filesize ); } print findinfile( $ARGV[0], $ARGV[1] ) . "\n";

Автор: ginnie 22.1.2009, 17:00

gcc, 1Гбт - 1 сек. возможно только при чтении из памяти, с диска таких скоростей чтения еще нет в свободном доступе

Автор: gcc 22.1.2009, 17:06

ginnie, на этом форуме обсуждалось что это можно сделать, ссылку не помню - сейчас поищу а в этом скрите что я привел, как его запустить какой формат данный в текстовом файле? а то я понять не омгу, не работает скрипт Добавлено @ 17:07 может быть не 1, а 2 Добавлено через 4 минуты и 6 секунд вот http://forum.vingrad.ru/forum/topic-241552.html

Автор: ginnie 22.1.2009, 17:17

gcc, по указанной ссылке обрабатываемый файл содержит упорядоченные по ключам данные. У Вас также? Там просто читаются не все данные, а лишь часть, поэтому возможно обработать большой файл за небольшое время.

Автор: gcc 22.1.2009, 17:21

да, именно так Код qq1\tuu1\x0Aqq2\tuu2\x0Aqq3\tuu3\x0A Добавлено через 1 минуту и 45 секунд только скорее всего так правильней Код qq1 uu1 qq2 uu2 qq3 uu3 \t - это табулятор \x0A - абзац

Автор: ginnie 22.1.2009, 18:22

gcc, в указанном примере формат обрабатываемого файла такой-же как у Вас. запускается script.pl filename key если не находит ключ, добавьте в функцию filebinsearch() строчку Код print "check key $key$/"; перед Код return $value if $key eq $fkey; и проанализируйте вывод

Автор: KSURi 22.1.2009, 20:49

У меня такое ощущение, что все говорят о разных вещах) Правильно ли я понимаю, что вам надо организовать поиск подстроки в файле? Если да, то вам как раз надо использовать алгоритм двоичного поиска (ака метод деления пополам, дихотомия и т.д.). Он предназначен для поиска в упорядоченных массивах. Понятное дело, что считывать ваш огромный файл в память нельзя. Поэтому придется абстрагироваться от перловых массивов и принять файл за массив. Для этого придется написать ф-ию, которая будет перемещать указатель чтения построчно (учитывая строгий формат файла это не сложно). Ну а потом собственно реализовать алгоритм поиска (http://algolist.manual.ru/search/bin_search.php есть более простое и понятное его объяснение) [а может на CPAN уже есть]. ЗЫ: спасибо человеку, который когда-то меня ткнул носом в эту вещь Добавлено через 1 минуту и 44 секунды упс, надолго я оставил страницу с постингом... уже все до меня написали)

Автор: gcc 23.1.2009, 05:04

заработало короче, не знаю или правильно, но меняем: Код return split( /\t/, $ln ); на: Код return split( / /, $ln ); а может кто-то объяснить что такое $buf и $r?  почему функция filebinsearch запускается внутри самой фукнции? никогда такого не видел и где в данном скрипте ключевые моменты (потому что не понятно на все 100% принцип действия, но некоторые момонты понятные, но остальные нет) если это реально...    еще раз нашел:   Код Для перемещения по файлу можно воспользоваться функциями tell() и seek(). Первая возвращает текущую позицию указателя в файле: $pos=tell(PASSWD); А вторая устанавливает указатель на указаную позицию. Причем позицию можно указать как положительную так и отрицатильную. В качестве третьего необязатель- ного параметра эта функция принемает указатель отсчета. Он может быть равен 0 - от начала файла, 1 - от текущего положения и 2 - от конца файла. Пример:  $pos=tell(PASSWD);  seek(PASSWD, $pos+10, 1); Функция read Синтаксис: read файл, скаляр, длина, смещение? Аргументы: файл — описатель файла            скаляр — имя скалярной переменной            длина, смещение — числовые выражения Результат: числовое значение Функция read пытается считать из заданного файла количество байтов, заданное аргументом длина. Результат чтения заносится в переменную скаляр как строка байтов. Если задан аргумент смещение, то результат заносится в скаляр как в строку, начиная с ее байта с заданным смещением (отрицательное смещение отсчитывается от конца строки). Эта функция возвращает количество фактически считанных байтов, 0 при попытке чтения в конце файла и undef при ошибке чтения. Пример: допустим, что наш файл TEST.DAT начинается с символов abcdef. Тогда сценарий open F, 'test.dat'; read F, $x, 5; print $x; выведет на экран строку abcde. Функция rindex Синтаксис: rindex строка, подстрока, позиция? Аргументы: строка, подстрока — строковые выражения            позиция — числовое выражение Результат: числовое значение Функция rindex ищет в строке заданную подстроку справа налево, начиная с заданной позиции или с конца строки, если позиция опущена. Она возвращает позицию найденной подстроки в исходной строке или -1, если подстрока не найдена. Пример: print rindex('abcabc', 'abc');  # 3 Функция substr Синтаксис: substr строка, смещение, длина?, замена? Аргументы: строка, замена — строковые выражения            смещение, длина — числовые выражения Результат: строковое значение Функция substr возвращает подстроку строки заданной длины, начиная с заданного смещения. Если смещение отрицательно, то оно отсчитывается от конца строки. Если длина опущена, то извлекаются символы до конца строки; если она отрицательна, то она складывается с длиной строки. Пример: print substr('abcdef', 1, -2);  # bcd Если строка задана переменной, то эта функция может иметь четвертый аргумент, который задает строку, на которую заменяется заданная подстрока, например: $str = 'abcdef'; substr($str, 1, -2,'xxx'); print $str; # axxxef Этот пример можно записать и так: $str = 'abcdef'; substr($str, 1, -2) = 'xxx'; print $str; # axxxef Синтаксис: eof файл?            eof() Аргументы: файл — описатель файла Результат: логическое значение Функция eof возвращает 1, если следующее чтение файла обнаружит конец файла или если данный файл не был открыт. В противном случае возвращается 0. Если аргумент опущен, то проверяется файл, из которого производилась последняя операция чтения. Функция eof() имеет особое назначение. Она относится к псевдофайлу, образованному списком файлов, указанных в командной строке программы, и проверяет наличие входных записей в нем. Подробнее об этом см. описание операции <>. Данная функция используется редко, поскольку все функции ввода PERL возвращают undef при достижении конца файла или ошибке чтения.

Автор: gcc 23.1.2009, 21:06

может кто-то подсказать Код rec_shift( $file, 1 ); почему данные  функции в скрипте без переменной вывода? my $tt = rec_shift( $file, 1 ); идет 3 функции Код seek( $file, -$r, 1 ); read( $file, $buf, $r ); seek( $file, -$r, 1 ); как это понимать, куда записываеться вывод? я хотел переделать эту часть: Код sub filebinsearch { my( $file, $fkey, $beg, $end ) = @_; return undef if $beg == $end; my $oc = int( ( $beg + $end ) / 2 ); # ( $beg + $end ) >> 1 -- 32bit :-( seek( $file, $oc, 0 ); rec_shift( $file, 1 ); $oc = tell( $file ); my( $key, $value ) = rec_read( $file ); return $value if $key eq $fkey; if( $key lt $fkey ) { filebinsearch( $file, $fkey, tell( $file ), $end ); } else { filebinsearch( $file, $fkey, $beg, $oc ); } } но не понял куда записывается вывод... Добавлено @ 21:06 может, Уважаемый arto, однострок покажет

Автор: gcc 24.1.2009, 20:15

File::SortedSeek http://search.cpan.org/~jfreeman/File-SortedSeek-0.015/lib/File/SortedSeek.pm вот еще нашел: никто не подскажет куда зыписывается вывод из функции rec_shift? Код seek( $file, $oc, 0 ); rec_shift( $file, 1 ); $oc = tell( $file );

Автор: KSURi 25.1.2009, 01:03

Цитата(gcc @  23.1.2009,  05:04 ) почему функция filebinsearch запускается внутри самой фукнции? никогда такого не видел Это называется рекурсия Цитата(gcc @  23.1.2009,  21:06 ) но не понял куда записывается вывод... Никуда он не записыватся, т.к. его нет. Эта ф-ия устанавливает курсор чтения (перемещает его построчно). Исходник плохо читаем, пройдитесь по нему perltidy. Возможно тогда найдется больше желающих помочь)

Автор: gcc 25.1.2009, 20:48

KSURi, я откоректировал...   Добавлено через 5 минут и 42 секунды я заметил что там перебор, но куда вывод записывается? смысл, можно ли его записать? как там прмиерно его записать? я пробовал по разному return там убрать но не работает... Код sub filebinsearch {     my ( $file, $fkey, $beg, $end ) = @_;     return undef if $beg == $end;     my $oc = int( ( $beg + $end ) / 2 );    # ( $beg + $end ) >> 1 -- 32bit :-(     seek( $file, $oc, 0 );     my $ln = '';     my $buf;     while (1) {         my $ofs = tell($file);         read( $file, $buf, $read_block_size );         my $o = index( $buf, "\x0a" );         if ( $o >= 0 ) {             seek( $file, $ofs + $o + 1, 0 );             $ln .= substr( $buf, 0, $o );             return split( /\t/, $ln );         }         $ln .= $buf;     }     rec_shift( $file,  );     $oc = tell($file);     my ( $key, $value ) = rec_read($file);     return $value if $key eq $fkey;     if ( $key lt $fkey ) {         filebinsearch( $file, $fkey, tell($file), $end );     }     else {         filebinsearch( $file, $fkey, $beg, $oc );     } }

Автор: arto 26.1.2009, 10:05

perl -MData::Dumper -0x0a -lne '%hash = ( %hash, split "\t" ); END { print Dumper \%hash }' file

Автор: KSURi 26.1.2009, 12:05

arto, one-liner'ы конечно хороши, в разумных пределах. Но для 20 гигабайтового файла и поиска подстроки в нем это не подойдет.

Автор: amg 26.1.2009, 14:17

gcc, если Вас не сильно затруднит, проверьте, пож., решение на основе БД на Вашем 20Г файле. У себя я попробовал на 175М -- база создается очень долго и занимает много на диске (у меня -- более 5 мин и 300 с лишним М), зато поиск ключей по ней идет практически мгновенно. Вот код (parse.pl): Код #!/usr/bin/perl -ws use vars qw($create $DB); die " Usage: $0 [-DB=parse.db] -create parse.txt        $0 [-DB=parse.db] key1 key2 ... " unless @ARGV || $create;  my $db = $DB || 'parse.db'; use DB_File; tie %hash, "DB_File", $db or die "Can't open $db: $!\n"; if ($create) {   while (<>) {     my ($k,$v) = split, /\t/;     $hash{$k} = $v;     print "\r$.";   }   print "\nCreation $db done\n"; } else {   while (@ARGV) {     my $key = shift;     print "$key\t$hash{$key}\n";   } } untie %hash; Пользоваться: Код parse.pl -create parse.txt  # Создать БД из parse.txt (который 20Г) parse.pl key  # Искать значение, соответствующее ключу key

Автор: KSURi 26.1.2009, 14:56

Я так полагаю это лабораторная работа в ВУЗе?) На реализацию бинарного поиска. Если да, то вариант с DB_File врядли подойдет.

Автор: gcc 26.1.2009, 16:47

эта одни мужики задали задание чтобы выполнить работу, я сначало подумал что это шутка, потом сказали что можно сделать, вообщем я попробую еще тем модулем seek.. но файл должен быть текстовый вообще-то гониво это все равно, извиняюсь        Добавлено @ 16:52 KSURi, теоритически такое решение применять врядли где-то будут, или зачем тогда придумали Oracle ?

Автор: gcc 26.1.2009, 17:09

KSURi, тут не совсем бинарный поиск, а бинараный поиск с алгоритмом передвижения по файлу, бинанрый поиск по массиву пишеться точно в одну строку тем более врядли где-то есть такие данные упорядоченные...

Автор: arto 27.1.2009, 11:19

Цитата(KSURi @ 26.1.2009,  12:05) arto, one-liner'ы конечно хороши, в разумных пределах. Но для 20 гигабайтового файла и поиска подстроки в нем это не подойдет. "есть файл ... как мне сделать хєши?"

Автор: gcc 27.1.2009, 11:36

извините arto,  http://unixforum.org.ua/index.php?topic=18004 (я сначало хотел спросить одно, потом другое, оказалось что оно не заработало, но если я сюда выложу задание, то тот кто будет искать может тут найти свое задание и ответ который я ему отправлю ) я попробую модулем File::SortedSeek

Автор: gcc 28.1.2009, 12:57

подскажите как узнать сколько строк в файле? так не получается: Код $ofs = tell( $file ); print $ofs; так тоже: Код $ofs = tell( BIG ); print $ofs; хочю сделать так: Код my $file = 'dfsdf.txt';   use File::SortedSeek ':all';   open <BIG>, $file or die $!;   $tell = alphabetic( *BIG, 4 );   $line = <BIG>; @serv_array = split( /\t/, $line, 2 ); print $serv_array[1]; и так сам поиск: Код sub BinSearch { my ($target, $cmp) = @_; my @array = @{$_[2]}; my $posmin = 0; my $posmax = $#array; return -0.5 if &$cmp (0, \@array, $target) > 0; return $#array + 0.5 if &$cmp ($#array, \@array, $target) < 0; while (1)   {   my $mid = int (($posmin + $posmax) / 2);   my $result = &$cmp ($mid, \@array, $target);      if ($result < 0)     {     $posmin = $posmax, next if $mid == $posmin && $posmax != $posmin;     return $mid + 0.5 if $mid == $posmin;     $posmin = $mid;     }   elsif ($result > 0)     {     $posmax = $posmin, next if $mid == $posmax && $posmax != $posmin;     return $mid - 0.5 if $mid == $posmax;     $posmax = $mid;     }   else     {     return $mid;     }   } } http://www.perlmonks.org/?node_id=503154 если получится и если это правильно

Автор: amg 28.1.2009, 13:14

Цитата(gcc @  28.1.2009,  12:57 ) подскажите как узнать сколько строк в файле? $count += tr/\n/\n/ while sysread(FILE, $_, 2 ** 20);

Автор: ginnie 28.1.2009, 13:17

gcc, строка Код $tell = alphabetic( *BIG, 4 ); для Вашего файла должна быть Код $tell = alphabetic( *BIG, 'qq4' ); еще надо проверять, было ли точное совпадение ключа при помощи File::SortedSeek:was_exact(), т.к. функция alphabetic() может вернуть значение для ключа, следующего за искомым, если он отсутствует в файле.   gcc, для чего Вы привели код функции BinSearch(), если модуль File::SortedSeek делает то, что Вам нужно?

Автор: gcc 28.1.2009, 13:53

Цитата(ginnie @ 28.1.2009,  13:17) gcc, для чего Вы привели код функции BinSearch(), если модуль File::SortedSeek делает то, что Вам нужно? сказали "написать функцию",  (функцию которую я тут привел,  я взял ее с другого форума, переделать не молучилось, на вопрос которы я задал тут никто не ответил) попробую этот модуль... как я сделать поиск/бинарный поиск только с помощюь этого модуля если делать так прмиерно: Код $find = '6'; $tell = alphabetic( *BIG, $find );  @lines = get_between( *BIG, $tell , $tell+7 ); то этот модуль ругается на то что "значение" (второй столбик) маленькое 7 символов или криво выводит результат, ну если я так напишу get_between( *BIG, $tell , $tell+7 );, вот это знаничение $tell+7 должно быть точнее... но определить его я не могу по другому я не понял, или Вы что-то другое имели ввиду?

Автор: ginnie 28.1.2009, 15:09

gcc, опишите, что, по Вашему, должен делать фрагмент Код $find = '6'; $tell = alphabetic( *BIG, $find ); @lines = get_between( *BIG, $tell , $tell+7 );

Автор: gcc 28.1.2009, 15:13

извените, я перепутал, случайно это написал.. метод get_between() по-моиму смотрит так как seek или нет?

Автор: ginnie 28.1.2009, 15:22

gcc,  Код get_between( *BIG, $tell , $tell+7 ); что Вам должна вернуть?

Автор: gcc 28.1.2009, 15:39

я написал функцию, только удалил ее, она возвращала как раз значение только фиксированной длинной... использовать этот метод как массив я хотел, попробую пересмотрю еще раз поиск по 20Мбайт файл работает вот так: Код  $tell = alphabetic( *BIG, 'qq4' );  $line = <BIG>; но это не бинарный поиск

Автор: gcc 28.1.2009, 17:29

ginnie, я сделаю короче просто через seek, 20Gb конечно делать не буду, процессор сильно грузится, а протестирую на меньшем размере, при 20Мбайт вроде бы работает... в этом топике информация есть полезная, наверное еще кому-то будет пригодится всем спасибо...

Автор: ginnie 28.1.2009, 23:04

Цитата(gcc @  28.1.2009,  15:39 ) но это не бинарный поиск А какой? Бинарный и есть! Если мне не верите, смотрите http://search.cpan.org/~jfreeman/File-SortedSeek-0.015/lib/File/SortedSeek.pm#DESCRIPTION (последний абзац: ...This is the halving the difference or binary search method...).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)