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 > <swift-users@swift.org> 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 > swift-users@swift.org > https://lists.swift.org/mailman/listinfo/swift-users
_______________________________________________ swift-users mailing list swift-users@swift.org https://lists.swift.org/mailman/listinfo/swift-users
