Генератор простых чисел в Swift


Я хотел бы сделать (или улучшить функцию) функция, которая возвращает массив целых чисел, содержащий все простые числа от 2...n Что можно выполнить максимально быстро и эффективно, насколько это возможно (в идеале, так что он будет в состоянии выполнить n = 1,000,000,000 в считанные секунды). Я с помощью SWIFT и Xcode 4.1 9.3.

Где я в настоящее время в

До сих пор я использовал решето Эратосфена , чтобы сделать эту функцию, которая может вычислить простые числа в 1 000 000 в 0.28 С, но когда я пытаюсь его с число, например, 1 млрд или 1 трлн., это занимает слишком много времени.

func generatePrimes(to n: Int) -> [Int] {

    precondition(n > 5, "Input must be greater than 5")

    var arr : [Int] = Array<Int>(stride(from: 3, to: n, by: 2))     

    for index in 0... {
        let num : Int = arr.remove(at: index)
        arr = arr.filter{ $0 % num != 0 }
        arr.insert(num, at: index)
        if arr[index + 1] >= Int(floor(sqrtf(Float(n)))) { break }
    }

    arr.insert(2, at: 0)

    //Print Statements
    print("Prime numbers under \(n):")
    _ = arr.enumerated().map { (index, element) in print("\t\(index + 1). \(element)") }

    return arr
}

Использование:

generatePrimes(to: 50)

Печать:

Prime numbers under 50:
    1. 2
    2. 3
    3. 5
    4. 7
    5. 11
    6. 13
    7. 17
    8. 19
    9. 23
    10. 29
    11. 31
    12. 37
    13. 41
    14. 43
    15. 47


Комментарии
1 ответ

Это не решето Эратосфена

В решето Эратосфена вычисление кратных
каждая найденная премьер-отмечать последующие составные числа в порожнее.
Ваш алгоритм вычисляет остаток всех последующих чисел.
Это делает огромную разницу. Я вернусь к этому позже, давайте начнем
с

Обзор ваш текущий код

Здесь есть несоответствие:

func generatePrimes(to n: Int) -> [Int] {
// ...
var arr : [Int] = Array<Int>(stride(from: 3, to: n, by: 2))
// ...
}

Функция – как я понимаю to параметр –
вычисляет все простые числа вплоть до и включая n. С другой стороны,
stride(from: 3, to: n, by: 2) совсем не включает верхнюю границу,
и это легко проверяется с

print(generatePrimes(to: 11)) // [2, 3, 5, 7]

Так что либо переименовать функцию func generatePrimes(below n: Int)
или использовать stride(from: 3, through: n, by: 2) включив в верхней границы.
Я сделаю последнее в этом обзоре.

Также было бы хорошей идеей, чтобы добавить комментарий документация,
однозначно документы параметры функции.

Явные аннотации типа не нужен, а создание массива
может быть упрощен до

var arr = Array(stride(from: 3, through: n, by: 2))

Почему-предельное количество, как ожидается, будет больше, чем 5? Это
ненужных ограничений и будет неожиданным для звонящего из вашей функции. Может быть так, что ваша реализация не будет работать, если
\ ФП \Ле 5 \$, но это было бы легко справиться, что чехол отдельно:

if n <= 5 {
return [2, 3, 5].filter { $0 <= n }
}

В

    let num : Int = arr.remove(at: index)

аннотация тип слева снова не нужен.

(Замечание: Это

    arr = arr.filter { $0 % num != 0 }

может быть заменен более эффективным

    arr.removeAll(where: { $0 % num == 0 })

в будущей версии Свифта, когда СЕ-0197 добавив в метод removeall(где:) в стандартной библиотеке реализован в Свифт-4.2.)

Здесь

    if arr[index + 1] >= Int(floor(sqrtf(Float(n)))) { break }

скрытый Жук: Как

print(generatePrimes(to: 26)) // [2, 3, 5, 7, 11, 13, 17, 19, 23, 25]

демонстрирует, вы не оставляя петли в начале.
Я также хотел вычислить квадратный корень только один раз, и использовать двойной точности
арифметика: 24 бит мантиссы из Float не может представлять большие
числа правильно (сравните вычисления целочисленного квадратного корня из больших чисел).

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

//Print Statements
print("Prime numbers under \(n):")
_ = arr.enumerated().map { (index, element) in print("\t\(index + 1). \(element)") }

должны быть удалены. Это вообще хорошая привычка раздельные расчеты с I/О.
Кроме того, это искажает результаты тестов, потому что вы измеряете и
время для преобразования чисел в строки, и время, чтобы напечатать эти строки
(что зависит от мощности устройства, печать в файл-это быстрее, чем печатать
до терминала или консоли Xcode).

Со всеми изменениями, которые предложил до сих пор, ваша функция будет выглядеть так:

/// Compute list of primes
///
/// - Parameter n: The upper bound
/// - Returns: An array with all primes <= `n`
func generatePrimes(to n: Int) -> [Int] {

if n <= 5 {
return [2, 3, 5].filter { $0 <= n }
}

var arr = Array(stride(from: 3, through: n, by: 2))

let squareRootN = Int(Double(n).squareRoot())
for index in 0... {
if arr[index] > squareRootN { break }
let num = arr.remove(at: index)
arr = arr.filter { $0 % num != 0 }
arr.insert(num, at: index)
}

arr.insert(2, at: 0)
return arr
}

Используя решето Эратосфена

Как я уже сказал выше, ваш алгоритм отличается от Эратосфена решето.
Каждый раз, когда простое число \$ р \$ будет найден, ваш код делает пробный отделов
все остальные цифры, чтобы удалить кратные \$ Р \$.
В решето Эратосфена вычисление кратных \$ р \$ вместо:

p*p, p*p + p, p*p + 2*p, p*p + 3*p, ...

и отмечает их как составные. Обратите внимание, что есть гораздо меньше значения для расчета.

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

На Эратосфена решето работает с фиксированного размера, а не булевский массив.

Вот очень простой прямой реализации в Swift:

func eratosthenesSieve(to n: Int) -> [Int] {
var composite = Array(repeating: false, count: n + 1) // The sieve
var primes: [Int] = []

if n >= 150 {
// Upper bound for the number of primes up to and including `n`,
// from https://en.wikipedia.org/wiki/Prime_number_theorem#Non-asymptotic_bounds_on_the_prime-counting_function :
let d = Double(n)
let upperBound = Int(d / (log(d) - 4))
primes.reserveCapacity(upperBound)
} else {
primes.reserveCapacity(n)
}

let squareRootN = Int(Double(n).squareRoot())
var p = 2
while p <= squareRootN {
if !composite[p] {
primes.append(p)
for q in stride(from: p * p, through: n, by: p) {
composite[q] = true
}
}
p += 1
}
while p <= n {
if !composite[p] {
primes.append(p)
}
p += 1
}
return primes
}

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

Это уже значительно быстрее, чем исходный код.
Вот мой код бенчмаркинга:

func benchmark(_ ident: String, _ function: (Int) -> [Int], to n: Int) {
let start = Date()
let primes = function(n)
let elapsed = Date().timeIntervalSince(start)
print(ident, primes.count, "primes up to", n, String(format: "time: %.3f", elapsed))
}

benchmark("original", generatePrimes, to: 100_000)
benchmark("original", generatePrimes, to: 1_000_000)
benchmark("original", generatePrimes, to: 10_000_000)

print()

benchmark("eratosthenes", eratosthenesSieve, to: 100_000)
benchmark("eratosthenes", eratosthenesSieve, to: 1_000_000)
benchmark("eratosthenes", eratosthenesSieve, to: 10_000_000)
benchmark("eratosthenes", eratosthenesSieve, to: 100_000_000)
benchmark("eratosthenes", eratosthenesSieve, to: 1_000_000_000)

На 1,2 ГГц процессор Core М5 MacBook (с дисплеем Retina, 12 дюймов, начало 2016)
с 8 ГБ ОЗУ я получаю следующие результаты (слегка переформатирован в
повышение удобочитаемости):


оригинальный 9592 простых чисел до 100000 раз: 0.038
оригинальный 78498 простых чисел до 1000000 раз: 0.418
оригинальный 664579 простых чисел до 10000000 время: 9.739

Эратосфен 9592 простых чисел до 100000 раз: 0.001
Эратосфен 78498 простых чисел до 1000000 раз: 0.007
Эратосфен 664579 простых чисел до 10000000 время: 0.096
5761455 Эратосфен простые числа до 100000000 раз: 1.223
Эратосфен 50847534 простых чисел до 1000000000 раз: 15.034

Это, безусловно, может быть улучшена, первым шагом будет обрабатывать случай p=2
отдельно и использовать решето только по нечетным числам (которые, однако, усложняет
расчеты индекса немного).

Но, как видите, вычисления простых чисел до 1 млрд рублей возможно с ситом
Эратосфена (и цифры верны, вы можете сравнить их с
https://primes.utm.edu/howmany.html).

Идет на триллион

Вы думали вычисления всех простых чисел до одного триллиона. Что может быть
проблема, независимо от того, какой алгоритм вы выберете. По данным
https://primes.utm.edu/howmany.htmlесть 37,607,912,018 простых чисел
ниже 1 трлн. Даже если мы используем 32-бит целых чисел для экономии места, что бы
по-прежнему требуют около 140 ГБ оперативной памяти, что делает возвращает массив со всеми, что
цифры сложно.

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

9
ответ дан 14 апреля 2018 в 12:04 Источник Поделиться