4 ms·

A use case may be shuffling the entire list, if I'm not mistaken?

OscarCunningham 7y ago
They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn. > The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.
- klingonopera 7y ago
  ...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail? You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...
  - OscarCunningham 7y ago
    An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.
    - klingonopera 7y ago
      Wouldn't this have a bias to how the initial input sequence is? EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.
    - sweeneyrod 7y ago
      That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.
      - OscarCunningham 7y ago
        I had an error which I believe I have now fixed. The intended algorithm is "starting at the end of the list, swap each element with a random predecessor or possibly with itself".
  - yorwba 7y ago
    You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.
    - klingonopera 7y ago
      I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above... ...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...
      - yorwba 7y ago
        OscarCunningham's implementation https://news.ycombinator.com/item?id=20961548 https://news.ycombinator.com/item?id=20961548 remembers what has already been swapped using the counter i.
      - reggieband 7y ago
        Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely". Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place." [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
        klingonopera 7y ago
        According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n). The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased. To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic. Thank you for posting the link. EDIT: I try not to post usernames in text, in case anyone ever changes their name. EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.
ses1984 7y ago
How long do you think it will take you to shuffle a list of size 2^64?

They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn. > The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.

klingonopera 7y ago
...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail? You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...
- OscarCunningham 7y ago
  An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.
  - klingonopera 7y ago
    Wouldn't this have a bias to how the initial input sequence is? EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.
  - sweeneyrod 7y ago
    That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.
    - OscarCunningham 7y ago
      I had an error which I believe I have now fixed. The intended algorithm is "starting at the end of the list, swap each element with a random predecessor or possibly with itself".
- yorwba 7y ago
  You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.
  - klingonopera 7y ago
    I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above... ...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...
    - yorwba 7y ago
      OscarCunningham's implementation https://news.ycombinator.com/item?id=20961548 https://news.ycombinator.com/item?id=20961548 remembers what has already been swapped using the counter i.
    - reggieband 7y ago
      Fisher-Yates [1] algorithm is proven to "produce an unbiased permutation: every permutation is equally likely". Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place." [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
      - klingonopera 7y ago
        According to examples in the English Wikipedia, the method I described above is actually the Fisher-Yates method (and its naive implementation, and thus the O(n²) complexity), and the swapping method on everyone's minds was actually Durstenfeld's (optimization?), with O(n). The initial code snippet intended to be Durstenfeld was erroneously an off-by-one Sattolo implementation, which then further solidifyed my suspicion that it had a bias, which Sattolo's implementation actually indeed has. The Durstenfeld method is however proven to be unbiased. To add further confusion to the names in the issue, though some readers might not be able to verify due to the language barrier, the German Wiki states (claims?) Fisher-Yates is Durstenfeld's method with O(n), and the "naive" Fisher-Yates is labelled as the "direct" approach, with O(n²). The name Durstenfeld is not mentioned anywhere on the German Wiki. Though the names are different, the maths are the same in both English and German. I speak German and often read both versions of an article, in case anyone's wondering why I even brought up the topic. Thank you for posting the link. EDIT: I try not to post usernames in text, in case anyone ever changes their name. EDIT2: I recommend to always positively increment an iterator from 0 to n-1, and use in-loop arithmetics to get the actual desired iterator/index you require. It's less performant, but I'd argue mistakes are less common.

ses1984 7y ago

How long do you think it will take you to shuffle a list of size 2^64?