[swift-users] Incorrect Fisher-Yates shuffle in example code

[Saagar Jha]

Saagar Jha

> On Dec 17, 2017, at 22:24, Nevin Brackett-Rozinsky via swift-users <swift-users at swift.org> wrote:
> 
> …well that was more complicated than I anticipated.
> 
> The “random” function was (Int) -> Int, so when I removed the “IndexDistance == Int” constraint on “shuffle” I either had to add several “numericCast” calls or make “random” generic.
> 
> So I made “random” generic. And also fixed the modulo bias issue in the Glibc version that Saagar mentioned. Or at least I hope I did. I haven’t tested that part (nor any of the non-Swift-4 / non-macOS parts). Also, I am not sure why “random” had been a closure value stored in a “let” constant, but I changed it to a function.

Great! I'll close my pull request, then.

> 
> While I was at it, I removed the random-access constraint I had placed on “shuffle”. It will now shuffle any MutableCollection, with complexity O(n) for a RandomAccessCollection and O(n²) otherwise. (The constraint was different in different Swift versions, so the entire extension had to be duplicated. Without the constraint the implementation is much sleeker.)
> 
> Nevin
> 
> 
> On Sun, Dec 17, 2017 at 9:26 PM, Nevin Brackett-Rozinsky <nevin.brackettrozinsky at gmail.com <mailto:nevin.brackettrozinsky at gmail.com>> wrote:
> On Sun, Dec 17, 2017 at 7:37 PM, Dave Abrahams <dabrahams at apple.com <mailto:dabrahams at apple.com>> wrote:
> 
>> On Dec 16, 2017, at 4:34 PM, Nevin Brackett-Rozinsky via swift-users <swift-users at swift.org <mailto:swift-users at swift.org>> wrote:
>> 
>> public extension MutableCollection where Self: RandomAccessCollection, IndexDistance == Int {
> 
> IndexDistance == Int is an over-constraint, FWIW.  Adding it is generally a mistake.  Not a serious one, but it does limit utility somewhat.
> 
> HTH,
> Dave
> 
> You are correct, however there is an accepted-and-implemented proposal (SE–0191 <https://github.com/apple/swift-evolution/blob/master/proposals/0191-eliminate-indexdistance.md>) to eliminate IndexDistance and replace it with Int, so the constraint will always be satisfied starting in Swift 4.1.
> 
> I wrote a version of shuffle() without that constraint, but it is less elegant: the line “for n in 0 ..< count - 1” no longer compiles, and writing “0 as IndexDistance” doesn’t fix it because the resulting Range is not a Sequence, since IndexDistance.Stride does not conform to SignedInteger (at least in Swift 4.0 according to Xcode 9.2).
> 
> A while loop works of course, though a direct conversion requires writing “var n = 0 as IndexDistance” before the loop. Luckily, with a bit of cleverness we can eliminate all mention of IndexDistance, and this time we really and truly don’t need the “guard !isEmpty” line:
> 
> extension MutableCollection where Self: RandomAccessCollection {
>     mutating func shuffle() {
>         var n = count
>         while n > 1 {
>             let i = index(startIndex, offsetBy: count - n)
>             let j = index(i, offsetBy: random(n))
>             n -= 1
>             swapAt(i, j)
>         }
>     }
> }
> 
> Essentially, the constraint is there to make the code nicer on pre-4.1 versions of Swift, though I’m happy to remove it if you think that’s better. If nothing else, removing the constraint means people reading the example code in the future won’t be misled into thinking they need to use it themselves, so perhaps it should go just on that account.
> 
> Okay, you’ve convinced me, I’ll update the PR. :-)
> 
> Nevin
> 
> _______________________________________________
> swift-users mailing list
> swift-users at swift.org
> https://lists.swift.org/mailman/listinfo/swift-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20171217/c6a60e2d/attachment.html>