//===----------------------------------------------------------------------===// // // This source file is part of the Swift Algorithms open source project // // Copyright (c) 2020 Apple Inc. and the Swift project authors // Licensed under Apache License v2.0 with Runtime Library Exception // // See https://swift.org/LICENSE.txt for license information // //===----------------------------------------------------------------------===// // For log(_:) and root(_:_:) @_implementationOnly import RealModule //===----------------------------------------------------------------------===// // randomStableSample(count:) //===----------------------------------------------------------------------===// extension Collection { /// Randomly selects the specified number of elements from this collection, /// maintaining their relative order. /// /// - Parameters: /// - k: The number of elements to randomly select. /// - rng: The random number generator to use for the sampling. /// - Returns: An array of `k` random elements. If `k` is greater than this /// collection's count, then this method returns the full collection. /// /// - Complexity: O(*n*), where *n* is the length of the collection. @inlinable public func randomStableSample( count k: Int, using rng: inout G ) -> [Element] { guard k > 0 else { return [] } var remainingCount = count guard k < remainingCount else { return Array(self) } var result: [Element] = [] result.reserveCapacity(k) var i = startIndex var countToSelect = k while countToSelect > 0 { let r = Int.random(in: 0.. [Element] { var g = SystemRandomNumberGenerator() return randomStableSample(count: k, using: &g) } } //===----------------------------------------------------------------------===// // randomSample(count:) //===----------------------------------------------------------------------===// // These methods use Algorithm L, described in "Reservoir-Sampling // Algorithms of Time Complexity O(n(1 + log(N/n)))": // https://dl.acm.org/doi/pdf/10.1145/198429.198435 @usableFromInline internal func nextW( k: Int, using rng: inout G ) -> Double { Double.root(.random(in: 0..<1, using: &rng), k) } @usableFromInline internal func nextOffset( w: Double, using rng: inout G ) -> Int { let offset = Double.log(.random(in: 0..<1, using: &rng)) / .log(onePlus: -w) return offset < Double(Int.max) ? Int(offset) : Int.max } extension Collection { /// Randomly selects the specified number of elements from this collection. /// /// - Parameters: /// - k: The number of elements to randomly select. /// - rng: The random number generator to use for the sampling. /// - Returns: An array of `k` random elements. The returned elements may be /// in any order. If `k` is greater than this collection's count, then this /// method returns the full collection. /// /// - Complexity: O(*k*), where *k* is the number of elements to select, if /// the collection conforms to `RandomAccessCollection`. Otherwise, O(*n*), /// where *n* is the length of the collection. @inlinable public func randomSample( count k: Int, using rng: inout G ) -> [Element] { guard k > 0 else { return [] } var w = 1.0 var result: [Element] = [] result.reserveCapacity(k) // Fill the reservoir with the first `k` elements. var i = startIndex while i != endIndex, result.count < k { result.append(self[i]) formIndex(after: &i) } while i != endIndex { // Calculate the next value of w. w *= nextW(k: k, using: &rng) // Find index of the next element to swap into the reservoir. let offset = nextOffset(w: w, using: &rng) i = index(i, offsetBy: offset, limitedBy: endIndex) ?? endIndex if i != endIndex { // Swap selected element with a randomly chosen one in the reservoir. let j = Int.random(in: 0.. [Element] { var g = SystemRandomNumberGenerator() return randomSample(count: k, using: &g) } } extension Sequence { /// Randomly selects the specified number of elements from this sequence. /// /// - Parameters: /// - k: The number of elements to randomly select. /// - rng: The random number generator to use for the sampling. /// - Returns: An array of `k` random elements. The returned elements may be /// in any order. If `k` is greater than this sequence's count, then this /// method returns the full sequence. /// /// - Complexity: O(*n*), where *n* is the length of the sequence. @inlinable public func randomSample( count k: Int, using rng: inout G ) -> [Element] { guard k > 0 else { return [] } var w = 1.0 var result: [Element] = [] result.reserveCapacity(k) // Fill the reservoir with the first `k` elements. var iterator = makeIterator() while result.count < k, let el = iterator.next() { result.append(el) } while true { // Calculate the next value of w. w *= nextW(k: k, using: &rng) // Find the offset of the next element to swap into the reservoir. var offset = nextOffset(w: w, using: &rng) // Skip over `offset` elements to find the selected element. while offset > 0, let _ = iterator.next() { offset -= 1 } guard let nextElement = iterator.next() else { break } // Swap selected element with a randomly chosen one in the reservoir. let j = Int.random(in: 0.. [Element] { var g = SystemRandomNumberGenerator() return randomSample(count: k, using: &g) } } //===----------------------------------------------------------------------===// // randomElement() //===----------------------------------------------------------------------===// // This method is a single-element specialization of `randomSample(count:)`, // and extends the stdlib's `randomElement()` functionality (which is available // for collections) down to sequences. extension Sequence { /// Randomly selects an element from this sequence, using the given generator /// as the source of randomness. /// /// - Parameter rng: The random number generator to use for sampling. /// - Returns: A random element. If the sequence has no elements, this method /// returns `nil`. /// /// - Complexity: O(*n*), where *n* is the length of the sequence. @inlinable public func randomElement( using rng: inout G ) -> Element? { var iterator = makeIterator() guard var result = iterator.next() else { return nil } var w = 1.0 while true { w *= nextW(k: 1, using: &rng) var offset = nextOffset(w: w, using: &rng) while offset > 0, let _ = iterator.next() { offset -= 1 } guard let nextElement = iterator.next() else { break } result = nextElement } return result } /// Randomly selects an element from this sequence. /// /// This method is equivalent to calling `randomSample(using:)`, passing in /// the system's default random generator. /// /// - Returns: A random element. If the sequence has no elements, this method /// returns `nil`. /// /// - Complexity: O(*n*), where *n* is the length of the sequence. @inlinable public func randomElement() -> Element? { var g = SystemRandomNumberGenerator() return randomElement(using: &g) } }