VPF::разделение - Форум программистов

KSURi

Дата 22.1.2009, 20:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 887
Регистрация: 8.6.2006
Где: Russia

Репутация: 20
Всего: 27

У меня такое ощущение, что все говорят о разных вещах) Правильно ли я понимаю, что вам надо организовать поиск подстроки в файле?

Если да, то вам как раз надо использовать алгоритм двоичного поиска (ака метод деления пополам, дихотомия и т.д.). Он предназначен для поиска в упорядоченных массивах. Понятное дело, что считывать ваш огромный файл в память нельзя. Поэтому придется абстрагироваться от перловых массивов и принять файл за массив. Для этого придется написать ф-ию, которая будет перемещать указатель чтения построчно (учитывая строгий формат файла это не сложно). Ну а потом собственно реализовать алгоритм поиска (здесь есть более простое и понятное его объяснение) [а может на CPAN уже есть].

ЗЫ: спасибо человеку, который когда-то меня ткнул носом в эту вещь

Добавлено через 1 минуту и 44 секунды
упс, надолго я оставил страницу с постингом... уже все до меня написали)

--------------------

Died at Life.pl line 21

gcc

Дата 23.1.2009, 05:04 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

заработало короче, не знаю или правильно, но

меняем:

Код


return split( /\t/, $ln );

на:

Код


return split( / /, $ln );

а может кто-то объяснить что такое $buf и $r?

почему функция filebinsearch запускается внутри самой фукнции? никогда такого не видел

и где в данном скрипте ключевые моменты (потому что не понятно на все 100% принцип действия, но некоторые момонты понятные, но остальные нет) если это реально... smile

еще раз нашел:

Код


Для перемещения по файлу можно воспользоваться функциями 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, 09:17

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

gcc

Дата 23.1.2009, 21:06 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

может кто-то подсказать

Код


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, однострок покажет smile

Это сообщение отредактировал(а) gcc - 23.1.2009, 21:09

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

gcc

Дата 24.1.2009, 20:15 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

File::SortedSeek
http://search.cpan.org/~jfreeman/File-Sort...e/SortedSeek.pm

вот еще нашел:

никто не подскажет куда зыписывается вывод из функции rec_shift?

Код


seek( $file, $oc, 0 );
rec_shift( $file, 1 );
$oc = tell( $file );

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

KSURi

Дата 25.1.2009, 01:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 887
Регистрация: 8.6.2006
Где: Russia

Репутация: 20
Всего: 27

Цитата(gcc @ 23.1.2009, 05:04

)

почему функция filebinsearch запускается внутри самой фукнции? никогда такого не видел

Это называется рекурсия

Цитата(gcc @ 23.1.2009, 21:06

)

но не понял куда записывается вывод...

Никуда он не записыватся, т.к. его нет. Эта ф-ия устанавливает курсор чтения (перемещает его построчно).

Исходник плохо читаем, пройдитесь по нему perltidy. Возможно тогда найдется больше желающих помочь)

Это сообщение отредактировал(а) KSURi - 25.1.2009, 01:04

--------------------

Died at Life.pl line 21

gcc

Дата 25.1.2009, 20:48 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

KSURi, я откоректировал... smile

Добавлено через 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 );
    }
}

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

arto

Дата 26.1.2009, 10:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1495
Регистрация: 31.10.2004

Репутация: 38
Всего: 40

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

KSURi

Дата 26.1.2009, 12:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 887
Регистрация: 8.6.2006
Где: Russia

Репутация: 20
Всего: 27

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

--------------------

Died at Life.pl line 21

amg

Дата 26.1.2009, 14:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

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

Это сообщение отредактировал(а) amg - 26.1.2009, 15:07

KSURi

Дата 26.1.2009, 14:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 887
Регистрация: 8.6.2006
Где: Russia

Репутация: 20
Всего: 27

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

--------------------

Died at Life.pl line 21

gcc

Дата 26.1.2009, 16:47 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

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

вообще-то гониво это все равно, извиняюсь smile

Добавлено @ 16:52
KSURi, теоритически такое решение применять врядли где-то будут, или зачем тогда придумали Oracle ? smile

Это сообщение отредактировал(а) gcc - 26.1.2009, 17:11

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

gcc

Дата 26.1.2009, 17:09 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

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

тем более врядли где-то есть такие данные упорядоченные...

Это сообщение отредактировал(а) gcc - 26.1.2009, 17:10

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

arto

Дата 27.1.2009, 11:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1495
Регистрация: 31.10.2004

Репутация: 38
Всего: 40

Цитата(KSURi @ 26.1.2009, 12:05)

"есть файл ...
как мне сделать хєши?"

gcc

Дата 27.1.2009, 11:36 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

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

)

я попробую модулем File::SortedSeek

Это сообщение отредактировал(а) gcc - 27.1.2009, 17:51

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

gcc

Дата 28.1.2009, 12:57 (ссылка)

(нет голосов)

Загрузка ...

Агент алкомафии

Профиль
Группа: Участник
Сообщений: 2691
Регистрация: 25.4.2008
Где: %&й

Репутация: 1
Всего: 17

подскажите как узнать сколько строк в файле?

так не получается:

Код


$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

если получится и если это правильно

Это сообщение отредактировал(а) gcc - 28.1.2009, 12:58

--------------------

Perl FAQ
freelance
perl, jquery, js, php
perl, jquery

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Общие вопросы \| Следующая тема »