Исправить выполнение моих gotoutines

Question

Фон: Я пытаюсь реализовать логику, которая находит наименьшее положительное число, которое равномерно делится на все числа от 1 до 20. Я реализовал последовательную версию и получил ответ as 232792560.

Вопрос: Когда я пытаюсь создать некоторый параллелизм по этой проблеме (см. незакомментированный блок кода), он запускается, но никогда не показывает никакого результата. Может ли кто-нибудь из вас вести меня туда, где я ошибаюсь?

Примечание: Я очень знаком с голангом; и я знаю, что это не самая лучшая проблема для параллелизма, поскольку нет гарантии, что у меня будет наименьшее положительное число в качестве первого результата. Однако я попробовал это из своего любопытства.

package main 

    import(
     "fmt" 
    ) 

    func divide(num int) bool { 
     for i := 1; i <= 20; i++ { 
      if num % i != 0 { 
       return false 
      } 
     } 
     return true 
    } 

    func main() { 
     num:=0 
     //simple function 
     /*for { 
      num++; 
      result := divide(num) 
       if result { 
        fmt.Println("Smallest number is: ", num) 
        break 
       } 
      }*/ 


     //go-routine 
     //go-routine 
    var wg sync.WaitGroup 
    for { 
     num++; 
     wg.Add(1) 
     go func(x int) { 
      result := divide(x) 
      if result { 
       fmt.Println("Smallest number is: ", x) 
       defer wg.Done() 
      } 

     }(num) 

    } 
    wg.Wait() 
    fmt.Println("End.") 

} 

Answer 1

Это не имеет смысла запускать неограниченное количество goroutines - это будет выступать хуже, чем без одновременного решения. Вы можете попытаться использовать шаблон рабочего пула и выполнить вычисления.

package main 

import (
    "fmt" 
    "runtime" 
) 

func divide(num int) bool { 
    for i := 1; i <= 20; i++ { 
     if num%i != 0 { 
      return false 
     } 
    } 
    return true 
} 

const step = 100000 

func main() { 
    result := make(chan int) 
    jobs := make(chan int) 
    for w := 0; w < runtime.NumCPU(); w++ { 
     go func() { 
      for n := range jobs { 
       for i := n; i < n+step; i++ { 
        if divide(i) { 
         result <- i 
        } 
       } 
      } 
     }() 
    } 
    num := 1 
    for { 
     select { 
     case jobs <- num: 
      num += step 
     case x := <-result: 
      fmt.Println("Smallest number is:", x) 
      return 
     } 
    } 
} 

Answer 2

Другой подход к вашей проблеме - это фильтры. Идея состоит в том, чтобы связать кучу goroutines с каналами и заставить их фильтровать все значения, которые не проходят какой-либо тест. В вашем случае вы хотите отфильтровать числа, которые не равномерно делятся на некоторое число. Вот как это выглядит:

package main 

import (
    "fmt" 
) 

func main() { 
    in := make(chan int) 
    tmp := in 
    // Create filter-goroutines 
    for i := 1; i <= 20; i++ { 
     tmp = makeDivisor(i, tmp) 
    } 

    running := true 

    // Now feed in all the numbers... 
    for i := 1; running; i++ { 
     select { 

     // Check if a number passed all filters. 
     case k := <-tmp: 
      fmt.Printf("Answer is %d\n", k) 
      close(in) 
      running = false 

     // Otherwise feed in the next. 
     case in <- i: 
     } 
    } 

} 

func makeDivisor(n int, c chan int) chan int { 
    cc := make(chan int) 
    go func() { 
     for i := range c { 
      if i%n == 0 { 
       cc <- i 
      } 
     } 
     close(cc) 
    }() 
    return cc 
} 

Здесь он находится на playground. (Обратите внимание, что игровая площадка не будет работать с 20 фильтрами, но попробуйте также локально).

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

Это работает?

Ответ 232792560

Да.