4 ms·
If it were up to me, I'd implement something sort of like an online[0] Fisher-Yates shuffle: Add a column to the article database for "random_index". This give
by munificent 3y ago
If it were up to me, I'd implement something sort of like an online[0] Fisher-Yates shuffle:
Add a column to the article database for "random_index". This gives each article a unique integer index within a consecutive range of 1 to N. To pick a random article, just pick a random number in that range using your favorite random number generator and then look up the row with that random_index value.
The tricky part, obviously, is maintaining the invariant that random index values are (1) randomly assigned and (2) contiguous. To maintain those, I believe it's enough to:
1. Whenever a new article is created, give it random_index N+1. Then choose a random number in the range (1, N+1). Swap the random_index of the new article and the article whose random_index is the number you just rolled. This is the Fisher-Yates step that gives you property (1).
2. Whenever an article is deleted or otherwise removed from the set of articles that can be randomly selected, look up the article with random_index N. Set that article's random_index to the random_index of the article about to be deleted. This gives you property (2).
[0]: https://en.wikipedia.org/wiki/Online_algorithm https://en.wikipedia.org/wiki/Online_algorithm
- crazygringo 3y agoOh wow, yup that will do it. That was my second suggestion for what is "correct" but I never heard of your #2 suggestion, so I thought there would still be performance issues because you'd have to shift all the values above. I'm kind of annoyed now I didn't know about this before... :) Yes, this should definitely considered to be the correct, definitive, performant solution then. Thank you! I think you'll need a full table lock in the case of a race condition trying to do a remove and add at the same time, but that's probably not usually going to be an issue?
- munificent 3y agoActually, now that I think about it, step 1 isn't necessary. You don't actually need to shuffle the indexes since you always choose a random one anyway. It should be enough to just do the swap on deletes in order to keep the integers contiguous. > I think you'll need a full table lock in case you're ever trying to do a remove and add at the same time Yeah, I think you need some sort of locking to ensure N can't be concurrently modified but I'm not a DB person, so I don't know how to go about that.
- crazygringo 3y agoYup, agreed on step 1. Basic autoincrement is perfectly fine, since you pick a random number at query time.
- Levitating 3y agoWhat an incredibly simple solution for something that was just deemed rocket science. Also I liked your book.
- jprete 3y agoThanks to both of you for pointing out some quite good solutions to this problem.
- stcg 3y agoThis is the nicest solution I've seen so far. I believe that for the operation of randomly sampling a single row, only the consecutiveness invariant is needed. The random permutation invariant is unnecessary, because the choice from the range (1, N+1) is random anyway. However, I can imagine the random permutation invariant being useful for other operations (although I can't immediately think of one). EDIT: the random permutation invariant could maybe be useful for a list that can be displayed to the user. I can imagine some cases where it is nice to have an order that doesn't change a lot while you don't want it to depend on any property in particular (like the order in which the rows were added).
- karmanyaahm 3y ago2 is exactly how removal from sets is O(1) whereas lists are O(N)
- chasd00 3y agoyou probably don't even need 2. If your select with a random number N returns null then increment to N+1 and select again. You'll find one eventually.
- jprete 3y agoI think that’s got a similar bias as the original, unfortunately. All deleted indices between K and N (K<N) will result in picking N, and the number of such deletions would vary wildly between individual articles.
- shpx 3y agoWhat we actually have though are thousands (potentially millions) of well-fed human brains which are volunteering their downtime in a particular moment of their life to receive factual information of any kind (of the kind they expect to see on Wikipedia) in the hopes of getting something good. A system that chose the best possible article to present to them in that moment to bend the course of their life in a good direction or satisfy some need (or attempt/pretend to satisfy, as much as we can by shooting photons at their retinas) would be a better engineered system than one that randomly selects from its entire catalog of options correctly and efficiently.