вторник, 16 июля 2013 г.

[prog] Мое решение упражнения Web Crawler из A Tour of Go

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

Прежде чем что-то писать, язык Go нужно сначала выучить. Начал изучение с A Tour of Go. Вещь прикольная, но в процессе накапливаются некоторые вопросы и недопонимание. Надеюсь, что ответы найдутся по ходу чтения более серьезных материалов.

Вчера добрался до упражнения Web Crawler. Его смысл в том, чтобы модифицировать некую функцию Crawl так, чтобы:

  • один и тот же URL дважды не обрабатывался;
  • обработка URL велась в параллель.

Собственно, вот полное условие задачи:

In this exercise you'll use Go's concurrency features to parallelize a web crawler. Modify the Crawl function to fetch URLs in parallel without fetching the same URL twice.

И все описание. А вот исходный код этой функции:

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher) {
    // TODO: Fetch URLs in parallel.
    // TODO: Don't fetch the same URL twice.
    // This implementation doesn't do either:
    if depth <= 0 {
        return
    }
    body, urls, err := fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        Crawl(u, depth-1, fetcher)
    }
    return
}

Честно признаюсь, впал в ступор. Поскольку для меня было очевидно, что если сохранять рекурсивную природу Crawl, да еще допускать ее запуск в разных потоках (goroutine-ах), то нельзя обойтись без общей структуры данных (вроде map-а), доступ к которой нужно синхронизировать. А из примитивов синхронизации в Tour of Go описывались только каналы. Еще одна загвоздка была в том, чтобы контролировать моменты завершения параллельных вызовов Crawl. Ведь об этом в Tour of Go ничего не говорилось, а простейший эксперимент показал, что функция main спокойно себе завершается не дожидаясь работы запущенных потоков.

В общем, с одной стороны было понятно, что при решении задачи нужно ограничится только теми средствами языка, которые были описаны в Tour of Go. С другой стороны, совершенно непонятно было, как сохранить рекурсивный принцип работы Crawl. В итоге, решил сделать паузу до сегодняшнего дня.

Сегодня, на свежую голову, решил отказаться от сохранения рекурсии в Crawl. Crawl превращается в менеджера, который запускает обход конкретных URL в параллель посредством простой нерекурсивной функции fetchUrl. Для обмена результатами работы используются Go-щные каналы. Более того, если вчера мне казалось, что потребуется несколько информационных каналов, то сегодня стало очевидно, что достаточно только одного, через который fetchUrl будут сообщать Crawl-у о результате обработки URL-а. В общем, где-то за час-полтора удалось переписать пример, скомпилировать его и убедится, что полученное решение вроде бы работает.

После чего погуглил аналогичные решения. С ходу нашлось три: #1, #2, #3 (наверняка их больше). Мне кажется, что мое не хуже :)

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

Свои же впечатления от языка Go пока описывать не стану, еще рано, нужно поднабраться опыта.

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

И таки да, это моя первая программа на Go :)

package main

import (
    "fmt"
)

type Fetcher interface {
    // Fetch returns the body of URL and
    // a slice of URLs found on that page.
    Fetch(url string) (body string, urls []string, err error)
}

func Crawl(url string, depth int, fetcher Fetcher) {
   results := make(chan fetchResult)

   processedUrls := map[string]bool {url: true}
   fetcherCount := 1

   go fetchUrl(url, depth, fetcher, results)

   for fetcherCount != 0 {
      r := <-results
      fetcherCount--

      fmt.Println("Handling fetch results...")

      for _, nextUrl := range r.Urls {
         if processedUrls[nextUrl] {
            fmt.Printf("URL already processed: %s\n", nextUrl)
         } else {
            processedUrls[nextUrl] = true
            fetcherCount++

            go fetchUrl(nextUrl, r.Depth - 1, fetcher, results)
         }
      }
   }
}

func main() {
    Crawl("http://golang.org/"4, fetcher)
}

type fetchResult struct {
   Urls []string
   Depth int
}

func fetchUrl(
      url string,
      depth int,
      fecther Fetcher,
      resultChannel chan fetchResult) {
   fmt.Printf("Processing '%s'(%d)...\n", url, depth)

   result := fetchResult{Depth: depth}

    if depth > 0 {
       body, urls, err := fetcher.Fetch(url)
       if err != nil {
           fmt.Println(err)
       } else {
          fmt.Printf("found: %s %q\n", url, body)

          result.Urls = urls
       }
    }

    resultChannel <- result
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f *fakeFetcher) Fetch(url string) (string, []stringerror) {
    if res, ok := (*f)[url]; ok {
        return res.body, res.urls, nil
    }
    return ""nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = &fakeFetcher{
    "http://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "http://golang.org/pkg/",
            "http://golang.org/cmd/",
        },
    },
    "http://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "http://golang.org/",
            "http://golang.org/cmd/",
            "http://golang.org/pkg/fmt/",
            "http://golang.org/pkg/os/",
        },
    },
    "http://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
    "http://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
}

Комментариев нет: