Comments 10
Никогда не писал на Swift, но не логичнее ли записать цикл вот так (и сократить операцию сравнения внутри цикла?):
while (testValue.powerOf2() <= max) {
data.removeAll(where: {$0 >= testValue.powerOf2() && $0.isMultiple(of: testValue)})
testValue = data.first(where: {$0 > testValue})!
}
var data = (2...max).map{$0}на
var data = Array(2...max)На инициализации массива выигрывает 0.01 секунду и почему-то почти 0.2 на исполнении (надо бы попрофайлить). На MBP 2014 (i7-4780HQ, 16Gb) при размере 8.5 млн исполняется за 3.46 секунды с оптимизациями. В дебаг режиме выполнилось за 240 секунд )
Если не заниматься бессмысленными перемещениями данных в памяти, то будет работать значительно быстрее.
Вот-такой код работает в ~60 раз быстрее, чем версия из статьи.
Хотя и стало немного многословнее, да.
import Foundation
// квадрат числа
extension Int {
func powerOf2() -> Int {
return self * self
}
}
// до скольки считаем?
let max = 8_500_000
let startTime = Date()
// заполняем массив
var data = Array(repeating: true, count: max + 1) //(2...max).map{$0}
data[0] = false
data[1] = false
let allocationTime = Date()
// вычисления
for currentPrime in (2...Int(sqrt(Double(max)))) {
if !data[currentPrime] {
continue
}
for multiple in stride(from:currentPrime.powerOf2(), through: max, by: currentPrime) {
data[multiple] = false
}
}
let primes = (2...max).filter{data[$0]}
let overallTime = Date()
// выводим результаты
print("Всего \(primes.count) простых чисел")
print()
print("Выделение массива: \(String(format: "%.2f",(allocationTime.timeIntervalSince(startTime)))) с. ")
print("Вычисления: \(String(format: "%.2f",(overallTime.timeIntervalSince(allocationTime)))) с. ")
print("Всего: \(String(format: "%.2f",(overallTime.timeIntervalSince(startTime)))) с. ")P.S.
К сожалению, запуск этого кода в плэйграунде на моем Mac Mini Late 2014 (Core i5, 8 ГБ) уже с параметром max = 1 000 000 приводит к диким тормозам, так что будьте осторожны
Лень запускать мак, чтобы убедиться на 100%, что дело именно в этом, но я вам зуб даю, что к диким тормозам приводит глупая попытка вывести кучу данных в консоль одной строкой. Перестаньте выводить мегабайты найденных чисел и тормоза внезапно перестанут быть дикими.
И насчёт тормозов. Может и так, как вы говорите, но тормоза возникали еще на этапе цикла, когда справа отображалось количество исполнений. До отображения результатов.
Хотя и стало немного многословнее, да.
Да как следует многословнее стало, да.
когда справа отображалось количество исполнений
Как-то умудрился пропустить момент, что вы это дело еще и в плейграунде пытались запустить. Тогда да, тут еще меньше поводов для удивления. Мало того, что код без оптимизаций собирается, так к нему еще дебаггер приаттачен, через который в риалтайме куча рюшечек в gui красиво мигает и обновляется.
Инструменты стоит использовать по назначению. Плейграунды — не для того, чтобы в них гонять миллионы итераций. А консоль Xcode не для того, чтобы выводить в нее мегабайты текста одной строкой.
я изначально не гнался за эффективностью выполнения
И к чему тогда все эти замеры времени в коде?
демонстрация возможностей Swift. Зато тут вся реализация заключена в трех строчках в цикле while, включая условие выхода.
Если стояла цель показать лаконичность свифта, то стоило нормально структурировать код хотя-бы путем выноса самого алгоритма в отдельную функцию. А в текущем виде — что у вас, что у меня, код — это полу-хаотичная мешанина из ввода-вывода, замеров времени, вспомогательных расширений и собственно самого алгоритма. Лаконичностью это все и не пахнет.
Если же под "возможностями" вы подразумеваете не лаконичность, а функциональные возможности, то выбор решета в качестве примера для демонстрации — очень странный. Какие возможности показаны? Циклы, массивы и замыкания? Исчерпывающая деморнстрация.
Код написан ясно, откомментирован и изначально без претензии на первые места в конкурсе на скорость поиска простых чисел.
Какие возможности показаны? Циклы, массивы и замыкания?
Показаны возможности, достаточные для решения конкретной задачи наименьшим количеством кода. Фильтров не показал, да.
import kotlin.system.measureTimeMillis
// квадрат числа
fun Int.powerOf2() = this * this
// кратность числа
fun Int.isMultiple(of: Int) = this % of == 0
// до скольки считаем?
const val max = 8_500_000
fun main() {
// заполняем массив
lateinit var data: List<Int>
val allocationTime = measureTimeMillis {
data = (2..max).toList()
}
// первое простое число
var testValue = 2
// вычисления
val overallTime = measureTimeMillis {
while (testValue.powerOf2() <= max) {
data = data.filterNot { it >= testValue.powerOf2() && it.isMultiple(testValue) }
testValue = data.first { it > testValue }
}
}
// выводим результаты
println("Всего простых чисел: ${data.count()}")
println("Выделение массива: $allocationTime")
println("Вычисления: $overallTime")
println("Всего: ${allocationTime + overallTime}")
}
Swift: решето Эратосфена