13 мар. 2011 г.

Миф о продуктивности Python-а

Последние 2-3 года моя основная работа связана с Perl-ом и каждая попытка написать на Python-е что-нибудь "для души" заканчивается раздражением. Спотыкаешься там, где, казалось бы, никаких "коряг" быть не должно. Так произошло и в эти выходные.

Мне понадобилось написать программку, которая разбирает access.log и раскладывает его поля по таблицам базы данных SQLite. Вполне тривиальная задачка, кто только ей ни занимался.

Сам парсер не представляет из себя ничего сложного. Вот пример строки лог-файла:

89.179.242.83 - - [06/Mar/2011:07:09:48 +0000] "GET /themes/_pebble/handheld.css HTTP/1.1" 200 1020 "http://www.lunarium.ru/2011/02/19/1298158440000.html" "Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_6; ru-ru) AppleWebKit/533.19.4 (KHTML, like Gecko) Version/5.0.3 Safari/533.19.4"


А вот регулярное выражение, которое прекрасно с ней справляется (я позаимствовал его из Johen's blog :

parts = [
    r'(?P\S+)', # host %h
    r'\S+', # indent %l (unused)
    r'(?P\S+)', # user %u
    r'\[(?P


В одной из таблиц базы данных я решил хранить IP-адреса хостов, с которых приходят запросы.  Хранить их удобнее в виде целых чисел, а не 4 значений, разделенных точками. Системные библиотеки прекрасно понимают и тот и другой формат.

Berkana:~ sergey$ ping 3232235777
PING 3232235777 (192.168.1.1): 56 data bytes
64 bytes from 192.168.1.1: icmp_seq=0 ttl=255 time=6.288 ms


В Python-овской бибиотеке urllib имеется функция inet_aton, возвращающая упакованное бинарное значение, которое может потребоваться при обмене данными с низкоуровневыми С-библиотеками.  Из него можно получить целочисленное значение, для этого его надо распаковать, используя  стандартный модуль struct. Беда в том, что документация к inet_aton немногословна и мне понадобилось немало времени, чтобы понять, с какими ключами вызывать функцию struct.unpack для получения нужного результата.

import socket
import struct
struct.unpack('!L', socket.inet_aton(ip))

, где ip представляет собой строку типа: '192.168.1.1'.

Обратная операция:
socket.inet_ntoa(struct.pack('!L', i))

, где i представляет собой целое число.

Я в курсе, что можно плюнуть на библиотеки и поступить по-простому:

a << 24 | b << 16 | c << 8 | d


, где a, b, c, d —  части Ip-адреса. Но не стал этого делать из принципа, дабы не плодить сущности.

Следующая трудность возникла снова на пустом месте. В таблице referer я решил хранить адреса, с которых посетители заходят на мой сайт. URL-адреса могут быть закодированы (URL-encoded). Типичный пример  адрес страницы поисковой системы с результатами, в которую включена поисковая фраза:

http://go.mail.ru/search?q=%E4%EE%EB%E3%EE%F2%E0%20%E4%ED%FF%20%ED%E0%20%EC%E0%F0%F2%202011%E3%EE%E4%E0&rch=e&num=10&sf=90%22


Тарабарщина со знаками процентов в данном случае ни что иное как фраза "долгота дня на март 2011года". Разумеется, хранить удобнее читаемый текст. В Perl-е, чтобы расшифровать закодированную таким методом строку, достаточно импортировать модуль URI::Escape и вызвать его функцию uri_unescape(). В Python-е для этой же цели служат urllib.unquote() и urllib.unquote_plus().


>>> import urllib
>>> url = "http://go.mail.ru/search?q=%E4%EE%EB%E3%EE%F2%E0%20%E4%ED%FF%20%ED%E0%20%EC%E0%F0%F2%202011%E3%EE%E4%E0&rch=e&num=10&sf=90"
>>> unquoted_url = urllib.unquote_plus(url)
>>> unquoted_url
'http://go.mail.ru/search?q=\xe4\xee\xeb\xe3\xee\xf2\xe0 \xe4\xed\xff \xed\xe0 \xec\xe0\xf0\xf2 2011\xe3\xee\xe4\xe0&rch=e&num=10&sf=90'


Поскольку SQLite работает с UTF-8, полученное значение необходимо перевести в unicode.

>>> unicode(unquoted_url)
Traceback (most recent call last):
File "", line 1, in
UnicodeDecodeError: 'ascii' codec can't decode byte 0xe4 in position 27: ordinal not in range(128)


Что случилось? А дело в том, что функция unicode не знает кодировку исходной строки. Раз запрос исходил из mail.ru, наверняка тут русская windows-кодировка. Так и есть!

>>> unicode(unquoted_url, encoding='cp1251')
u'http://go.mail.ru/search?q=\u0434\u043e\u043b\u0433\u043e\u0442\u0430 \u0434\u043d\u044f \u043d\u0430 \u043c\u0430\u0440\u0442 2011\u0433\u043e\u0434\u0430&rch=e&num=10&sf=90'


Ну, а как быть с другими кодировками? ...Вспоминаю, что для угадывания кодировки текста существует питоновский модуль chardet. Он считается достаточно надежным, однако для моей цели явно не подходит  уж слишком часто промахивается. Видимо потому, что исходный текст слишком короток. Пришлось написать вот такой костыль:

def decode_referer(url):
    refurl = urllib.unquote_plus(url)
    try:
       refurl = unicode(refurl)
    except UnicodeDecodeError:
       logger.warn("Could not decode string: '%s'. Trying cp1251..." % refurl)
       try:
           refurl = unicode(refurl, encoding='cp1251')
           logger.info('Success.')
       except 
UnicodeDecodeError:
           logger.warn("Could not decode string. Trying to guess encoding...")
           enc = chardet.detect(refurl)['encoding']
           logger.warn('Detected %s' % enc)
           try:
               refurl = unicode(refurl, encoding=enc)
               logger.info('Success.')
           except UnicodeDecodeError:
               logger.error('Could not decode string. Will store it as is')
    return refurl



...И кто придумал миф о продуктивности Python-а?

19 нояб. 2010 г.

Ленивая дата

Календарные функции, представленные в предыдущей заметке, работают, исходя из наивного предположения, что на вход поступают правильные данные. В каких-то случаях ничего плохого не произойдет. К примеру, при вычислении юлианской даты на 29 февраля 1975г (в феврале 1975 было 28 дней), результат будет таким же как для 1 марта:
$ perl julian.pl 1975 2 29
JD: 2442472.500000
JD at 0h: 2442471.500000
Fri

$ perl julian.pl 1975 3 1
JD: 2442472.500000
JD at 0h: 2442471.500000
Fri
Хорошим такое API никак не назовешь. Самое время задуматься над созданием удобного для использования класса.

В одних случаях нужно получать из календарной даты юлианскую, в других -- наоборот. Поэтому объект должен инициализироваться как из первой, так из второй даты. Если на входе год, месяц и число, то они сохраняются, а юлианская дата неопределена (undef) и вычисляется лениво, т.е только при вызове метода djd. Точно так же, если объект создан с аргументом djd, календарная дата неопределена до тех пор, пока ее не запросили.

В Perl-е не существует перегрузки методов, следовательно, нельзя создать два разных конструктора: один -- с календарной датой на входе, другой с юлианской. Можно было бы передавать в конструктор new именованные аргументы, что-то вроде:
Julian->new(date => \%ymd, djd => $scalar)
Но тогда пришлось бы нагромождать проверки: не заданы ли сразу оба аргумента и какой именно задан. А потом еще проверять правильность либо первого либо второго. Проще создать два "фабричных" метода:
  • new_from_date(year => $scalar, month => $scalar, day => $scalar)
  • new_from_djd($djd)

Как правило, я стараюсь не использовать модуль Params::Validate, который создан как раз для проверки входных параметров -- уж больно велики накладные расходы, да и ни к чему превращать динамический язык в подобие Java. Но тут как раз тот случай, когда без него не обойтись.

Начнем с более простого метода new_from_djd.
...
use Params::Validate qw/:all/;
use Readonly;
Readonly our $DJD_TO_JD => 2415020;

...

sub new_from_djd {
my $class = shift;

validate_pos(
@_,
{
type => SCALAR,
regex => qr/^[-+]?0*(\d+|(?:\d*\।\d+))$/,
callbacks => {
'djd range' => sub{ $_[0] >= -$DJD_TO_JD }
}
}
);

bless {
_djd => shift,
_date => undef,
}, $class
}
...
Поскольку параметры здесь не именованные, а позиционные, для валидации данных используется метод validate_pos из пакета Params::Validate. Имя класса предварительно убрано из списка аргументов ( @_ ). Проверка производится по трем критериям:
  • type => SCALAR
    аргумент должен быть скаляром
  • qr/^[-+]?0*(\d+|(?:\d*\.\d+))$/
    аргумент должен быть целым или десятичным числом, с любым количеством ведущих нулей и с необязательным ведущим "плюсом" или "минусом"
  • 'djd range' => sub{ $_[0] >= -$DJD_TO_JD }
    число не должно быть меньше нулевой стандартной юлианской даты (напомню, что видоизмененная юлианская дата, которую мы используем, больше стандартной на 2415020 суток. Функции обратного вызова (callbacks) -- "тяжелая артиллерия" пакет Params::Validate. Внутри них можно осуществлять любые проверки. На входе всегда два параметра: проверяемый аргумент и ссылка на все аргументы (хэш или массив).

В конце мы "благословляем" (bless) новорожденный экземпляр с инициализированным атрибутом djd и пустой (до поры до времени) календарной датой.


Второй метод-фабрика сложнее:

...
use Params::Validate qw/:all/;
use Readonly;

Readonly our $DJD_TO_JD => 2415020;
Readonly our $MIN_YEAR => -4713;
Readonly our $MAX_YEAR => 4713;

...

sub new_from_date {
my $class = shift;

my %args = validate(
@_,
{
year => {
type => SCALAR,
regex => qr/^[\-+]?\d{1,4}$/,
callbacks => {
'year range' => sub{
$MIN_YEAR <= $_[0] && $MAX_YEAR >= $_[0]
},
'non-zero year' => sub{ 0 != $_[0] }
}
},

month => {
type => SCALAR,
regex => qr/^0*([1-9]|(1[0-2]))$/,
},

day => {
type => SCALAR,
regex => qr/^0*([1-9]|([0-2]\d)|(3[0,1]))(\।\d+)?$/,
callbacks => {
'day range' => sub{
my ($d, $arg) = @_;
$d >= 1 &&
$d < _days_per_month($arg->{year}, $arg->{month}) + 1;
}
}
},
}
);


bless {
_djd => undef,
_date => \%args,
}, $class
}
...
Здесь аргументы именованные, поэтому для их валидации используется метод validate.
  • год проверяется по четырем критериям:
    1. тип аргумента -- скаляр
    2. аргумент -- положительное или отрицательное целое число
    3. диапазон: от 4713г. до н.э до 4713г. н.э.
    4. ноль не допускается

  • У месяца тип должен должен быть скаляром, а диапазон (1-12) проверяется регулярным выражением
    qr/^0*([1-9]|(1[0-2]))$/
  • Проверка числа самая сложная.
    1. тип аргумента -- скаляр.
    2. при помощи регулярного выражения проверяем, что это число, возможно, с десятичными долями; при этом целая часть не выходит за рамки диапазона 1-31.
    3. При окончательной проверке диапазона вызывается внешняя функция _days_per_month (см. ниже)
В конце мы "благословляем" (bless) новорожденный экземпляр с сохраненными в хэше годом, номером месяца и числом.

Сколько дней в месяце?

Количество дней во всех месяцах, кроме февраля, в григорианском календаре неизменно.
Чтобы узнать число дней в феврале, надо определить, является ли год високосным. Если да -- то 29, если нет -- то 28. Для определения "високосности" функция _leap_year. Год в григориансмком календаре является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400 (в отличие от "старого стиля", где високосным считался каждый четвертый год).
# является ли год високосным?
sub _leap_year {
my $y = shift;
return 1 if $y % 400 == 0;
return 0 if $y % 100 == 0;
return 1 if $y % 4 == 0;
return 0;
}

# количество дней в месяце
sub _days_per_month {
my ($y, $m) = @_;
return _leap_year($y) ? 29 : 28 if $m == 2; # февраль
return 30 if grep{ $m == $_ } (4, 6, 9, 11); # апрель, июнь, сентябрь, ноябрь
return 31; # остальные месяцы
}

Ленивые вычисления

Два getter-а: djd и date служат для получения юлианской и календарной даты. Если либо одно либо другое не определено (undef), оно вычисляется и сохраняется как аттрибут объекта.
sub djd {
my $self = shift;
$self->{_djd} = _date2djd(%{$self->{_date}})
unless defined $self->{_djd};
$self->{_djd}
}

sub date {
my $self = shift;
$self->{_date} = _djd2date($self->{_djd})
unless defined $self->{_date};
$self->{_date}
}
Функции _date2djd и _djd2date, которые заняты вычислениями, уже описаны в предыдущей заметке. Здесь я только добавил к их названиям нижнее подчеркивания в качестве рекомендации не использовать их снаружи.

10 нояб. 2010 г.

Юлианские даты

Гражданский календарь с его високосными годами и реформами крайне неудобен для расчетов. Сколько дней и часов осталось до начала мото-сезона? В какой день недели произошло памятное событие?... Вместо того, чтобы подсчитывать дни в годах и часы в сутках, удобнее пользоваться действительными числами. Я говорю, конечно, не о вычислениях в уме, а о программировании.

Непрерывный счет дней

Одним из широко известных решений этой проблемы стало так называемое "время Unix", измеряемое количеством секунд, прошедших от полуночи 1 января 1970 года. Прикладные языки программирования предоставляют собственные библиотечные средства. Помнится, в Delphi был тип TDateTime, который хранил даты и время в виде десятичных чисел; целая часть представляла количество дней, прошедших с полуночи 30 декабря 1899 года, а дробная часть -- время суток (стандарт OLE Automation). Базы данных, где проблема расчета времени весьма актуальна, делают это по-своему. Например, TIMESTAMP в MySQL 5.1 отсчитывается от 0ч 1 января 1000 года. Python умеет работать с датами в диапазоне от 1 до 9999 г.г. н.э. В языке Java... впрочем, довольно подробностей. Если нас интересуют события космического масштаба, как-то: восходы и заходы, равноденствия и солнцестояния, фазы Луны, координаты планет, наконец, интервалы времени, не ограничивающиеся нашей эрой -- ни одно из этих средств не подойдет. Что понадобится -- так это юлианские даты, система непрерывного счета времени, которую используют астрономы.

За точку отсчета астрономы приняли средний гринвичский полдень 1 января 4713 г. до н.э. Очередная юлианская дата начинается в 12ч00м UT, что на полсуток расходится с началом гражданских суток. Целая часть числа представляет собой число суток, дробная -- доли суток, прошедшие от полудня. Например, 6ч 17 февраля 1985 года соответствует юлианской дате 2446113.75.

Проблемы с точностью

В эпоху первых персональных компьютеров и программируемых калькуляторов возникали проблемы с точностью. В некоторых системах на хранение вещественных чисел отводилось всего 4 байта (то же самое, что сегодняшнее float), что ограничивало точность 6-7 цифрами. Между тем, юлианские даты часто представлены 11-12 цифрами. Скажем, 11ч. 17 августа 1938 года = JD 2429127.9583

Смещение точки отсчета

Можно принять за точку отсчета вместо даты, отстоящей от нас на 6 тысячелетий, момент поближе. Питер Даффетт-Смит в книге "Astronomy With Your Personal Computer" (Cambridge University Press, 1986) предлагает использовать 12ч GMT 31 декабря 1899 года, т.е. ближайший полдень до начала XXв. Вычисления в рамках ближайших столетий становятся точнее, поскольку на хранение переменных потребуется меньше памяти. Даты до этого момента отрицательные. Чтобы перейти от такой даты (назовем ее вслед за Даффетт-Смитом DJD) к стандартной юлианской (JD), надо прибавить к первой 2415020.

Современное восьмибайтное представление вещественных чисел (double), дает точность до 16 цифр, так что проблема, о которой идет речь, больше неактуальна, однако я намерен следовать методу из книги Даффетт-Смита. Тем более, что момент 12ч UT 31 декабря 1989 года взят не с потолка. Забегая вперед, скажу, что во множестве астрономических расчетов используется время в юлианских столетиях, прошедшее именно от этой даты (T). Формула такова:
T = (JD - 2415020) / 36525
Здесь JD -- юлианская дата. То же самое, что DJD / 36525. Делитель, как нетрудно догадаться, представляет собой количество суток в условном юлианском столетии.

Между прочим, класс DateTime из одноименного пакета Perl содержит метод jd, выдающий стандартную юлианскую дату. В базе SQLite имеется функция для ее получения.

От календаря к юлианской дате

Алгоритм пересчета календарной даты в юлианскую суров и непригляден. Его реализации на любых языках программирования
выглядят примерно одинаково. Ниже представлен ее вариант на языке Perl.

sub date2djd {
my %args = @_;
my $d = $args{date};
my $m = $args{month};
my $y = $args{year};

$y++ if $y < 0;
if ($m < 3) {
$m += 12;
$y--
}
my $b;
if (after_gregorian($y, $m, $d)) {
my $a = floor($y / 100);
$b = 2 - $a + floor($a / 4);
}
else {
$b = 0
}
my $f = 365.25 * $y;
my $c = floor( $y < 0 ? $f - 0.75 : $f ) - 694025;
my $e = floor(30.6001 * ($m + 1));
return $b + $c + $e + $d - 0.5
}
На входе у нее именованные аргументы:
  • year -- номер года, отрицательный для годов до н.э. Нулевое значение недопустимо, т.е. за -1 следует +1 вместо 0.
  • month - номер месяца (1-12)
  • day -- день месяца с долями суток. Например, 07ч 40м первого числа будет соответствовать 1 + (7 + 40 / 60.0) / 24.0
Правильность передаваемых аргументов не проверяется. Все проверки будут реализованы позже, при создании ООП-обертки.

Календарная дата относится к пролептическому григорианскому календарю. Так называется григорианский
календарь, который используется для обозначения дат, предшествовавших его введению. А применен он был впервые 15 октября 1582 года. Вспомогательная функция after_gregorian как раз и помогает определить, приходится ли заданная дата на период до или после календарной реформы

sub after_gregorian {
my ($y, $m, $d) = @_;
return 0 if $y < 1582;
return 1 if $y > 1582;
return 0 if $m < 10;
return 1 if $m > 10;
return 0 if $d <= 15;
return 1;
}
Использовать эту функцию самостоятельно, вне пролептического календаря, не имеет смысла, потому что григорианское летоисчисление не было принято везде одновременно. Наша страна перешла на "новый стиль" в 1918 году.

От юлианской даты к календарю

А вот как выглядит обратная функция, переводящая юлианскую дату в календарную.

sub djd2date {
my $djd = shift;

my $d = $djd + 0.5;
my ($f, $i) = modf($d);

if ($i > -115860) {
my $a = floor($i / 36524.25 + 9.9835726e-1) + 14;
$i += 1 + $a - floor($a / 4);
}
my $b = floor($i / 365.25 + 8.02601e-1);
my $c = $i - floor(365.25 * $b + 7.50001e-1) + 416;
my $g = floor($c / 30.6001);
my $dy = $c - floor(30.6001 * $g) + $f;
my $mn = $g - ($g > 13.5 ? 13 : 1);
my $yr = $b + ($mn < 2.5 ? 1900 : 1899 );
$yr-- if $yr < 1;

return {year => $yr, month => $mn, day => $dy}
}
На входе DJD -- число юлианских дней от начала XX века. На выходе -- хэш того же вида, что и на входе date2jd.

День недели

Система юлианских дней позволяет довольно просто вычислить день недели. Для этого достаточно:
  1. Взять юлианскую дату на начало календарных суток (0ч UT).
  2. Прибавить к ней 1.5.
  3. Найти остаток от деления результата на 7
0 будет соответствовать воскресенью, 1 -- понедельнику, 2 -- вторнику и так до 6 -- субботы.

Добавим две новые функции:
  • jd_midnight для вычисления юлианской даты на календарную полночь, исходя из заданной юлианской даты
  • weekday для вычисления дня недели по юлианской дате на начало суток.

#!/usr/bin/perl -w
use strict;
use warnings;
use POSIX qw/modf floor/;
use Readonly;

Readonly our $DJD_TO_JD => 2415020;
Readonly our @WEEKDAYS => qw/Sun Mon Tue Wed Thi Fri Sat/;

....

sub jd_midnight {
my $j = shift;
my $f = floor($j);
return $f + (abs($j - $f) > 0.5 ? 0.5 : -0.5);
}

sub weekday {
my $j = shift;
my $j0 = jd_midnight($j);
return ($j0 + 1.5) % 7
}


if (@ARGV < 3) {
print "Usage: perl julian.pl YEAR MONTH DAY";
exit(0)
}

my $djd = date2djd(year => $ARGV[0], month => $ARGV[1], day => $ARGV[2]);
my $j = $djd + $DJD_TO_JD;
printf "JD: %f\n", $j;
my $j0 = jd_midnight($j);
printf "JD at 0h: %f\n", $j0;
my $w = weekday($j);
print $WEEKDAYS[$w], "\n";
На месте многоточий в скрипте должны фигурировать функции date2djd и after_gregorian.
Важно: на входе jd_midnight и weekday стандартная юлианская дата, а не DJD. Иначе пришлось бы возиться с отрицательными значениями.

Пример: в какой день недели был запущен первый советский спутник? Известно, что это произошло 4 октября 1957 года 19ч28м34с UT.
Третьим аргументом (день) будет:((34 / 60 + 28) / 60 + 19) / 24 + 4 = 4.8115
$ perl julian.pl 1957 10 4.8115
JD: 2436116.311500
JD at 0h: 2436115.500000
Fri
Пятница, все правильно.

Применение юлианской даты для вычисления дня недели -- стрельба из пушки по воробьям. Но это только начало. Дальше речь пойдет о решении куда более интересных календарных и астрономических задач, а уж там без юлианской даты никуда.

9 нояб. 2010 г.

Perl и рекурсия: ура!

В прошлой заметке выяснилось, что в Python-е рекурсия работает медленнее, чем for-цикл, а тот, в свою очередь -- медленнее, чем while. С циклами все понятно, while всегда быстрее. Что же касается рекурсии, то мне стало любопытно: специфична ли ее низкая производительность для Python-а или это везде так. И я решил ту же задачку -- получение из десятичного числа градусов, минут и секунд -- на Perl-е. Правда, ограничившись двумя
функциями: рекурсивной и циклом-while. Было интересно, насколько сильно здесь рекурсия отстает от цикла.

Результат удивил: рекурсия оказалась эффективнее.



Benchmark: timing 1000000 iterations of Recursive, While-loop...
Recursive: 136.521 wallclock secs (119.61 usr + 0.64 sys = 120.25 CPU) @ 8316.01/s (n=1000000)
While-loop: 142.86 wallclock secs (123.91 usr + 0.66 sys = 124.57 CPU) @ 8027.61/s (n=1000000)



Получается, что на миллион вызовов рекурсивной функции понадобилось 136 секунд. На столько же вызовов нерекурсивной функции ушло 142 секунды. За секунду рекурсивная функция успела отработать примерно на 300 раз больше.
Разница невелика -- и этот факт радует, потому что как система Perl ведет себя предсказуемо. Я не хочу вникать в устройство интерпретатора каждый раз когда приходится задумываться о реализации какого-то алгоритма.

Вот скрипт целиком:


8 нояб. 2010 г.

Python и рекурсия? Увы...

Задача пересчета градусов, выраженных десятичной дробью, в градусы, минуты и секунды для положительного числа x решается тривиально:
  1. Полагаем, что x = исходное число.
  2. Находим целую (i) и дробную (f) часть x.
  3. Целую часть сохраняем как градусы, минуты или секунды.
  4. Если найдены три числа, конец.
  5. Полагаем x = f * 60 и возвращаемся к шагу 2.
Понятно, что эти вычисления производятся в цикле, однако подробности организации цикла пока не важны.
Как быть с отрицательными числами? В этом случае алгоритм немного усложняется:
  1. Полагаем, что x = исходное число.
  2. Находим целую (i) и дробную (f) часть от абсолютного значения x.
  3. Если x положительное, переходим к шагу 5.
  4. Если i не равно 0, полагаем i = -i. В противном случае, f = -f
  5. Целую часть сохраняем как градусы, минуты или секунды.
  6. Если найдены три числа, конец.
  7. Полагаем x = f * 60 и возвращаемся к шагу 2.
Теперь при отрицательном исходном числе, первое значащее число будет отрицательным. Так,
  •  11.75 -- 11:45:0
  • -11.75 -- -11:45:0
  •  -0.75 -- 0:-45:0
Кроме того, удобнее будет секунды возвращать как вещественное, а не целое число, потому что в противном случае при обратном пересчете (градусов, минут и секунд в десятичные градусы) не будет получаться исходное число.
  1. Полагаем, что x = исходное число.
  2. Если при текущем повторении вычисляются секунды, сохраняем x как секунды и выходим из цикла.
  3. Находим целую (i) и дробную (f) часть от абсолютного значения x.
  4. Если x положительное, переходим к шагу 6
  5. Если i не равно 0, полагаем i = -i. В противном случае, f = -f
  6. Целую часть сохраняем как градусы или минуты.
  7. Полагаем x = f * 60 и возвращаемся к шагу 2.
Когда в твоем распоряжении язык высокого уровня можно потратить немало времени в поисках наиболее красивой, эффективной и органичной для языка реализации этого алгоритма. В Python-е имеются как минимум три способа:
  1. рекурсивно;
  2. при помощи циклов: for и while;
  3. с использованием генераторов.
Начнем с рекурсии.



def dms1(x, num_vals=3):

    def mul_60(x, count=1):
        if count == num_vals:
            return [x]
        f, i = math.modf(abs(x))
        if x < 0:
            if i == 0:
                f = -f
            else:
                i = -i
        res = mul_60(f*60.0, count+1)
        res.append(int(i))
        return res

    return tuple(reversed(mul_60(x)))


Функция возвращает кортеж из шестидесятиричных значений: (градусы, минуты, секунды). Именованный параметр num_vals указывает на то, сколько значений необходимо вернуть. Если секунды не нужны, num_vals=2.

Рассмотрим альтернативные способы. Чтобы не повторять один и тот же код, вынесем общую часть в отдельную функцию:

def _next_fi(f):
    negative = f < 0
    f, i = modf(abs(f))
    if negative:
        if i == 0:
            f = -f
        else:
            i = -i
    return (f * 60.0, int(i))

Функция, делающая то же самое при помощи for-цикла, выглядит менее изящно:

def dms2(x, num_vals=3):
    arr = []
    last_j = num_vals - 1
    f = x
    for j in range(0, num_vals):
        if j == last_j:
            arr.append(f)
        else:
            f, i = _next_fi(f)
            arr.append(i)
    return tuple(arr)


А вот вариант с циклом while:

def dms3(x, num_vals=3):
    arr = []
    j = 1
    f = x
    while(j <= num_vals):
        if j == num_vals:
            arr.append(f)
        else:
            f, i = _next_fi(f)
            arr.append(i)
        j += 1
    return tuple(arr)

На очереди -- генераторы. Первый из них использует for, второй -- while

def dms4(x, num_vals=3):
    def mul_60(f):
        last_j = num_vals - 1
        for j in range(0, num_vals):
            if j == last_j:
                yield f
            else:
                f, i = _next_fi(f)
                yield i
    
    return tuple([v for v in mul_60(x)])


def dms5(x, num_vals=3):

    def mul_60(f):

        j = 1
        while(j <= num_vals):
            if j == num_vals:
                yield f
            else:
                f, i = _next_fi(f)
                yield i
            j += 1
    
    return tuple([v for v in mul_60(x)])


Какая из функций работает быстрее всех? Для измерения я воспользовался стандартным методом Timer.timeit, которая по умолчанию запускает заданный код миллион раз. Получилось вот что:

Benchmarking X -> D,M,S

06.465 сек.: 'while'-цикл
07.600 сек.: 'while'-генератор
07.768 сек.: 'for'-цикл
08.544 сек.: 'for'-генератор
09.995 сек.: рекурсия

Увы, самый изящный, на мой взгляд, способ оказался самым медленным! А выиграла самая примитивная функция -- даже не генераторы.

19 февр. 2010 г.

Входной билет на собеседование

Письмо, полученное сегодня утром, показалось мне знакомым. Так и есть! В 2008 году та же "ведущая игровая компания" уже искала Perl программистов. Требования к кандидатам и условия работы стандартные. Далее шла неуклюжая формулировка:

"Решением о дальнейшем сотрудничестве являются:
Успешно выполненное тестовое задание;
Положительные результаты собеседования."

Тестовое задание прилагалось -- даже не одно, а два.
  1. В первом предлагалось написать сценарий регистрации посетителя веб-сайта, входа в систему и редактирования профиля. Дополнительные требования звучали несколько экзотично. Скажем, нельзя использовать модуль CGI (стандартную библиотеку, входящую в дистрибутивы Perl-а, которую обойдет мимо разве что любитель изобретать велосипеды).
  2. Второе задание состояло из 6 вопросов по SQL. Для каждого рекомендовалось привести несколько решений.
Допустим, веб-приложение я напишу за вечер. Хотя нет, вечера не хватит, учитывая необходимость дублировать CGI. Хоть в условиях и сказано, что можно ограничиться GET-запросами (а POST, мол, является дополнительным плюсом), у меня рука не поднимется передавать логин и пароль пользователя так, чтобы они были видны в адресной строке браузера. Так что, если в пятницу вечером я сяду, то закончу в субботу часикам к четырем. На второе задание уйдет как минимум полдня.

И в том и другом случае особого ума не требуется, это рутина. Но рутина трудоёмкая. А на выходные у меня уже имеются кое-какие планы. Во-первых, мы с Мариной собирались на концерт, в кои-то веки. Во-вторых, детям при моей занятости недостает внимания. Позавчера сижу в офисе, Марина звонит, жалуется: "...Два сапога -- пара, только что поругались и принялись кидаться друг в друга едой". В-третьих, есть пара собственных проектов, на которые катастрофически не хватает времени. Так что, увольте. Выходные -- слишком высокая цена для входного билета на собеседование.

Два случая, когда человек не откажется тратить время на такие задания:
  1. Он мечтает попасть в эту компанию. Мне самому ни разу не приходилось слышать о компании "Адептус". Но, наверное, я не в теме. Ясно, что существует она не меньше двух лет, причем -- кризисных, хороший признак. Может, программисты валят туда толпами и они выбирают лишь тех, кто готов на все лишь бы получить там место.
  2. Нет выбора. С работы уволили, деньги кончились, больше никуда не берут.
Больше ничего не приходит в голову.

PS. Кто-то метко сказал: "тестовое задание я готов выполнить за тестовую зарплату".

30 янв. 2009 г.

Краулер своими руками. Часть 12

Как работает базовая аутентификация

Наряду с аутентификацией при помощи формы, существует и более простая -- так наз. "базовая аутентификация":

  • При первой попытке зайти на сайт сервер проверяет, если среди заголовков запроса поле 'Authorization'. Если нет или там содержится неверное значение, возвращается ошибка 401.
  • Браузер открывает всплывающее окошко для ввода имени пользователя логин и пароля
  • Пользователь вводит имя и пароль, нажимает OK и браузер делает повторный запрос, вставив в заголовок запроса: Authorization: Basic данные.
  • Сервер проверяет логин с паролем и если все в порядке, возвращает запрошенную страницу с кодом 200.

Пользователей заводит администратор веб-сервера. Их имена и пароли заносятся в конфигурацию. Они могут быть зашифрованы или храниться в виде текста -- зависит от требований к безопасности.

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


В одной из заметок был продемонстрирован краулер, способный обходить сайт и проверять, все ли ссылки правильно работают. Поскольку использоваться он будет чаще всего на этапе тестирования сайтов, ему недостает умения заходить на защищенные таким способом страницы.

Базовая аутентификация и urllib2

Для базовой аутентификации средствами питоновской библиотеки urllib2 нужно использовать два встроенных класса:
  • HTTPPasswordMgr
  • HTTPBasicAuthHandler
Первый позволяет задавать имя пользователя и пароль, второй добавляется в набор handler-ов (обработчиков запроса) для специализированного экземпляра OpenDirector (см. подробности).

Простейший вариант HTTPPasswordMgr

class KnownPasswordMgr(HTTPPasswordMgr):
"""
Хранит заранее заданную пару логин/пароль
"""
def __init__(self, username, password):
HTTPPasswordMgr.__init__(self)
self.username = username
self.password = password

def find_user_password(self, realm, authuri):
"""
Возвращает заранее известную пару значений
"""
retval = HTTPPasswordMgr.find_user_password(self, realm, authuri)
if not (retval[0] or retval[1]):
return (self.username, self.password)

return retval
Этот класс рассчитан на использование одной единственной пары имя/пароль.

HTTPBasicAuthHandler

В конструктор класса UserAgent добавим необязательный параметр: credentials. Если он присутствует, к набору handler-ов будет добавлен HTTPBasicAuthHandler.

class UserAgent(object):
"""
Краулер.

Именованные аргументы конструктора и значения по умолчанию:
agentname -- имя ('Test/1.0')
email -- адрес разработчика (пустая строка)
hdrs -- словарь HTTP-заголовков (DEFAULT_HEADERS)
ignore_robots -- True, если следует игнорировать robots.txt (False)

credentials -- словарь с ключами 'логин' и 'пароль', если нужна
базовая аутентификация (None).
"""

def __init__(self,
agentname=DEFAULT_AGENTNAME,
email=DEFAULT_EMAIL,
hdrs=None,
ignore_robots=False,
credentials=None):

if not hdrs:
hdrs = {}
self.agentname = agentname
self.email = email

self.cookies_handler = SessionCookieHandler()
handlers = [ self.cookies_handler, ]
if not ignore_robots:
handlers.append(RobotsHTTPHandler(self.agentname))

if credentials:
handlers.append(
HTTPBasicAuthHandler(KnownPasswordMgr(**credentials))
)

self.opener = urllib2.build_opener(*handlers)

# переопределение заголовков по умолчанию
headers = copy(DEFAULT_HEADERS)
headers.update(hdrs)
op_headers = [ (k, v) for k, v in headers.iteritems() ]
op_headers.append(('User-Agent', self.agentname))
# если email не задан, HTTP-заголовок 'From' не нужен
if self.email:
op_headers.append(('From', self.email))

self.opener.addheaders = op_headers
Вот, собственно, и все. TestCase для новой функции может выглядеть так:

class TestAuth(unittest.TestCase):
def setUp(self):
self.crawler = crawler.UserAgent(
agentname='Mozilla/4.0 (compatible; MSIE 5.5; Windows NT)',
ignore_robots=True,
credentials = dict(username='ЛОГИН', password='ПАРОЛЬ')
)

def _on_success(self, *args):
self.assertTrue(1)

def _on_failure(self, url, err):
self.fail('Authentication failed: %s' % err)

def test_authentication(self):
self.crawler.visit('АДРЕС САЙТА',
on_success=self._on_success,
on_failure=self._on_failure )
Здесь, в отличие от авторизации через форму, в случае успешного ответа не надо дополнительно проверять содержание страницы. В случае ошибки будет возвращаться все тот же код 401, т.е. функция обратного вызова _on_success не будет вызвана.

26 янв. 2009 г.

Краулер своими руками. Часть 11

Лень как двигатель прогресса

В последнее время я пристрастился к порталу "Кинокопилка", откуда можно скачивать фильмы. Я захожу в разделы интересующих меня жанров, чтобы узнать, не появилось ли там что-нибудь интересное. Не все же время программы писать! Еще есть онлайн-библиотека технической литературы. Рассылка приходит раз в месяц, а новые книги появляются ежедневно. В отличие от "Кинокопилки", этот сайт предоставляет RSS-канал. Но среди первых заголовков, которые я вижу через программу просмотра каналов, далеко не всегда фигурируют книги по моей специальности. Так что, все равно приходится идти на сайт.

Если добавить еще пяток ежедневно просматриваемых сайтов, то процедура становится уже несколько утомительной. А кому-то необходимо отслеживать информацию, меняющуюся каждый час: наблюдать за финансовыми событиями, наличием свободных мест и объявлений... Вот почему пользуются спросом так называемые "скраперы".

Скрапер

Скрапер -- это программа, которая, по определению Википедии, специализируется на извлечении той или иной информации с веб-страниц. Во многих случаях эта информация доступна только авторизованным посетителям.

Типичный сценарий

  1. Клиент заходит на страницу, где содержится форма авторизации.
  2. Отправляет на сервер логин и пароль методом POST
  3. Сервер проверяет данные и если все правильно, создает сессию, возвращает клиенту ее уникальный код и перенаправляет его на другую страницу.
  4. Клиент открывает нужные страницы, каждый раз передавая на сервер код сессии. По этому "ярлычку" сервер будет узнавать авторизованного клиента.
  5. Сессия завершается (либо по таймеру либо клиент заходит на страницу "Выход"), сервер удаляет код сессии и все данные, которые уже неактуальны.
Нельзя ли пропустить первый шаг, сразу отправляя на сервер логин и пароль? Иногда можно, но чаще -- нет, по двум причинам:
  1. В ходе авторизации сервер может проверить наличие кода анонимной сессии. А код этот можно получить только если вначале открыть страницу сайта (читай: сделать GET-запрос). У анонимной сессии тоже имеется код, только сервер не связывает его с базой данных зарегистрированных пользователей.
  2. Многие сайты, помимо логина и пароля, проверяют еще и заголовок HTTP-запроса "Referer", ожидая увидеть там адрес страницы авторизации (а то ходят тут всякие...).
Второе ограничение можно, конечно, обойти, вбив нужный заголовок руками: "Referer: адрес страницы авторизации"-- эта бесчестная практика называется "Referer spoofing", но лучше (да и надежнее) все-таки соблюдать приличия.

Авторизация средствами urllib2

Кодом сессии клиент и сервер обычно обмениваются через механизм cookie, о котором шла речь в предыдущей заметке. Поэтому при использовании Python-библиотеки urllib2 в первую очередь надо позаботиться о том, чтобы в экземпляр OpenDirector был включен HTTPCookieProcessor. В заметке, посвященной cookies, использовался
экземпляр стандартного HTTPCookieProcessor-а. Он работает out of the box. Но если требуется расширенная функциональность -- к примеру, возможность сохранять полученные коды авторизации в файле, удобнее определить класс-наследник:

Поддержка cookies


import cookielib
from urllib2 import HTTPCookieProcessor
COOKIEFILE = '...' # путь к файлу, где хранятся cookies
class SessionCookieHandler(HTTPCookieProcessor):
"""
Загружает и сохраняет куки.
"""
def __init__(self):
cjar = cookielib.LWPCookieJar()
if os.path.isfile(COOKIEFILE):
cjar.load(COOKIEFILE)

HTTPCookieProcessor.__init__(self, cjar)

def save_cookies(self):
""" Сохранение кук"""
self.cookiejar.save(COOKIEFILE)


В код инициализации краулера (напомню, что в самом начале этого цикла заметок был создан класс UserAgent, который затем совершенствовался) следует включить такой фрагмент:


self.cookies_handler = SessionCookieHandler()
handlers = [
self.cookieshandler,
# другие нестандартные handler-ы
]
self.opener = urllib2.build_opener(*handlers)

POST-запрос

Класс urllib.Request имеет второй аргумент -- data. При непустом значении предполагается, что там содержатся параметры POST-запроса, которые выглядят примерно так: param1=value1&param2=value2... Для создания такой строки используется функция из "соседнего" пакета urllib:
import urllib # не путать с urllib2!
data = urllib.urlencode({'param1':'param1', 'param2':'value2',})

ESCAPE-последовательности и кирилица

Не проще ли создать строку параметров запроса руками? Нет, потому что функция urlencode при необходимости конвертирует строки в ESCAPE-последовательности.
from urllib import urlencode
urlencode({'name':'sergey krushinsky'})
'name=sergey+krushinsky'

Тонкость работы urlencode с кириллицей в том, что уникодные и байтовые строки возвращают разные результаты.
from urllib import urlencode, unquote
s1 = urlencode({'name':'вася'})
s2 = urlencode({'name':u'вася'})
print unquote(s1).encode('1251')
name=вася
print unquote(s2).encode('1251')
name=вася

Запрос будет выглядеть так:
req = urllib2.Request(url, post_data)
handle = self.opener.open(req, None, TIMEOUT)
...
self.self.cookies_handler.save_cookies()

Скрапер как "конечный автомат"

Скрапер удобнее всего написать, используя классическую идиому под названием "конечный автомат".

#!/usr/bin/python
# -*- coding: utf8 -*-
#########################################################################
# Scrapper
# author: Sergey Krushinsky
# created: 2009-01-25
#########################################################################
from crawler import UserAgent
from parsers import extract_text
import urllib
import logging
logging.basicConfig(
level=logging.DEBUG,
format='%(asctime)s %(levelname)-8s %(message)s',
datefmt='%Y-%m-%d %H:%M:%S',
)


class Scrapper(object):
"""
Пример авторизации на сайте 'www.kinokopilka.ru'
через POST-форму.
"""
def __init__(self):
self.crawler = UserAgent(
#agentname='Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.0.5) Gecko/2008120122 Firefox/3.0.5',
ignore_robots=True
)

# страница с формой
self.signin_url = 'http://www.kinokopilka.ru/account/signin'
# адрес, куда отправляется POST-запрос
self.login_url = 'http://www.kinokopilka.ru/account/login'
# адрес, куда сервер должен перенаправить клиента
# после авторизации
self.expected_redirect = 'http://www.kinokopilka.ru/movies'

self.form = {
'login': 'ЛОГИН',
'password': 'ПАРОЛЬ',
'remember': 'true',
'commit_login': 'Войти', # кнопка
}

# исходное стостояние "конечного автомата"
# по мере выполнения задач, значением становится очередное
# состояние.
self.state = 'signin'


def error(self):
"""
Состояние ошибки. Прекращает выполнение.
"""
logging.debug('Error state')
self.state = None

def completed(self):
"""
Состояние успешного завершения действий.
Прекращает выполнение.
"""
logging.debug('Completed')
# TODO: на практике, должно включаться следующее состояние,
# которое выполняет что-то полезное -- например, поиск
# новых фильмов
self.state = None

def login(self):
"""
Логин при помощи формы
"""
def _handle_success(url, data, info):
if (url != self.expected_redirect):
logging.error('Expected redirect to %s. Got: %s' % \
(self.expected_redirect, url))
self.state = 'error'
else:
text = extract_text(data)
# print 'text: %s' % text
# В случае успешной авторизации на странице будет приветствие:
# "Здравствуйте, имя_пользователя", где имя пользователя
# совпадает со значением 'login' в форме.
if text.find(self.form['login']) > -1:
self.state = 'completed'
else:
logging.debug('No greeting text found')
self.state = 'error'

def _handle_failure(url, err):
logging.error("Could not login: %s: %s" % (url, err))
self.state = 'error'

data = urllib.urlencode(self.form)
self.crawler.visit(self.login_url,
on_success=_handle_success,
on_failure=_handle_failure,
post_data=data)

def signin(self):
"""
Получение страницы с формой и всех cookies.
"""
def _handle_failure(url, err):
logging.error("Could not signin: %s: %s" % (url, err))
self.state = 'error'

def _handle_success(url, data, info):
self.state = 'login'

self.crawler.visit(self.signin_url,
on_success=_handle_success,
on_failure=_handle_failure)

def run(self):
"""
Главный метод "конечного автомата".
"""
while self.state:
logging.info('-' * 50)
logging.info("Entering '%s' state" % self.state)
logging.info('-' * 50)
# поиск функции, чье название соответствует состоянию.
fn = getattr(self, self.state)
fn()

if __name__ == '__main__':
Scrapper().run()



***

Должен признаться, что используя Perl и библиотеку WWW::Mechanize, я написал быстрее, чем за час, скрипт, который делает то же самое. На отладку скрапера, чей код приведен выше, пришлось потратить изрядное количество времени... не буду говорить, сколько, чтобы меня не заподозрили в непрофессионализме. При том, что для краулера имеется набор функциональных тестов. Строчек кода в питоновской версии значительно больше. ...Эй, кто там восхвалял продуктивность Питона?

Другое дело, что в Perl-версии использовалась специализированная библиотека. Справедливости ради, надо отметить, что и в Python-е имеется ее аналог под названием mechanize. Она состоит из довольно большого количества классов, которые встраиваются в urlllib2, расширяя ее возможности, а иногда подменяют существующие там классы. Но если документацию к WWW::Mechanize достаточно бегло просмотреть в течение ровно пяти минут, чтобы начать писать что-то полезное, то с этим хозяйством предстоит разбираться долго. Когда-нибудь я это обязательно сделаю. А пока лучше посмотрю фильм, полученное с "Кинокопилки"...

16 янв. 2009 г.

Краулер своими руками. Часть 10

Ярлычки на чемодане

В некоторых случаях взаимодействие клиента с сервером невозможно без обмена порциями данных, получивших поэтическое имя cookies -- "печенье". Сценарий таков:
  1. При первом обращении к серверу клиент приходит с пустыми руками. Сервер "видит" это и передает ему HTTP-заголовок "Set-Cookie:данные". В данных может быть уникальный идентификатор или какие-то настройки -- скажем, языковые.
  2. Клиент запоминает эти данные и при повторном обращении снова возвращает их серверу через заголовок "Cookie:данные".
  3. Сервер читает заголовок "Cookie" и распознает клиента.
Таким образом достигается постоянство сессии. Без этого было бы трудно, к примеру, при переходе с одной страницы интернет-магазина на другую видеть корзину покупателя в неизменном состоянии. На практике сервер часто при первом ответе "закрепляет" за клиентом куку (как ярлычок на чемодане), сразу перенаправляет его на ту же самую страницу и только после этого начинает полноценно взаимодействовать.

***
OpenDirector, который используется в библиотеке urllib2 по умолчанию, не работает с Cookie. В наборе готовых handler-ов имеется HTTPCookieProcessor, но если не подключить его руками, он не будет задействован. Подключить его можно таким образом:
import cookielib
COOKIEFILE = '...' # путь к файлу, где хранятся cookies

cookie_jar = cookielib.LWPCookieJar()
# загрузить сохраненные cookies, если файл существует
if os.path.isfile(COOKIEFILE):
cookie_jar.load(COOKIEFILE)

cookie_processor = urllib2.HTTPCookieProcessor(cookie_jar)
opener = urllib2.build_opener(cookie_processor, другие handler-ы)
Теперь библиотека urllib2 будет автоматически читать и передавать назад данные, полученные через cookies.
После выполнения запроса надо сохранить полученные cookies:
req = urllib2.Request(url, None)
...
handle = self.opener.open(req, None, TIMEOUT)
cookie_jar.save(COOKIEFILE)
Все эти операции легко включить в класс UserAgent.

Библиотека cookielib появилась в Python 2.4. До этого использовался класс ClientCookie. О том, как сделать работу с cookies независимой от версий питона, подробно рассказано в статье cookielib and ClientCookie на www.voidspace.org.uk.

13 янв. 2009 г.

Краулер своими руками. Часть 9

Пора заняться усовершенствованием краулера.

Сжатие контента

Большинство серверов умеют сжимать передаваемый контент, а браузеры, соответственно,-- разжимать. Делается это ради экономии трафика. Только вначале клиент и сервер должны договориться об этом между собой.
  • Клиент должен отправить в запросе заголовок Accept-encoding: алгоритм сжатия(например, gzip).
  • Если сервер умеет сжимать страницу указанным алгоритмом, он это сделает и вернет заголовок Content-Encoding: алгоритм сжатия.
  • Клиент проверяет заголовок Content-Encoding и если там указано сжатие, распаковывает данные.
До недавних пор распаковывать налету сжатый контент средствами питоновских библиотек было непросто. Xah Lee даже использовал официальную документацию к модулю gzip как пример неудачной документации. У меня год-два назад не получалось распаковывать сжатый web-контент, как ни старался. Но, видимо, в текущей версии недоработки были исправлены. Сейчас простой рецепт приведен в Dive Into Python.

Метод visit, добавленный в класс UserAgent, представляет собой обертку вокруг open:
...
from StringIO import StringIO
import gzip

class UserAgent(object):
...

def open(self, url, add_headers=None):
"""
Возвращает file-like object, полученный с заданного адреса.
В случае ошибки возвращает HTTPError, URLError или IOError.
"""
logging.info('Opening %s...' % url)
req = urllib2.Request(url, None)
if add_headers:
for k, v in add_headers.iteritems():
req.add_header(k, v)
handle = self.opener.open(req, None, TIMEOUT)

return handle

def gunzip(self, stream):
gz = gzip.GzipFile(fileobj=stream)
return StringIO(gz.read())

def visit(self, url, add_headers={}, on_success=None, on_failure=None):
"""
Возвращает последний пройденный URL, объект StringIO и info, полученные
с заданного адреса через callback-метод on_success.
В случае ошибки вызывает метод on_failure, передавая туда исклчение.

Фактически, это обертка вокруг open. Важное отличие в том, что
этот метод автоматически разворачивает сжатый контент.
"""
add_headers.update({'Accept-encoding': 'gzip'})
try:
r = self.open(url, add_headers)
s = StringIO(r.read())
info = r.info()
if info.get('Content-Encoding') == 'gzip':
logging.debug('Gzipped content received')
stream = self.gunzip(s)
else:
stream = s
stream.seek(0)
on_success(r.geturl(), stream, info)
except Exception, e:
on_failure(url, e)

  • старый метод open принимает дополнительные заголовки.
  • новый метод visit читает данные и "заворачивает" их в StringIO
  • результат возвращается в callback-функции on_success и on_failure.

Почему используются callback-функции?

В случае успешного запроса, могут понадобиться три результата:
  1. содержание страницы
  2. заголовки ответа
  3. адрес, с которого были получены результаты (в случае редиректов он не совпадает с исходным адресом)
Можно, конечно, вернуть список результатов, но по-моему, это не очень красиво и удобно с точки зрения поддержки. Нехорошо когда функция возвращает больше одного значения. И не всегда будут нужны сразу три результата. В последнем случае callback-функция может быть объявлена без указания лишних аргументов:
def handle_success(*args):
ctype = args[2].get('Content-Type')
...

Мне это больше нравится, чем:
results = visit(аргументы)
ctype = results[2].get('Content-Type')
Впрочем, дело вкуса...

Старый метод open теперь снаружи практически не нужен.

10 янв. 2009 г.

Краулер своими руками. Часть 8

Извлечение текста из HTML

В пятой части этой серии заметок HTML-парсер BeautifulSoup был заменен на html5lib. Справится ли новая библиотека с извлечением текста из HTML так же хорошо, как с извлечением сcылок? Ответ на этот вопрос будет критическим для всего проекта. Потому что от краулера, который умеет двигаться, но не умеет говорить, проку мало.

Поскольку парсер возвращает DOM-дерево (точнее minidom), для извлечения текста применяется тривиальный рекурсивный обход узлов:

from html5lib import treebuilders

IGNORED_ELEMENTS = ('script')

...

def build_dom(fileobj):
"""
Читает fileobj и возвращает дерево minidom.
"""
#HTMLSanitizer дает странные результаты
#parser = html5lib.HTMLParser(tree=treebuilders.getTreeBuilder('dom'),
# tokenizer=sanitizer.HTMLSanitizer)
parser = html5lib.HTMLParser(tree=treebuilders.getTreeBuilder('dom'))
return parser.parse(fileobj)


def extract_text(fileobj):
"""
Извлекает текст из HTML-страницы. Результат в кодировке utf-8.
fileobj -- файло-подобный объект.
"""
def visit(node):
if node.nodeType == node.TEXT_NODE:
return node.data.strip()
elif node.nodeType == node.ELEMENT_NODE \
and not node.tagName in IGNORED_ELEMENTS \
and node.hasChildNodes():

resulttext = ''
for child in node.childNodes:
subtext = visit(child)
if subtext:
resulttext = '%s %s' % (resulttext, subtext)
return resulttext
return None

dom = build_dom(fileobj)

text = visit(dom.getElementsByTagName('body')[0])
dom.unlink()
return text


  • DOM-дерево получается тем же способом, что и при извлечении ссылок. Поэтому я вынес парсинг в отдельную функцию 'build_dom'. Только от Sanitizer-а пришлось отказаться (см. закомментированные строки) -- с ним в результат, помимо чистого текста попадали HTML-теги, уж не знаю, почему.
  • Поиск начинается с содержимого элемента 'body'.
  • Если текущий узел -- текстовый (node.TEXT_NODE), возвращается его содержимое.
  • Если текущий узел -- элемент (node.ELEMENT_NODE), имеющий потомков и не относящийся к числу игнорируемых элементов, потомки проверяются один за другим. Текст, добытый из каждой дочерней ветки, добавляется через пробел к уже собранному тексту.
Получается одна длинная строка.
Вот простейший тест:
class TestTextExtractor(unittest.TestCase):
def setUp(self):
self.user_agent = crawler.UserAgent()

def test_utf8_source(self):
page_url = 'http://krushinsky.blogspot.com/'
fileobj = self.user_agent.open(page_url)
txt = extract_text(fileobj)
print txt
self.assertTrue(txt, 'No text was extracted from %s' % page_url)

Результаты выглядят неплохо:
Фото -субъектив четверг, Декабрь 18, 2008 Вторая Табачная Экспедиция Утром отправился в экспедицию за табаком. Шла метель, дороги стали скользкими. Я впервые познакомился с заносами. Ехал предельно осторожно, на поворотах замедлялся и страховался ногами...

Функцию извлечения текста из HTML наверняка придется еще совершенствовать, как и тесты, но главное: с этим уже можно работать.

9 янв. 2009 г.

Краулер своими руками. Часть 7

Программа для проверки ссылок, о которой впервые зашла речь в четвертой заметке, годится разве что в качестве иллюстрации. Как инструмент она бесполезна.
  • Одного перечня неработающих ссылок недостаточно; важно знать, на каких страницах сайта находятся эти ссылки, чтобы можно было внести исправления.
  • Обход сайта и проверка ссылок в первой версии -- фактически, одно и то же. Значит, нет возможности проверить работоспособность внешних ссылок и вообще всего, что отбрасывается фильтром is_valid_link.
Пускай это будет в ущерб производительности, но придется построить программу немного иначе. При успешном открытии страницы надо извлекать из нее ссылки, несмотря на то, что это уже делается один раз внутри функции traverse. А потом проверять каждую запросом HEAD.


HEAD-запрос

Сделать HEAD-запрос в Python-е проще всего средствами httplib. Библиотека urllib2 это тоже позволяет, но придется писать много лишнего кода. Функция, представленная ниже, возвращает код ответа на HTTP-запрос или 0, если соединение не состоялось. Этого достаточно, чтобы узнать, жива ли страница.
from urlparse import urlparse
import httplib

def request_head(url):
parts = urlparse(url)
conn = None
try:
conn = httplib.HTTPConnection(parts.netloc)
conn.request('HEAD', parts.path, parts.params)
return conn.getresponse().status
except:
return 0
finally:
if conn:
conn.close()

И методы, использующие эти запросы:

# если при попытке открыть ссылку возвращается один из этих кодов,
# ссылка считается неработающей
BAD_CODES = (301, 303, 307, 404, 410, 500, 501, 502, 503, 504)

for link in links_iterator(response, is_http_link ):
status = passed.setdefault(
link,
request_head(link)
)

if not status or status in BAD_CODES:
print '%s --> %s: %s ' % (url, hostname, status)
...

Выглядит неплохо. Но не работает. Корневая страница открывается, как положено, из нее извлекаются новые ссылки. После чего скрипт благополучно завершает свою работу. Обхода вглубь не происходит.

Проблема в том, что после парсинга страницы внутри callback-метода test_links из файло-подобного объекта (file-like object), который возвращает метод opener.open(), уже невозможно ничего прочесть. Первая идея, приходящая в голову: применить метод файла seek(0), чтобы вернуться в начало. Однако, вызов response.seek(0) ни к чему ни приводит, хотя Python не ругается, как непременно сделала бы Java.


Утка или не утка?

В динамических языках любят идиому: "Если нечто ходит, как утка -- значит, это утка". Именно так устроено в питоне все, что называется "file-like object", в том числе, результат urllib2.Request.open(). Однако, метод seek не работает. Если задуматься, нет ничего удивительного в том, что сокет работает иначе, чем файл. Другой вопрос: хорошо это или плохо когда нечто, что называется уткой, ходит, как положено утке, но отказывается нести яйца -- не лучше бы ее тогда назвать как-то иначе? Эта тема уже обсужалась в списке рассылки python-bugs-list. Там же был предложен рецепт: как все-таки заставить файло-подобный объект одноразового использования перематываться. Для этого достаточно прочесть данные из потока и "завернуть" их в StringIO, чтобы получить своего рода виртуальный файл.
import StringIO

response = self.open(url)
data = StringIO.StringIO(response.read())

Большая стирка

Теперь seek работает, но вместе с response исчезли и его дополнительные методы, такие как info() и geturl(). Заголовки HTTP-ответа, которые можно было получить через response.info(), уже недоступны вне traverse, поскольку в функцию обратного вызова on_success передается другой объект -- StringIO. Придется изменить функцию обратного вызова, добавив туда новый аргумент:
on_success(url, response.info(), data)
В модуль parsers.py тоже надо внести изменения. Поскольку теперь мы не можем получить базовый адрес для преобразования относительных адресов в абсолютные, используя response.geturl(), придется передавать этот адрес как аргумент:
def links_iterator(base, response, link_filter=None):
"""
Итератор по ссылкам, найденным в документе.
Аргументы:
base -- URL страницы, с которой делается запрос
response -- поток ввода
filter -- функция, которая может быть использована для
отбора нужных ссылок. На входе: url, на выходе
True, если проверка прошла, иначе -- False
Если параметр 'filter' не задан, итератор возвращает
все найденные ссылки.
"""
...
Новая версия UserAgent.traverse() выглядит так:
def traverse(self, start_url, links_filter=None, on_success=None, on_failure=None):
"""
Обход сети.

start_url -- исходный адрес
links_filter -- функция для оценки очередной ссылки, полученной со
страницы. При результате False не включается в очередь.
on_success -- callback-функция, которая вызывается при успешном
открытии страницы с аргументами (url, response)
on_failure -- callback-функция, которая вызывается в случае неудачи
с аргументами: (url, exception)
"""
queue = [ start_url ]
passed = set()
last_url = None
while queue:
logging.debug('Queue size: %d, Passed: %d ' % \
(len(queue), len(passed)) )
url = queue.pop(0)
try:
if last_url:
r = self.open(url, {'Referer': last_url})
else:
r = self.open(url)
data = StringIO(r.read())
logging.debug('Success')
if on_success:
on_success(url, r.info(), data)
# извлекаем со страницы новые ссылки и добавляем их в очередь
data.seek(0)
new_links = [
u for u in links_iterator(
url,
data,
lambda u: False if (u in passed or u in queue) \
else links_filter(u)
)
]
queue.extend(new_links)
logging.debug('Added %d new links' % len(new_links))

except Exception, ex:
logging.warn('Failure: %s' % ex)
if on_failure:
on_failure(url, ex)
finally:
last_url = url
passed.add(url)

logging.debug('Crawling completed. %d pages passed' % len(passed))


Помимо "заворачивания" результата self.open в StringIO и изменения API callback-функции on_success, есть и другие улучшения:
  1. В очередной запрос, начиная со второго, добавляется заголовок 'Referer' для имитации поведения браузера. Некорые сайты проверяют его.
  2. При извлечении ссылок со страницы вначале проверяется, не пройден ли уже адрес и нет ли его в очереди заданий и только потом, если эти условия выполняются, вызывается функция link_filter. Раньше проверка происходила в другом порядке. Поскольку неизвестно заранее, сколько ресурсов потребуются на фильтрацию, лучше сразу отсекать лишнее и не дергать link_filter лишний раз.
  3. Добавился блок finally.

5 янв. 2009 г.

Краулер своими руками. Часть 6

Нормализация ссылок

Присмотревшись к логам, я заметил странные адреса, например:
INFO Opening http://pi-code.blogspot.com/2008/12/\"http://pi-code.blogspot.com/\"
Дешевый способ преобразовывать относительные адреса в абсолютные:

u = urlparse.urldefrag( # удаление фрагмента
urlparse.urljoin(base, tag['href'], allow_fragments=False)
)[0].encode('ascii')
явно ненадежен. Пришлось писать новый вариант:

def normalize_url(base, url):
"""
Нормализация URL. Используется для преобразования относительных адресов
в абсолютные.

base -- домен (напр. 'taxonomist.tripod.com'), вторая часть результата
urlparse.urlsplit result
url -- исходный URL, может быть относительным.
"""
parts = urlparse.urlsplit(url)
defaults = ('http', base, '/', parts[3], parts[4])
norm = [ p if p else defaults[i]
for i, p in enumerate(parts) ]
url = urlparse.urlunsplit(norm)
url = urlparse.urldefrag(url)[0] # удаление фрагмента
url = url.encode('ascii') # перекодировка из уникода в ascii
return url


def links_iterator(response, link_filter=None):
"""
Итератор по ссылкам, найденным в документе.
Аргументы:
response -- file-like object, возвращаемый
при открытии страницы библиотекой urllib2
filter -- функция, которая может быть использована для
отбора нужных ссылок. На входе: url, на выходе
True, если проверка прошла, иначе -- False
Если параметр 'filter' не задан, итератор возвращает
все найденные ссылки.
"""
if not link_filter:
link_filter = lambda x: True
base = response.geturl()

parser = html5lib.HTMLParser(
tree=treebuilders.getTreeBuilder('dom'),
tokenizer=sanitizer.HTMLSanitizer)
dom = parser.parse(response)
for elem in dom.getElementsByTagName('a'):
if elem.hasAttribute('href'):
href = elem.getAttribute('href')
u = normalize_url(base, href)
if link_filter(u):
yield u

dom.unlink()

Теперь относительные адреса стали преобразовываться в абсолютные по-человечески.

"Минздрав предупреждает"

Еще один неприятный момент: при импорте html5lib Python 2.6 выдавал DeprecationWarning:
C:\Python26\lib\site-packages\html5lib-0.11.1-py2.6.egg\html5lib\
inputstream.py:367:DeprecationWarning: object.__init__() takes no parameters
Эти предупреждения Минздрава ничего, кроме раздражения не вызывают. Чтобы избавиться от них, я добавил в parsers.py следующий код:
from html5lib import treebuilders, sanitizer
import warnings
warnings.simplefilter("ignore",DeprecationWarning)

4 янв. 2009 г.

Краулер своими руками. Часть 5

В 2007 году, когда я писал краулера на Питоне для поискового проекта, именно отсутствие надежного HTML-парсера заставила меня пересесть на Perl. Ни SGMLParser ни HTMLParser из стандартных библиотек не в состоянии справиться со страницами, выходящими за рамки академического гипертекста. Альтернативная библиотека BeautifulSoup, вроде бы хорошо себя зарекомендовавшая, оказалась, как выяснилось в предыдущей заметке, ненадежной.

Прежде чем ставить вердикт, что Python -- неподходящий инструмент для написания простейшего краулера, дадим шанс еще одной библиотеке: html5lib. Прежде всего, добавим в модуль test_parsers новый тест:
class TestLinks(unittest.TestCase):
...
def test_blogspot(self):
page_url = 'http://krushinsky.blogspot.com/'
fileobj = self.user_agent.open(page_url)
test_link = 'http://krushinsky.blogspot.com/2007_12_01_archive.html'

links = [ u for u in links_iterator(fileobj, lambda u: u == test_link) ]
self.assertTrue(len(links), "Link '%s' is absent" % test_link)
...

Первой версии функции links_iterator не удавалось пройти этот тест, поскольку парсер BeautifulSoup не справлялся со страницей гугловского блога.

Альтернативная версия links_iterator опирается на парсер из библиотеки html5lib.
import urlparse
import html5lib
from html5lib import treebuilders, sanitizer

def links_iterator(response, link_filter=None):
"""
Итератор по ссылкам, найденным в документе.
Аргументы:
response -- file-like object, возвращаемый
при открытии страницы библиотекой urllib2
filter -- функция, которая может быть использована для
отбора нужных ссылок. На входе: url, на выходе
True, если проверка прошла, иначе -- False
Если параметр 'filter' не задан, итератор возвращает
все найденные ссылки.
"""
if not link_filter:
link_filter = lambda x: True
base = response.geturl()

parser = html5lib.HTMLParser(
tree=treebuilders.getTreeBuilder('dom'),
tokenizer=sanitizer.HTMLSanitizer)
dom = parser.parse(response)
for elem in dom.getElementsByTagName('a'):
if elem.hasAttribute('href'):
href = elem.getAttribute('href')
u = urlparse.urldefrag( # удаление фрагмента
urlparse.urljoin(base, href, allow_fragments=False)
)[0].encode('ascii')
if link_filter(u):
yield u

dom.unlink()

  • html5lib.HTMLParser способен возвращать разного типа деревья: minidom, elementTree и даже злополучный BeautifulSoup. Я начал с minidom-а как с простейшего варианта. Поэтому в конструкторе парсера присутствует аргумент: tree=treebuilders.getTreeBuilder('dom').
  • Второй аргумент: tokenizer=sanitizer.HTMLSanitizer предписывает использовать стандартный класс для очистки HTML от двусмысленных элементов и CSS-объявлений.
  • Чтобы получить все теги "a" применяется стандартный методы DOM: getElementsByTagName.
Тест test_blogspot выполняется. Ура! Удаляем BeautifulSoup, работаем с html5lib и продолжаем писать краулер на Питоне.

Отмечу только, что установка html5lib версии 0.11.1 из исходных кодов не проходит гладко -- по крайней мере, в среде Windows. Стандартная команда python setup.py install не перенесла библиотечные файлы в директорию site-packages, а оставила их там, где лежали исходники. Пришлось копировать их вручную.

Краулер своими руками. Часть 4

Обход сети

Ниже представлен метод краулера (UserAgent) traverse, позволяющий обходить сеть.
def traverse(self, start_url, links_filter=None, on_success=None, on_failure=None):
"""
Обход сети.

start_url -- исходный адрес
links_filter -- функция для оценки очередной ссылки, полученной со
страницы. При результате False не включается в очередь.
on_success -- callback-функция, которая вызывается при успешном
открытии страницы с аргументами (url, response)
on_failure -- callback-функция, которая вызывается в случае неудачи
с аргументами: (url, exception)
"""
queue = [ start_url ]
passed = set()
last_url = None
while queue:
logging.debug('Queue size: %d, Passed: %d ' % \
(len(queue), len(passed)) )
url = queue.pop(0)
try:
if last_url:
response = self.open(url, {'Referer': last_url})
else:
response = self.open(url)
if on_success:
on_success(url, response)
logging.debug('Success')
# извлекаем со страницы новые ссылки и добавляем их в очередь
new_links = [
u for u in links_iterator(response, links_filter)
if not u in passed and not u in queue ]
queue.extend(new_links)
except Exception, ex:
logging.warn('Failure: %s' % ex)
if on_failure:
on_failure(url, ex)
last_url = url
passed.add(url)
logging.debug('Crawling completed.')


  • Задания снимаются из "головы" очереди (queue). Сперва туда помещается исходный адрес. Затем она пополняется ссылками, извлеченными с очередной страницы.
  • Открыв очередную страницу, краулер вызывает callback-функцию on_success, передавая туда адрес, а также файло-подобный (file-like) объект, из которого можно прочесть ее содержание. Если открыть страницу не удается, вызывается другой метод обратного вызова: on_error.
  • Из текущей страницы извлекаются ссылки и помещаются в конец очереди заданий. Для их отбора применяется внешняя функция links_filter. Как и было обещано в предыдущей части, сам UserAgent не принимает решений относительно дальнейшего маршрута. Кроме того, выражение list comprehension построено таким образом, что игнорируются как пройденные ссылки, так и те, что уже имеются в очереди (...if not u in passed and not u in queue).
  • Обход завершается когда заданий не остается.
В набор тестов TestUserAgent добавляется новая функция:
def test_traverse(self):
"""
Проверяет функцию обхода сети.
"""
page_url = 'http://pi-code.blogspot.com'
hostname = urlsplit(page_url).hostname

def is_valid_link(u):
url_parts = urlsplit(u)
return False if url_parts.hostname != hostname \
else False if url_parts[0] != 'http' \
else True

passed = [] # успешно пройденные адреса
errors = [] # адреса, которые не удалось пройти

def on_success(url, response):
passed.append(url)

def on_failure(url, error):
errors.append(url)

self.crawler.traverse(
page_url,
links_filter=is_valid_link,
on_success=on_success,
on_failure=on_failure)

self.assert_(passed > 1, 'No nodes were passed')

Почему не генератор?

Я предпочел более традиционный подход с функциями обратного вызова. Можно было бы сделать traverse генератором по образцу стандартной функции для обхода директорий os.walk. Но тогда было бы сложнее с обработкой ошибок. Если в генераторе возникнет исключение, цикл остановится. Как сообщить "наверх" о том, что страницу не удалось открыть, не останавливая паука?

В os.walk для обработки ошибок может быть использована callback-функция onerror. Если она не задана в качестве аргумента, ошибки игнорируются. Но это довольно некрасиво с точки зрения архитектуры. Любой генератор -- своего рода callback наизнанку, альтернатива функциям обратного вызова. Одновременное их использование явно избыточно.

В os.walk предполагается, что в большинстве случаев ошибки не будут обрабатываться, поэтому там такой "костыль" может быть и оправдан. При использовании краулера обработка ошибок почти всегда необходима. Отрицательный результат не менее ценен, чем положительный. Ошибка регистрируется, а паучок ползет дальше.


Проверка ссылок

Пора сделать что-нибудь полезное. Попробуем приспособить краулер для решения довольно распространенной задачи: проверки "мертвых" внутренних ссылок на сайте.

Игнорирование robots.txt

Для тестирования сайта учитывать ограничения robots.txt ни к чему. В конструктор класса UserAgent стоит добавить необязательный параметр ignore_robots со значением False по умолчанию. При значении True, opener будет создаваться без RobotsHTTPHandler (cм. "Краулер своими руками, часть 2"):
class UserAgent(object):
def __init__(self,
agentname=DEFAULT_AGENTNAME,
email=DEFAULT_EMAIL,
new_headers=None,
ignore_robots=False):

...
if ignore_robots:
self.opener = urllib2.build_opener()
else:
self.opener = urllib2.build_opener(
RobotsHTTPHandler(self.agentname))
...
Любопытно, что попытка использовать метод self.opener.add_handler(RobotsHTTPHandler) ни к чему ни приводит.

Скрипт для проверки "мертвых" ссылок совсем короткий:


#!/usr/bin/python
# -*- coding: cp1251 -*-
#########################################################################
# Tool for testing site links
# author: Sergey Krushinsky
# created: 2008-12-28
#########################################################################

from urlparse import urlunparse, urlsplit
from crawler import UserAgent
import logging
logging.basicConfig(
level=logging.DEBUG,
format='%(asctime)s %(levelname)-8s %(message)s',
datefmt='%Y-%m-%d %H:%M:%S',
filename='%s.log' % __name__,
filemode='w'
)

# имитируем браузер
AGENT_NAME = "Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.0.5) Gecko/2008120122 Firefox/3.0.5"

def is_valid_link(u, hostname):
"""
Фильтрация ссылок.
"""
logging.debug("Validating link: '%s'" % u)
url_parts = urlsplit(u)
return False if url_parts.hostname != hostname \
else False if url_parts[0] != 'http' \
else True

def main(hostname):
"""
Обход хоста с целью проверки на наличие мертвых ссылок.
"""
def on_failure(url, error):
"""Вывод ошибки"""
print "%s: %s" % (url, error)

ua = UserAgent(agentname=AGENT_NAME, ignore_robots=True)
root = urlunparse(('http', hostname, '/', '', '', ''))
ua.traverse(
root,
links_filter=lambda u: is_valid_link(u, hostname),
on_failure=on_failure)


if __name__ == '__main__':
import sys
if len(sys.argv) < 2:
print 'Usage: python deadlinks.py HOSTNAME'
sys.exit(1)
main(sys.argv[1])

Первым делом я напустил этот скрипт на собственный блог krushinsky.blogspot.com. И очень удивился когда увидел, что краулер прошел всего 7 страниц -- это в блоге, который ведется с лета 2007 года. В число ссылок, извлеченных со страницы, не попала ни одна архивная.

Как выяснилось в ходе тестов, часть ссылок BeautifulSoup просто молча игнорировал! Когда я попытался вместо того, чтобы использовать SoupStrainer (см. часть 3), парсить весь HTML, а потом методом find_all искать нужные теги, как описано в документации, парсер просто начал умирать. Гугловский шаблон оказался ему не по зубам.