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

gcc

Дата 22.1.2009, 12:55 (ссылка)

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

Загрузка ...

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

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

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

есть файл

Код


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
        };

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

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

gcc

Дата 22.1.2009, 13:38 (ссылка)

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

Загрузка ...

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

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

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

фай подправил

сделал не бинарный

Код


qq1 uu1
qq2 uu2
qq3 uu3

хотя не знаю...может быть файл такой как я написал в первом посте

так работает

Код



  for $element(split '\0xa', $data[$loopindex]){
    ($key, $value) = split ' ', $element;

можите подсказать еще пожалуйста:

при бинарном поиске в таком файле, по ключю найти значение, только такой файл занимает 20Гбт, нужно использовать массив хєшей или через свзяку встроенных функций seek, rindex, index, read, tell?

Это сообщение отредактировал(а) gcc - 22.1.2009, 13:41

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

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

amg

Дата 22.1.2009, 14:16 (ссылка)

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

Загрузка ...

Эксперт

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

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

gcc, на больших файлах нельзя делать @data=<F>; -- памяти может не хватить, да и медленнее это, чем while (<F>) {push @data, $_} (если все же нужно зачитать файл целиком).

Насколько я вижу -- у Вас обычный текстовый файл. Зачем с ним обращаться, как с бинарным?

Хэш или массив хэшей из файла размером 20Гбт -- памяти может не хватить (если только ключи не будут часто повторяться). Если нужно многократно искать по ключу найти значение (из одного и того же файла),
то лучший выход, наверное, создать хэш, связанный со специальным дисковым файлом (модули для этого есть). Тогда создание хэша потребует много времени (и диска), зато поиск значений по ключам будет сравнительно быстр.

gcc

Дата 22.1.2009, 14:21 (ссылка)

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

Загрузка ...

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

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

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

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

это реализуемо? тут нужен массив или не объязательно?

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

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

KSURi

Дата 22.1.2009, 14:44 (ссылка)

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

Загрузка ...

Опытный

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

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

gcc, может вы про какой-то другой "бинарный поиск" подумали? Вообще это алгоритм.

Это сообщение отредактировал(а) KSURi - 22.1.2009, 14:45

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

Died at Life.pl line 21

gcc

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

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

Загрузка ...

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

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

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

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

Это сообщение отредактировал(а) gcc - 22.1.2009, 14:50

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

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

amg

Дата 22.1.2009, 14:59 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(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 (ссылка)

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

Загрузка ...

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

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

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

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

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

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

amg

Дата 22.1.2009, 16:24 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(gcc @ 22.1.2009, 15:10

)

можно ли быстрый поиск сделать по такому файлу или нет?

Именно по файлу -- нет. Скорость современных жестких дисков -- до 100 Мбт/с, 20Гбт -- 200 с (если не супер-рейд какой-нибудь).

Можно пробовать создать БД (тот же MySQL, или tie %hash, 'DB_File'). Создание базы -- долго, зато поиск будет быстр.

Если же поиск нужно вести каждый раз в новом 20Гбт файле, то, IMHO, в 10 с никак не уложиться.

gcc

Дата 22.1.2009, 16:34 (ссылка)

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

Загрузка ...

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

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

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

но вот мне сказали что такой код работает, только я не знаю какой файл на самом деле с какми разделителями, и что за 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";

Это сообщение отредактировал(а) gcc - 25.1.2009, 20:46

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

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

ginnie

Дата 22.1.2009, 17:00 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

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

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

Написать код, понятный компьютеру, может каждый, но только хорошие программисты пишут код, понятный людям. (Мартин Фаулер. Рефакторинг)

gcc

Дата 22.1.2009, 17:06 (ссылка)

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

Загрузка ...

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

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

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

ginnie, на этом форуме обсуждалось что это можно сделать, ссылку не помню - сейчас поищу

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

Добавлено @ 17:07
может быть не 1, а 2

Добавлено через 4 минуты и 6 секунд
вот

http://forum.vingrad.ru/forum/topic-241552.html

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

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

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

ginnie

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

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

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

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

gcc

Дата 22.1.2009, 17:21 (ссылка)

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

Загрузка ...

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

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

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

да, именно так

Код


qq1\tuu1\x0Aqq2\tuu2\x0Aqq3\tuu3\x0A

Добавлено через 1 минуту и 45 секунд
только скорее всего так правильней

Код


qq1 uu1
qq2 uu2
qq3 uu3

\t - это табулятор
\x0A - абзац

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

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

ginnie

Дата 22.1.2009, 18:22 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

gcc, в указанном примере формат обрабатываемого файла такой-же как у Вас.

запускается script.pl filename key

если не находит ключ, добавьте в функцию filebinsearch() строчку

Код


print "check key $key$/";

перед

Код


return $value if $key eq $fkey;

и проанализируйте вывод

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

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

amg

Дата 28.1.2009, 13:14 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(gcc @ 28.1.2009, 12:57

)

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

$count += tr/\n/\n/ while sysread(FILE, $_, 2 ** 20);

ginnie

Дата 28.1.2009, 13:17 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

gcc, строка

Код


$tell = alphabetic( *BIG, 4 );

для Вашего файла должна быть

Код


$tell = alphabetic( *BIG, 'qq4' );

еще надо проверять, было ли точное совпадение ключа при помощи File::SortedSeek:was_exact(), т.к. функция alphabetic() может вернуть значение для ключа, следующего за искомым, если он отсутствует в файле.

gcc, для чего Вы привели код функции BinSearch(), если модуль File::SortedSeek делает то, что Вам нужно?

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

gcc

Дата 28.1.2009, 13:53 (ссылка)

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

Загрузка ...

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

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

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

Цитата(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 должно быть точнее... но определить его я не могу

по другому я не понял, или Вы что-то другое имели ввиду?

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

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

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

ginnie

Дата 28.1.2009, 15:09 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

gcc, опишите, что, по Вашему, должен делать фрагмент

Код


$find = '6';
$tell = alphabetic( *BIG, $find );
@lines = get_between( *BIG, $tell , $tell+7 );

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

gcc

Дата 28.1.2009, 15:13 (ссылка)

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

Загрузка ...

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

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

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

извените, я перепутал, случайно это написал..

метод get_between() по-моиму смотрит так как seek или нет?

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

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

ginnie

Дата 28.1.2009, 15:22 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

gcc,

Код


get_between( *BIG, $tell , $tell+7 );

что Вам должна вернуть?

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

gcc

Дата 28.1.2009, 15:39 (ссылка)

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

Загрузка ...

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

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

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

я написал функцию, только удалил ее, она возвращала как раз значение только фиксированной длинной...

использовать этот метод как массив я хотел, попробую пересмотрю еще раз

поиск по 20Мбайт файл работает вот так:

Код


 $tell = alphabetic( *BIG, 'qq4' );
 $line = <BIG>;

но это не бинарный поиск smile

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

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

gcc

Дата 28.1.2009, 17:29 (ссылка)

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

Загрузка ...

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

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

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

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

в этом топике информация есть полезная, наверное еще кому-то будет пригодится

всем спасибо...

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

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

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

ginnie

Дата 28.1.2009, 23:04 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

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

Цитата(gcc @ 28.1.2009, 15:39

)

но это не бинарный поиск

А какой? Бинарный и есть! Если мне не верите, смотрите описание модуля (последний абзац: ...This is the halving the difference or binary search method...).

Это сообщение отредактировал(а) ginnie - 28.1.2009, 23:06

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

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