Запрещённое (в Северной Корее, по крайней мере)

[migmit]

Поистине, Go — шикарный язык программирования. У него настолько нет недостатков, что его создатели, не зная, что ещё усовершенствовать, решили сделать для него специальные новые шрифты. А что? Хорошим программам — хорошее оформление:

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

package main
import "fmt"
import "os"
import "strconv"
func Generate(ch chan<- int) {
        for i := 2; ; i++ {
                ch <- i
        }
}
func Filter(in <-chan int, out chan<- int, prime int) {
        for {
                i := <-in
                if i%prime != 0 {
                        out <- i
                }
        }
}
func main() {
        c := 0
        n, _ := strconv.Atoi(os.Args[1])
        ch := make(chan int)
        go Generate(ch)
        prime := <-ch
        for prime <= n {
                c++
                ch1 := make(chan int)
                go Filter(ch, ch1, prime)
                ch = ch1
                prime = <-ch
        }
        fmt.Println(c)
}

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

Запускаем:

$ gccgo -g -o primes primes.go
$ ./primes 10
4

И правда, простых чисел до 10 всего четыре: 2, 3, 5 и 7. Ура!

Пробуем ещё:

$ ./primes 100
25

И правда. Ещё:

$ ./primes 100000

Не понял, висим, что ли?

Ждём.

Ждём.

А, вот:

9592

Долго что-то. Ну, дело такое, простые числа считаются нелегко. Не то, чтобы для них формула была, правда?

А главное, программу так легко распараллелить! Просто написали go — и готово! Программа тривиальным образом делается быстрее во сколько хошь раз! Вот, для сравнения, однопоточная, классическая версия:

package main
import "fmt"
import "os"
import "strconv"
func main() {
        n, _ := strconv.Atoi(os.Args[1])
        sieve := make([]bool, n-1)
        c := 0
        for p, b := range sieve {
                if !b {
                        c++
                        for i := 2; i <= n / (p+2); i++ {
                                sieve[i*(p+2)-2] = true
                        }
                }
        }
        fmt.Println(c)
}

Покороче, но зато ни разу не распараллеливается, все эти циклы выполняются итерация за итерацией — ужас. Вот, смотрите:

$ gccgo -g -o slowPrimes slowPrimes.go
$ ./slowPrimes 100000
9592

Не понял.

$ time ./primes 100000; time ./slowPrimes 100000
9592

real	3m20.962s
user	2m36.270s
sys	0m44.936s
9592

real	0m0.047s
user	0m0.028s
sys	0m0.020s

Ого.

Хотя вообще, понятно, тест нечестный. Там же куча накладных расходов — создание всех этих тредов, каналов, пересылка сообщений через них... Ясно, что на подобном синтетическом примере они будут играть основную роль. Давайте введём их в нашу «классическую» версию: будем создавать по дополнительному потоку на каждый чих (точнее, на каждое простое число), а числа будем не тупо отмечать в массиве, а пересылать в сообщениях. И оставим всё однопоточным: каждый поток, породив ещё один, будет тупо ждать, пока тот завершится:

package main
import "fmt"
import "os"
import "strconv"

type SieveCommand interface {
        perform(sieve []bool, top int)
}

type Cross struct {
        number int
}

func (c Cross) perform(sieve []bool, top int) {
        sieve[c.number-2] = true
}

func cross(number int, sieveCommands chan<- SieveCommand) {
        sieveCommands <- Cross{number: number}
}

type Lookup struct {
        from int
        result chan<- int
}

func (l Lookup) perform(sieve []bool, top int) {
        for p := l.from; p <= top; p++ {
                if !sieve[p-2] {
                        l.result <- p
                        return
                }
        }
        l.result <- 0
}

func lookup(from int, sieveCommands chan<- SieveCommand) int {
        result := make(chan int)
        sieveCommands <- Lookup{from: from, result: result}
        return <-result
}

func Sieve(sieve []bool, top int, commands <-chan SieveCommand) {
        for {
                command := <-commands
                command.perform(sieve, top)
        }
}

func OnPrime(prime int, top int, sieveCommands chan<- SieveCommand, result chan<- int) {
        for n := 2*prime; n <= top; n += prime {
                cross(n, sieveCommands)
        }
        p := lookup(prime+1, sieveCommands)
        if p == 0 {
                result <- 1
        } else {
                subResult := make(chan int)
                go OnPrime(p, top, sieveCommands, subResult)
                r := <-subResult
                result <- r+1
        }
}

func main() {
        n, _ := strconv.Atoi(os.Args[1])
        sieve := make([]bool, n-1)
        sieveCommands := make(chan SieveCommand)
        go Sieve(sieve, n, sieveCommands)
        result := make(chan int)
        go OnPrime(2, n, sieveCommands, result)
        r := <-result
        fmt.Println(r)
}

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

$ gccgo -g -o verySlowPrimes Dropbox/verySlowPrimes.go 
$ time ./verySlowPrimes 100000
9592

real	0m2.186s
user	0m1.000s
sys	0m1.174s

М-дя. Помедленне, конечно, но как-то не получаются те три минуты, которые были в исходном варианте.

Ладно, хорош издеваться. В Северной Корее запрещён сарказм, но мы-то, слава Монстру, не в Северной Корее (если вы таки в Северной Корее, то могу вас только поздравить с тем, что вам удалось вылезти в интернет). Если коротко, то: нефиг было лекции прогуливать. В варианте от авторов Go каждое простое число мы проверяем на делимость на каждое меньшее простое число. Что всего в два раза меньше, чем если бы мы проверяли каждое простое число на каждое простое число — а это, по сути, все пары простых чисел, что означает (количество простых чисел)² операций сравнения. Простых чисел, меньших n, всего около n / ln n (гуглить по словам «асимптотика простых чисел»), так что получается n2 / (ln n)2 — почти что квадратичное количество операций.

А вот классическое решето Эратосфена (второй или третий вариант) работает гораздо быстрее: для каждого простого числа p вычёркиваются примерно n / p чисел — то есть, всего количество операций будет n * (1/2 + 1/3 + 1/5 + 1/7 + ...). Это можно ОЧЕНЬ ГРУБО оценить сверху как n * (1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n) (просто добавив слагаемых), а это, в свою очередь — как n * (1/1 + (1/2 + 1/2) + (1/4 + 1/4 + 1/4 + 1/4) + ...) — каждая из внутренних скобок равна единице, а их количество — log2n, то есть получается максимум n * log2n операций. На самом деле, оценка слишком грубая, и правильный ответ будет n * ln(ln n) — но и так хорошо, почти линейная зависимость.

Мораль. Книжки надо читать и мозги развивать, а не шрифты для своего недоязычка программирования придумывать.

Comments

Запрещённое (в Северной Корее, по крайней мере)

[livejournal.livejournal.com]

User gineer referenced to your post from Запрещённое (в Северной Корее, по крайней мере) (http://gineer.livejournal.com/5895267.html) saying: [...] Originally posted by at Запрещённое (в Северной Корее, по крайней мере) [...]

[yatur.livejournal.com]

Злой ты. С одной стороны ты, конечно, прав. С другой стороны - это же пример программы для изучающих язык, а не учебник по теории алгоритмов.
Ты им, кстати, написал, чтобы исправили? Или там некуда писать?

[migmit.livejournal.com]

Там нет комментов. Может, какой-то контакт и есть, но мне лениво. Да и потом — они ж наверняка это же и скажут, «это пример для иллюстрации, а не учебник».