Rekurencyjne Goroutines, jaki jest najlepszy sposób, aby powiedzieć Go, aby przestał czytać z kanału?

Question

Chcę poznać idiomatyczny sposób rozwiązania tego problemu (który obecnie powoduje błąd zakleszczenia), rekursja rozgałęzia się nieznaną liczbę razy, więc nie mogę po prostu zamknąć kanału.

http://play.golang.org/p/avLf_sQJj_

Zrobiłem to działa, przekazując wskaźnik do numeru i zwiększając ją i szukałem w użyciu waitgroups Sync. Nie czułem (i mogę się mylić), że wymyśliłem eleganckie rozwiązanie. Przykłady Go, które widziałem, wydają się być proste, sprytne i zwięzłe.

To ostatni ćwiczenia z Tour Go https://tour.golang.org/#73

Czy wiesz „jak programista Go” będzie zarządzać tym? Każda pomoc będzie doceniona. Od samego początku staram się dobrze uczyć.

Answer 1

Zamiast obejmować sync.WaitGroup, można rozszerzyć wynik wysyłania na sparsowany adres URL i podać liczbę nowych znalezionych adresów URL. W głównej pętli będziesz dalej czytał wyniki, o ile będzie coś do zebrania.

W twoim przypadku liczba znalezionych adresów URL byłaby liczbą uruchomionych procedur go, ale niekoniecznie musi być. Osobiście odrodziłem mniej lub bardziej ustaloną liczbę procedur pobierania, więc nie otwierasz zbyt wielu żądań HTTP (lub przynajmniej masz nad nim kontrolę). Twoja główna pętla nie zmieniłaby się wtedy, ponieważ nie obchodzi ją, w jaki sposób wykonywane jest pobieranie. Ważnym faktem jest to, że musisz wysłać wynik lub błąd dla każdego adresu URL - zmodyfikowałem tutaj kod, więc nie odradza się nowych procedur, gdy głębokość jest już 1.

Efekt uboczny rozwiązaniem jest to, że możesz łatwo wydrukować postęp w głównej pętli.

Oto przykład na placu zabaw:

http://play.golang.org/p/BRlUc6bojf

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) 
} 

type Res struct { 
    url string 
    body string 
    found int // Number of new urls found 
} 

// Crawl uses fetcher to recursively crawl 
// pages starting with url, to a maximum of depth. 
func Crawl(url string, depth int, fetcher Fetcher, ch chan Res, errs chan error, visited map[string]bool) { 
    body, urls, err := fetcher.Fetch(url) 
    visited[url] = true 
    if err != nil { 
     errs <- err 
     return 
    } 

    newUrls := 0  
    if depth > 1 { 
     for _, u := range urls { 
      if !visited[u] { 
       newUrls++ 
       go Crawl(u, depth-1, fetcher, ch, errs, visited) 
      } 
     } 
    } 

    // Send the result along with number of urls to be fetched 
    ch <- Res{url, body, newUrls} 

    return 
} 

func main() { 
    ch := make(chan Res) 
    errs := make(chan error) 
    visited := map[string]bool{} 
    go Crawl("http://golang.org/", 4, fetcher, ch, errs, visited) 
    tocollect := 1 
    for n := 0; n < tocollect; n++ { 
     select { 
     case s := <-ch: 
      fmt.Printf("found: %s %q\n", s.url, s.body) 
      tocollect += s.found 
     case e := <-errs: 
      fmt.Println(e) 
     } 
    } 

} 

// 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, []string, error) { 
    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/", 
     }, 
    }, 
} 

I tak, wykonaj @jimt porady i uczynić dostęp do mapy bezpieczny wątku.

Answer 2

Oto moja interpretacja ćwiczenia. Jest wielu takich, ale to jest moje. Używam sync.WaitGroup i niestandardowej mapy chronionej muteksem do przechowywania odwiedzonych adresów URL. Głównie dlatego, że typ Go to standard map nie jest bezpieczny dla wątków. Łączę również kanały danych i błędów w jedną strukturę, która ma metodę odczytu tych kanałów. Głównie dla oddzielenia obaw i (prawdopodobnie) utrzymywania rzeczy nieco czystszych.

Przykład on playground:

package main 

import (
    "fmt" 
    "sync" 
) 

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) 
} 

// Crawl uses fetcher to recursively crawl 
// pages starting with url, to a maximum of depth. 
func Crawl(wg *sync.WaitGroup, url string, depth int, fetcher Fetcher, cache *UrlCache, results *Results) { 
    defer wg.Done() 

    if depth <= 0 || !cache.AtomicSet(url) { 
     return 
    } 

    body, urls, err := fetcher.Fetch(url) 
    if err != nil { 
     results.Error <- err 
     return 
    } 

    results.Data <- [2]string{url, body} 

    for _, url := range urls { 
     wg.Add(1) 
     go Crawl(wg, url, depth-1, fetcher, cache, results) 
    } 
} 

func main() { 
    var wg sync.WaitGroup 
    cache := NewUrlCache() 

    results := NewResults() 
    defer results.Close() 

    wg.Add(1) 
    go Crawl(&wg, "http://golang.org/", 4, fetcher, cache, results) 
    go results.Read() 
    wg.Wait() 
} 

// Results defines channels which yield results for a single crawled URL. 
type Results struct { 
    Data chan [2]string // url + body. 
    Error chan error  // Possible fetcher error. 
} 

func NewResults() *Results { 
    return &Results{ 
     Data: make(chan [2]string, 1), 
     Error: make(chan error, 1), 
    } 
} 

func (r *Results) Close() error { 
    close(r.Data) 
    close(r.Error) 
    return nil 
} 

// Read reads crawled results or errors, for as long as the channels are open. 
func (r *Results) Read() { 
    for { 
     select { 
     case data := <-r.Data: 
      fmt.Println(">", data) 

     case err := <-r.Error: 
      fmt.Println("e", err) 
     } 
    } 
} 

// UrlCache defines a cache of URL's we've already visited. 
type UrlCache struct { 
    sync.Mutex 
    data map[string]struct{} // Empty struct occupies 0 bytes, whereas bool takes 1 bytes. 
} 

func NewUrlCache() *UrlCache { return &UrlCache{data: make(map[string]struct{})} } 

// AtomicSet sets the given url in the cache and returns false if it already existed. 
// 
// All within the same locked context. Modifying a map without synchronisation is not safe 
// when done from multiple goroutines. Doing a Exists() check and Set() separately will 
// create a race condition, so we must combine both in a single operation. 
func (c *UrlCache) AtomicSet(url string) bool { 
    c.Lock() 
    _, ok := c.data[url] 
    c.data[url] = struct{}{} 
    c.Unlock() 
    return !ok 
} 

// 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, []string, error) { 
    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/", 
     }, 
    }, 
} 

ten nie został przetestowany, więc być może istnieją optymalizacje i poprawki, które mogą być stosowane, ale powinien przynajmniej dać Ci kilka pomysłów.