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 сек.: рекурсия

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

Краулер своими руками. Часть 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 искать нужные теги, как описано в документации, парсер просто начал умирать. Гугловский шаблон оказался ему не по зубам.