VPF::Работа с очень большими файлами. Поиск информации.

Trikselion

Дата 14.6.2011, 20:00 (ссылка)

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

Загрузка ...

Новичок

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

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

Сломал мозг. Обращаюсь к коллективному разуму =) Помогите советом.
Давно не програмил на перле, а тут надо решить именно на нем такую задачку.

Условие задачи таково:

Обработка файла unix.mailbox. Письма идут подряд в одном файле в текстовом формате, длина  строк  не  превышает  1000 байт. Надо рассортировать письма по отправителям и разбить по файлам что б каждый файл - отдельный отправитель в таком же формате.  Признак  начала  письма - строка,  начинающаяся  на  слово  From  ,  сразу  за которым следует 1 пробел,  сразу за которым следует e-mail отправителя, сразу за которым следует  пробел  и  какая-то  дополнительная  информация.  Писем очень много,  некоторые  из  них  могут  иметь большой объем. Объем входного файла может составлять много гигабайт. С другой стороны, кол-во разных отправителей не превышает 100.

Есть ряд требований:

1) объем  RAM  ограничен,  поэтому не нужно хранить в памяти "лишних"
структур и данных, без которых можно обойтись;
2) каждый файл должен открываться/закрываться только 1 раз;
3) нельзя использовать сторонние модули;
4) решение  ожидается  в виде одного относительно короткого файла (не более  примерно 50 строк на Perl). Не нужно усложнять решение каким-то дополнительным функционалом, проверками данных и т. п.

Я написал вот такую программу:

Цитата

#!/usr/bin/perl -w

use Fcntl;

sysopen(IN, "unix.mailbox", O_RDONLY) or die "Can't open input file $!";

$cnt = 0;

while(<IN>) {
       if (/^From /) {
             $mail = $_;
             if ($mail =~ s/From ([\w\-\.]+)@([\w\-\.]+\.\w{2,10}) .+/$1-at-$2/) {
                     if (!$adr{$mail}) {
                         $cnt++;
                         $adr{$mail} = $cnt;
                         sysopen($adr{$mail}, $cnt, O_WRONLY|O_TRUNC|O_CREAT) or die "Can't create output file $mail $cnt: $!";
                     }
             }
       }
       syswrite($adr{$mail}, $_);
}

close(IN);

foreach (keys %adr) {
         close($adr{$_});
}

На что мне ответили вот что:

1) use strict; -- с этого начинается любая программа на Perl;
2) мы не просили валидировать адреса e-mail;
3) уберите из программы всё лишнее: лишние переменные и действия, которые не обязательны для решения задачи;
4) новая версия Вашей программы должна работать на тех же данных (для большого файла) значительно (на десятки процентов) быстрее старой. Конкретный прирост производительности, конечно, будет зависеть от входных данных и аппаратного обеспечения, но навскидку мы ожидаем рост скорости в 50..70% или более.
Как итог Ваших изменений, Ваша программа должна стать легче читаемой и более быстрой.

Ну, насчет стрикт - это мне ясно. Насчет валидности адресов не совсем понятно... А как еще определить что это емейл, кроме как проверить на валидность? А вдруг просто случайное совпадение... К тому же у меня на проверке еще завязано создание файлов.

А насчет производительности совсем не ясно...

СОС =)

Это сообщение отредактировал(а) Trikselion - 14.6.2011, 20:05

gcc

Дата 14.6.2011, 22:08 (ссылка)

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

Загрузка ...

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

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

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

может быть подойдет File::SortedSeek

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

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

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

afiskon

Дата 15.6.2011, 06:31 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 294
Регистрация: 31.3.2011
Где: Россия, Москва

Репутация: нет
Всего: 4

Похоже на тестовое задание, которое нужно выполнить, чтобы попасть на собеседование. Угадал?

Если я правильно понял задание, вам нужно что-то вроде этого:

Код


#!/usr/bin/perl
use strict;

open my $fid, "<", "unix.mailbox"
  or die $!;
my $line = <$fid>;

while($line) { # (defined($line))? ($line ne "")?
  chomp($line);
  if($line !~ m#^From: ([^\ ]+) #i) {
    die "Invalid line format: $line";
  }
  my $from = $1;
  my $msg = "";
  
  while($line = <$fid>) {
    if($line =~ m#^From: ([^\ ]+) #i) {
      last;
    }
    $msg .= $line;
  }
  parseFromMsg($from, $msg);
}

close $fid;

sub parseFromMsg {
  my($from, $msg) = @_;

  # тут парсим ($from, $msg) - можно сразу писать в файл,
  # образованный от имени $from
  # а можно запустить несколько дочерних процессов (по одному на отправителя)
  # и пересылать им $msg.
}

Как один из способов распараллеливания, можно использовать скрипт из этой заметки (см пункт 2). Только его нужно будет немного переписать. И желательно замерить скорость, чтобы точно сказать - поможет распараллеливание или нет. Еще один способ ускорить скрипт - использовать вместо регулярных выражений функции типа strstr.

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

Записки программиста

Trikselion

Дата 15.6.2011, 15:50 (ссылка)

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

Загрузка ...

Новичок

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

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

gcc: хм... хотя мне не совсем ясно, что они имели в виду под сторонними модулями.

afiskon:

Учебное задание ))

Тоесть получается, что здесь возможный прирост скорости будет достигаться за счет создания отдельных процессов? Ушел разбираться =)

кстати, использовать вместо регексов субстр это хорошая тема. И как я про нее забыл... Привык к регексам =)

Всем спасибо! Ушел думать )

afiskon

Дата 15.6.2011, 16:44 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 294
Регистрация: 31.3.2011
Где: Россия, Москва

Репутация: нет
Всего: 4

Цитата

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

хз, эксперементировать нужно. Но как минимум, если выходные файлы лежат на отдельных винтах или в tmpfs, то прирост будет 100 пудово - иначе не факт.

Цитата

Привык к регексам =)

Да вообще непонятно, кому нужны эти 100500 функций для работы со строками, когда есть =~ ;)

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

Записки программиста

loginn

Дата 28.8.2011, 21:35 (ссылка)

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

Загрузка ...

Новичок

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

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

Как говорится, дешево и сердито:

Код


#!/usr/bin/perl -w
$sender = "";
open (Mailbox, "</var/unix.mailbox");
while ($current_string = <Mailbox>) {
  if (($current_string =~ /^From\s([0-9a-zA-Z_\.\-]+@[0-9a-zA-Z_\.\-]+)\s/) or (eof Mailbox)) {       #new letter
    if(defined $H{$sender}) {           
      print {$H{$sender}} @buffer;       #dumping previous letter
      @buffer = (); }                     #clean buffer
    $sender = $1;                        
    unless (defined $H{$sender}) {
      open ($H{$sender}, ">>/var/mailboxes/$sender"); }
    push @buffer, $current_string;}
    else {                                                                                             #in current letter
      push @buffer, $current_string;
      if ($#buffer == 100000) {
        print {$H{$sender}} @buffer;       #dumping 100000 lines of current letter
        @buffer = (); } } }                #clean buffer
close (Mailbox);
foreach (keys %H) {                       #closing all clients file handlers
      close ($H{$_}); }

Это сообщение отредактировал(а) loginn - 28.8.2011, 21:39

arto

Дата 30.8.2011, 09:56 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

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

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

perl -MIO::File -nle 'BEGIN{ $/ = "From " } m#(\S+)# or next; $io{$1} ||= new IO::File "> $1"; $io{$1}->print("From: $_")'

Pilat66

Дата 21.9.2011, 19:32 (ссылка)

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

Загрузка ...

Новичок

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

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

Одно замечание.. Реальный unix mailbox ни одна из предложенных программ не прочитает.

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