Добежать до парикмахера

Указатели

Письмо с предложением удаленной работы на американскую компанию за неплохие деньги пришло с бесплатного почтового ящика. Девушка, представившаяся приглашенным HR-ом, не указала своего контактного телефонного номера. Все это настораживало. Мне предлагали решить тестовое задание, после чего "... если все Ок, назначим интервью по скайпу с Техническим директором компании". Про компанию было сказано, что ее основатель — бывший техдиректор Гугла. Название ее совпадало с популярной маркой подсолнечного масла 1. Внушительно!

Обычно я отказываюсь писать тесты для незнакомцев, тем более если это займет больше пары часов. Как метко выразился кто-то из коллег, "тестовое задание я готов выполнить за тестовую зарплату". Но задачка казалась интересной, упускать шанс, пусть и небольшой, не хотелось, наконец, не мешало размять мозги перед серией собеседований на предстоящей неделе (я уже успел в одном месте опозориться, не решив на невыспавшуюся голову и голодный желудок простейшую алгоритмическую задачку). Так что, в субботу я взялся за дело, а результат отправил в воскресенье днем. Но не на бесплатный почтовый ящик, а на Гитхаб — на случай, если возникнут вопросы с авторством.

Задание

Задание было изложено на смешанном русско-английском.

"Сайт может быть представлен как ориентированный граф, где вершинами являются страницы, а ребрами — переходы между ними, при наличии ссылки с одной страницы на другую".2

Требовалось написать два скрипта.

  1. Первый обходит сайт, начиная с заданного адреса, собирает с очередной страницы внутренние ссылки3, затем идет вглубь по каждой из них, собирает новые ссылки и так далее, до заданного уровня (глубины). Цель — создать карту пройденного маршрута и сохранить ее.

  2. Второй скрипт считывает сохраненные данные, строит граф и находит его
    диаметр. Так в теории графов называется самый длинный из кратчайших маршрутов (подробности ниже).

Маршруты на местности

Граф удобно представить как план местности, где адреса — это вершины, а дороги — ребра. Допустим, мне нужно дойти от дома до парикмахерской, находящейся на другом конце квартала. Способов много. Но когда я тороплюсь, приходится выбирать самую короткую дорогу, иначе я рискую опоздать, чего парикмахер Лена очень не любит. То же самое с маршрутом от подъезда до остановки, из продуктового магазина в парикмахерскую и так далее. Из нескольких маршрутов почти всегда можно выбрать самый короткий. Если сравнить все кратчайшие пути по моему кварталу, то самый длинный из них и будет считаться диаметром.

Важный момент: расстояние определяется количеством пройденных участков. Путь A - B - C длиннее, чем D - E, пускай даже в первом случае речь идет о трех соседних домах, а во втором — о полете на Луну. Если бы мы оценивали путь, учитывая такие факторы, как километраж, пробки, ямы, орочьи патрули — это был бы уже т.наз. взвешенный граф. Навигаторы работают, конечно же, с последним. С другой стороны, измерять расстояния в рамках сайта удобнее количеством кликов.

Граф на основе словаря

Простейший способ представить граф средствами Python-а — словарь (dict), где каждый ключ служит вершиной, а его значения — это список "соседей"". Вот пример неориентированного графа:

{
    'A' : ['D', 'F'],
    'B' : ['C'],
    'C' : ['B', 'D', 'E'],
    'D' : ['A', 'C', 'E'],
    'E' : ['C', 'D', 'F'],
    'F' : ['A', 'E']
}

Здесь движение "двустороннее". Скажем, из A можно проследовать в D, а из D — обратно в A.

Неориентированный граф

В ориентированном графе каждая дорога ведет в один конец:

{
    'A' : ['D', 'F'],
    'B' : ['C'],
    'C' : ['E'],
    'D' : ['C', 'E'],
    'E' : ['F'],
    'F' : []
}

Ориентированный граф

Сравнив два рисунка, несложно заметить, что ходов в первом куда больше, чем во втором. Имея дело с ориентированным графом, можно запросто попасть в безвыходную ситуацию. Остерегайтесь пункта F — это тупик, оттуда не выбраться! А кто вышел из B, обратно уже не вернется.

Класс SimpleGraph (см. исходный код на Гитхабе) хранит структуру графа в словаре и предоставляет несколько базовых методов для работы с ним. Например, property edges возвращает список ребер в виде кортежей. Метод find_all_paths позволяет определить все маршруты из одного пункта в другой.

В реальной жизни для работы с графом я бы воспользовался библиотекой NetworkX. Но для прототипа хватит и собственного класса.

Поиском диаметра занимается отдельный модуль, sitewalker.diameter.py.

В путь!

Безымянный автор задания советовал для обхода сайта воспользоваться фреймворком Scrappy. Я решил, что раз требований к производительности нет, хватит библиотеки requests. Усложнять код очередями и многозадачностью не хотелось, поэтому я ограничился несложной рекурсивной функцией

def f(url, callback=None, level=0, parent=None):
    if level == depth:
        return
    logging.debug('Visiting %s...', url)
    try:
        resp = make_request(url, session)
        soup = Soup(resp.text, 'lxml')
    except (RequestException, AssertionError) as ex:
        logging.warning(ex)
    else:
        if level > 0:
            callback(parent, url)

        for link in iter_links(soup, domain, filter=lambda x: belongs_to_domain(x, domain)):
            if link in passed or link == url:
                continue
            f(link, callback, level+1, parent=url)
            passed.add(url)
        time.sleep(DELAY)

Эта функция представляет собой closure, возврашаемую "фабрикой" traverse_function(start_url, depth=None). Некоторые переменные, например, session, domain, passed, объявлены в родительском пространстве (scope). Исходный код расскажет больше, чем пояснения. Никаких новых техник, о которых я не писал в предыдущих заметках, тут нет. Остановлюсь лишь на нескольких ключевых моментах.

  • Функция iter_links представляет собой итератор по ссылкам, найденнным на странице средствами BeautifulSoup.

  • Параметр callback — это внешняя функция, отвечающая за построение словаря, который по завершении обхода сайта сохраняется как JSON-файл.

  • Функция belongs_to_domain определяет, принадлежит ли ссылка заданному домену. Имя хранится в переменной domain.

  • В переменной passed хранится множество (set) пройденных адресов, что позволяет избежать циклов.

Наивные предположения

Идея представить сайт в виде ориентированного графа показалось мне несколько искусственной:

  • Cсылка — не единственный способ попасть с одной страницы на другую. Кнопка бразера "назад" всегда вернет посетителя на предыдущую страницу, следовательно, движение всегда двустороннее.

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

Другие допущения

  • Адреса, принадлежающе к общему домену, принадлежат одному сайту. В большинстве случаев так и есть, но раньше, когда виртуальный хостинг стоил дороже, главная страница нередко открывалась при переходе в одну из директорий в рамках общего для всех сайтов домена. Что-то вроде example.com/~sergey.

  • Разные домены определяют разные сайты. То есть, weather.yandex.ru и tv.yandex.ru программа распознает как разные сайты, с чем можно и не согласиться.

  • Префикс www. не играет роли. Так, www.python.org — совершенно то же самое, что python.org. В большинстве случаев так и есть, но никто не запрещает веб-мастеру настроить свое хозяйство по-другому.

  • Параметры запроса не определяют страницу. Скажем, http://example.com/ и http://example.com/?foo=bar ведут в одно и то же место. Такой подход, как правило, работает, но я знаю по крайней мере один web-фреймворк, популярный лет десять тому назад, где именно параметр запроса определял контент. Так, запросы http://example.com?r=1 и http://example.com?r=2 вели на совершенно разные страницы.

Годится ли программа, построенная на таких допущениях, для реальной жизни?— заранее не скажешь. Правила диктуются целью; если она абстрактна, то и решение приблизительно.

Эпилог

Ответа от заказчика я так и не дождался. Может, мой скромный труд помог кому-то написать курсовую или даже пройти интервью? Как бы то ни было, я не считаю, что потратил время даром. Полезно было размять мозги в промежутке между неравной борьбой с фреймворками на основной работе. А еще я давно искал повод сюда написать.


  1. Я конечно же, имею в виду Altera. Очень рекомендую для приготовления оладьев. 

  2. Ориентированный граф можно проилюстрировать городом, где на каждой улице одностороннее движение. Из пункта A можно попасть в пункт B, а обратно — лишь окольным путем. 

  3. То есть, ссылки, ведущие на другие страницы того же сайта, вовнутрь, а не наружу, на другие сайты. 

social

Яндекс.Метрика