Почему Int.random () медленнее, чем arc4random_uniform ()?

Question

Я использовал метод Int.random () и arc4random_uniform () для тестов скорости генерации чисел.
Оба теста были запущены в консоли macOS с настроенной версией сборки Ниже приведены коды, которые я использовал для тестирования.

public func randomGen1() {
    let n = 1_000_000
    let startTime = CFAbsoluteTimeGetCurrent()
    for i in 0..<n {
        _ = arc4random_uniform(10)
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(timeElapsed)
}
public func randomGen2() {
    let n = 1_000_000
    let startTime = CFAbsoluteTimeGetCurrent()
    for i in 0..<n {
        _ = Int.random(in: 0..<10)
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(timeElapsed)
}

Время, которое я получил
0.029475092887878418 (для arc4random_uniform (10))
0.20298802852630615 (для Int.random (in: 0 .. <10)) </p>

Почему Int.random () намного медленнее?
Есть ли способ оптимизировать его?
Есть ли в swift более быстрые методы генерации случайных чисел?

Answer 1

Обновление

Эта реализация генератора случайных чисел в интервале была объединена со стандартной библиотекой и должна работать лучше, чем раньше:

// s = upperBound; r1, r2 = random numbers from generator
func bounded(s: UInt64, r1:UInt64, r2: UInt64) -> UInt64 {
    // r1 would come from invoking generator's next()
    var m = r1.multipliedFullWidth(by: s)
    if m.low < s {
        // let t = (0 &- s) % s // Lemire's original form
        var t = 0 &- s // O'Neill's modulo optimization
        if t >= s {
            t &-= s
            if t >= s {
                t %= s
            }
        }
        while m.low < t {
            // r2 would come from invoking generator's next()
            m = r2.multipliedFullWidth(by: s)
        }
    }
    return m.high
}

См.ответ ниже для более подробной информации.

Ответ

Ответ на ваш второй вопрос:

"Есть ли более быстрые методы генерации случайных чисел в swift?"

Я ранее использовал Xoshiro Генератор псевдослучайных чисел, который довольно быстр.

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

• randomGen1

import Foundation

public func randomGen1() {
    let n = 1_000_000
    var sum: UInt32 = 0
    let startTime = CFAbsoluteTimeGetCurrent()
    for _ in 0..<n {
        sum = sum &+ arc4random_uniform(10)
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(sum, timeElapsed)
}

do {
    randomGen1()
}

• randomGen2

public func randomGen2() {
    let n = 1_000_000
    var sum: UInt32 = 0
    let startTime = CFAbsoluteTimeGetCurrent()
    for _ in 0..<n {
        sum = sum &+ UInt32.random(in: 0..<10)
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(sum, timeElapsed)
}


do {
    randomGen2()
}

• Генератор случайных чисел Xoshiro из этой библиотеки :

struct Xoshiro: RandomNumberGenerator {
    public typealias StateType = (UInt32, UInt32, UInt32, UInt32)

    private var state: StateType

    public init(seed: StateType) {
        self.state = seed
    }

    public mutating func next() -> Int {
        let x = state.1 &* 5
        let result = ((x &<< 7) | (x &>> 25)) &* 9
        let t = state.1 &<< 9
        state.2 ^= state.0
        state.3 ^= state.1
        state.1 ^= state.2
        state.0 ^= state.3
        state.2 ^= t
        state.3 = (state.3 &<< 21) | (state.3 &>> 11)
        return Int(result)
    }
}

var x = Xoshiro(seed: (UInt32.random(in: 0..<10),  //Other upper limits could be used to increase randomness
    UInt32.random(in: 0..<10),
    UInt32.random(in: 0..<10),
    UInt32.random(in: 0..<10)))

public func randomGen3() {
    let n = 1_000_000
    var sum: UInt32 = 0
    let startTime = CFAbsoluteTimeGetCurrent()
    for _ in 0..<n {
        sum = sum &+ UInt32(abs(x.next()) % 10)
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(sum, timeElapsed)
}

do {
    randomGen3()
}

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

Даниэль Лемир (автор этой статьи)любезно только что прислал мне Swift реализацию Wyhash:

class WyhashGenerator {
    var seed : UInt64

    let multiplier1 : UInt64 = 0xa3b195354a39b70d
    let multiplier2 : UInt64 = 0x1b03738712fad5c9
    let increment : UInt64 = 0x60bee2bee120fc15

    init(userSeed : UInt64) {
        seed = userSeed;
    }

    func random() -> UInt64 {
        seed &+= increment
        let fullmult1 = seed.multipliedFullWidth(by: multiplier1)
        let m1 = fullmult1.high ^ fullmult1.low;
        let fullmult2 = m1.multipliedFullWidth(by: multiplier2)
        let m2 = fullmult2.high ^ fullmult2.low;
        return m2
    }
}

Это можно использовать так:

public func randomGen4() {
    let n = 1_000_000
    var sum: UInt64 = 0
    let startTime = CFAbsoluteTimeGetCurrent()
    let gen = WyhashGenerator(userSeed: 0)
    for _ in 0..<n {
        sum = sum &+ gen.random() % 10
    }
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    print(sum, timeElapsed)
}

do {
    randomGen4()
}

---

А вот и тестрезультаты с кодом, скомпилированным в терминале с оптимизацией (-O):

arc4random_uniform()  : 0.034s
UInt32.random(in:)    : 0.243s
WyHash64              : 0.002s
Xoshiro               : 0.001s

---

^{Вы можете найти больше генераторов случайных чисел здесь .}