Saagar Jha
> On Dec 16, 2017, at 16:34, Nevin Brackett-Rozinsky via swift-users
> <[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.
Actually, I believe the first guard is still necessary–if the collection is
empty, you’d end up with trying to construct the range 0..<-1, which traps.
Alternatively, stride(from:to) is more lenient.
>
> 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]
> https://lists.swift.org/mailman/listinfo/swift-users
_______________________________________________
swift-users mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-users
