While we’re still looking at the Fisher-Yates shuffle package, I stumbled upon
this
<https://github.com/apple/example-package-fisheryates/blob/master/Sources/FisherYates/random.swift#L18>
definition of random():
public let random: (Int) -> Int = {
while true {
let x = Glibc.random() % $0
let y = Glibc.random() % $0
guard x == y else { return x }
}
}
Perhaps I’m mistaken here, but if this is random(3)
<https://developer.apple.com/legacy/library/documentation/Darwin/Reference/ManPages/man3/random.3.html>
don’t we have to 1. seed it before use and 2. deal with modulo bias? I’m also
not quite sure why the guard is there, either.
Saagar Jha
> On Dec 16, 2017, at 16:37, Daniel Dunbar via swift-users
> <[email protected]> wrote:
>
> Would you like to post a PR to fix these issues?
>
> - Daniel
>
>> On Dec 16, 2017, at 4:34 PM, Nevin Brackett-Rozinsky via swift-users
>> <[email protected] <mailto:[email protected]>> wrote:
>>
>> The example implementation of the Fisher-Yates shuffle found here
>> <https://github.com/apple/example-package-fisheryates/blob/master/Sources/FisherYates/Fisher-Yates_Shuffle.swift>
>> on Apple’s GitHub (and linked from swift.org/package-manager
>> <https://swift.org/package-manager/>) has some problems. Stripping it down
>> to just the Swift 4 version, the code is:
>>
>> public extension MutableCollection where Index == Int, IndexDistance == Int {
>> mutating func shuffle() {
>> guard count > 1 else { return }
>>
>> for i in 0..<count - 1 {
>> let j = random(count - i) + i
>> guard i != j else { continue }
>> swapAt(i, j)
>> }
>> }
>> }
>>
>> The main issues are:
>>
>> 1) It assumes that indices are 0-based.
>> 2) It assumes that indices can be randomly accessed by addition.
>>
>> The former means it does not work for ArraySlice, and the latter means it
>> won’t work for all custom types. Additionally, the “count” property (which
>> is only guaranteed to be O(n) here) is accessed inside the loop, thus making
>> the algorithm potentially O(n²).
>>
>> To fix everything, we’ll want RandomAccessCollection conformance. Once we
>> add that, we no longer need “Index == Int”. The result looks like:
>>
>> public extension MutableCollection where Self: RandomAccessCollection,
>> IndexDistance == Int {
>> mutating func shuffle() {
>> for n in 0 ..< count-1 {
>> let i = index(startIndex, offsetBy: n)
>> let j = index(i, offsetBy: random(count-n))
>> swapAt(i, j)
>> }
>> }
>> }
>>
>> Both of the original guard statements would be superfluous here (notably,
>> “swapAt” is documented to have no effect when i and j are the same) so I
>> removed them.
>>
>> Technically we could get away without random access and still have an O(n)
>> algorithm, at the cost of copying the indices to an array:
>>
>> public extension MutableCollection {
>> mutating func shuffle() {
>> guard !isEmpty else { return }
>>
>> var idx = Array(indices)
>>
>> for i in 0 ..< idx.count - 1 {
>> let j = i + random(idx.count - i)
>> swapAt(idx[i], idx[j])
>> idx.swapAt(i, j)
>> }
>> }
>> }
>>
>> In any event, just in case someone was using a cut-and-paste version of the
>> example code in their own project, now you know it needs adjustment.
>>
>> Nevin
>> _______________________________________________
>> swift-users mailing list
>> [email protected] <mailto:[email protected]>
>> https://lists.swift.org/mailman/listinfo/swift-users
>
> _______________________________________________
> swift-users mailing list
> [email protected]
> https://lists.swift.org/mailman/listinfo/swift-users
_______________________________________________
swift-users mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-users
