Идеальная алгоритмическая секция на Golang (ИМХО)

Привет, Хабр! А вы любите на собеседованиях проходить алгоритмические секции? А лайв-кодинг? Задачки такие «интересные», что на код-ревью такого бы умельца — тряпками и бранными словами. Минимум…., но коллега же. Поэтому просто попросим переделать.

Решать задачки под присмотром пары, а то и десятка глаз, смотрящих на тебя. И в них далеко не страх, как в известной песне, а боль и разочарование. Вроде и резюме, и опыт релевантный, а задачу дали абсурдную, которую на проекте никогда решать не придется.

Я очень плохо прохожу любые экзамены. Почти всегда иду не в ногу. И мне всегда казалось, что в этом процессе есть что-то неправильное. В компаниях типа Яндекса или Гугла, когда требуется набрать инженеров-программистов, причем неизвестно, на каком языке и проекте они будут работать, еще хотя бы понятно, зачем это нужно. А что делать в обычных компаниях? Где нужно писать CRUD’ы и настраивать межсерверное взаимодействие? Мне кажется, это неестественно.

Но однажды, объясняя дочери, что такое простые числа, я придумал идеальную алгоритмическую секцию для Go-разработчика. Примерно за час набросал задачу (как раз стандартное время на алгосекцию). Интересно? Добро пожаловать под кат!

Итак, сегодня мы попробуем совместно пройти идеальный АлгоСобес. У нас сегодня будет:

1. Банальный вариант реализации

2. Алгоритмический вариант реализации

3. GOрутинный (или многопоточный)

4. И задача со звездочкой.

Реализуем банальным способом.

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

func isPrime(n uint64, primes []uint64) bool { for _, p := range primes { if p*p > n { break } if n%p == 0 { return false } } return true }

Просто сделаем функцию, которая проверяет на простое число наше число и массив простых чисел.

Посмотрим, сколько времени потребуется для какого то большого расчета.

Простых чисел от 2 до :1000000000 — 50847534 шт.
Время выполнения: 3m19.523102917s

package main  import ( "fmt" "time" )  func isPrime(n uint64, primes []uint64) bool { for _, p := range primes { if p*p > n { break } if n%p == 0 { return false } } return true }  const maxCounter = 1_000_000_000  func main() { start := time.Now() primes := []uint64{}  i := uint64(2) for i = 2; i <= maxCounter; i++ { if isPrime(i, primes) { primes = append(primes, i) } }  fmt.Printf("Простых чисел от 2 до :%v - %v шт.\n", maxCounter, len(primes)) fmt.Printf("Время выполнения: %s\n", time.Since(start)) } 

Алгоритмический вариант реализации

Для тех, кто подзабыл, алгоритмически верное решение задачи подсчета простых чисел достигается при использовании алгоритма, который называют «Решето Эратосфена»

Ссылка на вики

Поэтому реализуем ее в коде.

func sieveOfEratosthenes(max uint64) []uint64 { if max < 2 { return []uint64{} }  sieve := make([]bool, max+1) for i := range sieve { sieve[i] = true }  for p := uint64(2); p*p <= max; p++ { if sieve[p] { for i := p * p; i <= max; i += p { sieve[i] = false } } }  var primes []uint64 for p := uint64(2); p <= max; p++ { if sieve[p] { primes = append(primes, p) } }  return primes }

И как ожидалось, наши результаты при одинаковых исходных данных

Простых чисел от 2 до 1000000000: 50847534 шт.
Время выполнения: 50.8603695s

Абсолютные цифры не так важны, т.к. будут зависеть от максимальной мощности одного ядра нашего железа. Но разница в 4 раза, кмк, прекрасно демонстрирует важность правильности выбора алгоритма при решении задачи. (это ответ для тех, зачем мне алгоритмы, я CRUDы только и делаю)

package main  import ( "fmt" "time" )  func sieveOfEratosthenes(max uint64) []uint64 { if max < 2 { return []uint64{} }  sieve := make([]bool, max+1) for i := range sieve { sieve[i] = true }  for p := uint64(2); p*p <= max; p++ { if sieve[p] { for i := p * p; i <= max; i += p { sieve[i] = false } } }  var primes []uint64 for p := uint64(2); p <= max; p++ { if sieve[p] { primes = append(primes, p) } }  return primes }  const maxCounterAlgo = 1_000_000_000  func main() { start := time.Now()  primes := sieveOfEratosthenes(maxCounterAlgo)  fmt.Printf("Простых чисел от 2 до %v: %v шт.\n", maxCounterAlgo, len(primes)) fmt.Printf("Время выполнения: %s\n", time.Since(start)) } 

GOрутинный (или многопоточный) способ решения

Язык go позволяет прекрасно писать многопоточные приложения. А значит, давайте реализуем правильный алгоритм, только в многопоточном режиме.

В качестве ограничения количества горутин, будем использовать семафор

func markNonPrimes(sieve []bool, start, end, prime uint64, sem chan struct{}, wg *sync.WaitGroup) { defer wg.Done() for i := start; i <= end; i += prime { sieve[i] = false } <-sem }  func parallelSieveOfEratosthenes(max uint64, numWorkers int) []uint64 { if max < 2 { return []uint64{} }  sieve := make([]bool, max+1) for i := range sieve { sieve[i] = true }  var wg sync.WaitGroup sem := make(chan struct{}, numWorkers)  sqrtMax := uint64(math.Sqrt(float64(max))) for p := uint64(2); p <= sqrtMax; p++ { if sieve[p] { wg.Add(1) sem <- struct{}{} go markNonPrimes(sieve, p*p, max, p, sem, &wg) } }  wg.Wait()  var primes []uint64 for p := uint64(2); p <= max; p++ { if sieve[p] { primes = append(primes, p) } }  return primes }

Таким образом, мы уже можем загрузить не только одно ядро, но и разделить его по всему доступному CPU. Ну и естественно, результат опять лучше.

Простых чисел от 2 до 1000000000: 50847534 шт.
Время выполнения: 8.31986275s

package main  import ( "fmt" "math" "runtime" "sync" "time" )  func markNonPrimes(sieve []bool, start, end, prime uint64, sem chan struct{}, wg *sync.WaitGroup) { defer wg.Done() for i := start; i <= end; i += prime { sieve[i] = false } <-sem }  func parallelSieveOfEratosthenes(max uint64, numWorkers int) []uint64 { if max < 2 { return []uint64{} }  sieve := make([]bool, max+1) for i := range sieve { sieve[i] = true }  var wg sync.WaitGroup sem := make(chan struct{}, numWorkers)  sqrtMax := uint64(math.Sqrt(float64(max))) for p := uint64(2); p <= sqrtMax; p++ { if sieve[p] { wg.Add(1) sem <- struct{}{} go markNonPrimes(sieve, p*p, max, p, sem, &wg) } }  wg.Wait()  var primes []uint64 for p := uint64(2); p <= max; p++ { if sieve[p] { primes = append(primes, p) } }  return primes }  const maxCounterConcurrent = 1_000_000_000  func main() { start := time.Now() numWorkers := (runtime.NumCPU() * 2) - 1  primes := parallelSieveOfEratosthenes(maxCounterConcurrent, numWorkers)  fmt.Printf("Простых чисел от 2 до %v: %v шт.\n", maxCounterConcurrent, len(primes)) fmt.Printf("Время выполнения: %s\n", time.Since(start)) }

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

Но есть одна проблема. Эта реализация имеет невероятно банальное ограничение. И как вы конечно догадались, ограничение это — в максимальном значении типа uint64.

Что будет, если нам нужно посчитать действительно большое число? Как решить задачу? А сколько это стоит вычислительного времени? (ведь бесплатно не бывает ничего)

Задача со звездочкой

Скажу честно, я не очень долго думал над вариантами решения (ну время же поджимает, собес то 1 час идет же). Поэтому я решил использовать big.Int’ы , как решение которое уже есть в языке. Возможно можно сделать оптимальнее, но на практике с big.Int я не сталкивался — напишите в комментариях свой опыт.

func parallelSieveOfEratosthenesBigInt(max *big.Int, numWorkers int) []*big.Int { maxInt64 := max.Int64() sieve := make([]bool, maxInt64+1) for i := range sieve { sieve[i] = true } sieve[0], sieve[1] = false, false  sqrtMax := new(big.Int).Sqrt(max) sqrtMaxInt64 := sqrtMax.Int64()  var wg sync.WaitGroup semaphore := make(chan struct{}, numWorkers)  for p := int64(2); p <= sqrtMaxInt64; p++ { if sieve[p] { wg.Add(1) semaphore <- struct{}{} go func(p int64) { defer func() { <-semaphore }() start := new(big.Int).SetInt64(p * p) prime := new(big.Int).SetInt64(p) markNonPrimesBigInt(sieve, start, max, prime, &wg) }(p) } }  wg.Wait()  var primes []*big.Int for i := int64(2); i <= maxInt64; i++ { if sieve[i] { primes = append(primes, big.NewInt(i)) } }  return primes }

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

Простых чисел от 2 до 1000000000: 50847534 шт.
Время выполнения: 15.391528792s

Как видно разница, почти в 2 раза, это как раз и проблема «универсальности» решения. Поэтому кроме правильно алгоритма стоит правильно ставить ограничения условий работы данного кода.

package main  import ( "fmt" "math/big" "runtime" "sync" "time" )  func markNonPrimesBigInt(sieve []bool, start, end, prime *big.Int, wg *sync.WaitGroup) { defer wg.Done() for i := new(big.Int).Set(start); i.Cmp(end) <= 0; i.Add(i, prime) { sieve[i.Int64()] = false } }  func parallelSieveOfEratosthenesBigInt(max *big.Int, numWorkers int) []*big.Int { maxInt64 := max.Int64() sieve := make([]bool, maxInt64+1) for i := range sieve { sieve[i] = true } sieve[0], sieve[1] = false, false  sqrtMax := new(big.Int).Sqrt(max) sqrtMaxInt64 := sqrtMax.Int64()  var wg sync.WaitGroup semaphore := make(chan struct{}, numWorkers)  for p := int64(2); p <= sqrtMaxInt64; p++ { if sieve[p] { wg.Add(1) semaphore <- struct{}{} go func(p int64) { defer func() { <-semaphore }() start := new(big.Int).SetInt64(p * p) prime := new(big.Int).SetInt64(p) markNonPrimesBigInt(sieve, start, max, prime, &wg) }(p) } }  wg.Wait()  var primes []*big.Int for i := int64(2); i <= maxInt64; i++ { if sieve[i] { primes = append(primes, big.NewInt(i)) } }  return primes }  const maxCounterBigIntS = "1000000000"  func main() { start := time.Now() maxCounterBigInt := new(big.Int) maxCounterBigInt.SetString(maxCounterBigIntS, 10) numWorkers := (runtime.NumCPU() * 2) - 1  primes := parallelSieveOfEratosthenesBigInt(maxCounterBigInt, numWorkers)  fmt.Printf("Простых чисел от 2 до %v: %v шт.\n", maxCounterBigIntS, len(primes)) fmt.Printf("Время выполнения: %s\n", time.Since(start)) } 

И тут я понимаю, что вообще задача со звездочкой решена не верна. И там не все значения идут через bigInt
И вообще там стоит поговорить еще и об ограничении по памяти. Поэтому видимо это уже из другого собеса.