Привет, Хабр! А вы любите на собеседованиях проходить алгоритмические секции? А лайв-кодинг? Задачки такие «интересные», что на код-ревью такого бы умельца — тряпками и бранными словами. Минимум...., но коллега же. Поэтому просто попросим переделать.
Решать задачки под присмотром пары, а то и десятка глаз, смотрящих на тебя. И в них далеко не страх, как в известной песне, а боль и разочарование. Вроде и резюме, и опыт релевантный, а задачу дали абсурдную, которую на проекте никогда решать не придется.
Я очень плохо прохожу любые экзамены. Почти всегда иду не в ногу. И мне всегда казалось, что в этом процессе есть что-то неправильное. В компаниях типа Яндекса или Гугла, когда требуется набрать инженеров-программистов, причем неизвестно, на каком языке и проекте они будут работать, еще хотя бы понятно, зачем это нужно. А что делать в обычных компаниях? Где нужно писать CRUD’ы и настраивать межсерверное взаимодействие? Мне кажется, это неестественно.
Но однажды, объясняя дочери, что такое простые числа, я придумал идеальную алгоритмическую секцию для Go-разработчика. Примерно за час набросал задачу (как раз стандартное время на алгосекцию). Интересно? Добро пожаловать под кат!
Итак, сегодня мы попробуем совместно пройти идеальный АлгоСобес. У нас сегодня будет:
Реализуем банальным способом.
У нас на сегодня одна задача. Нам нужно как можно быстрее посчитать большое количество простых чисел. Давайте реализуем это в коде.
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
И вообще там стоит поговорить еще и об ограничении по памяти. Поэтому видимо это уже из другого собеса.
Комментарии (2)
NomLi
13.09.2024 06:03+1У нас кадровик как анекдот рассказывала про одно собеседование. Пришел претендент и чем-то он сильно не понравился, решили его намеренно завалить - дали сложные алгоритмические задачи. Чувак раз и решил, давайте говорит ещё - дали. Он бац и опять шустро решил. Ему пытаются как-то отказать в стиле "мы вам перезвоним". Претендент отвечает: что я к вам на работу устраиваться что ли пришел? Мне сказали у вас крутые, интересные, а главное свежие задачи. Мне как раз для сайта нужны. Давайте все что у вас есть.
qrKot
поиск простых чисел!