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

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

Я очень плохо прохожу любые экзамены. Почти всегда иду не в ногу. И мне всегда казалось, что в этом процессе есть что-то неправильное. В компаниях типа Яндекса или Гугла, когда требуется набрать инженеров-программистов, причем неизвестно, на каком языке и проекте они будут работать, еще хотя бы понятно, зачем это нужно. А что делать в обычных компаниях? Где нужно писать 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
И вообще там стоит поговорить еще и об ограничении по памяти. Поэтому видимо это уже из другого собеса.