111–120 of 200 posts
So let me get this straight... This algorithm creates an initially empty array of size K with the DB internal ids of what would randomly be selected. Then it goes in order from 0 to the number of rows - 1, and for each one it goes e.g. "What are the chances that number 0 would get randomly picked out of N items if K items need to be picked?" Then, if the #0 passes the "random check", it gets added. Then it would go t…
The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.
This works, but only if you're sampling the exact same space as the block size. For example, if your cipher outputs 64-bit blocks, but you want to sample in 2^32, you're back to the drawing board, because there's no way to truncate the cipher output without risking duplicates.
However, you can also use a Feistel network to create a block cipher for an arbitrary bit length. So, you can always bound the block space to be no more than twice the sampling space, which is okay.
The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.
The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.
Earlier quoted context omitted.
In general, assuming that we have constant-time operations on arbitrarily large numbers (which we almost universally assume when doing these analyses, except in very specific fields), then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Additionally, the only problem with this approach is the extra O(k) space taken up by…
> then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Hashtables can never guarantee constant time operations. It is expected O(1) time, but it is completely possible that everything hashes to the same bucket and you get O(n) operations, no matter how much you rehash.
A bit mask is a form of hash table and is guaranteed O(1) lookup for O(lg(Universe)) space.
When you have fixed universes, all kinds of options open up. I personally love vEB Trees, which can do set operations in O(lg(lg(U)))
While reading, I was thinking about LFSR [0] with suitable properties and period. Not strictly random, although LFSRs are commonly used for generating "random" numbers. [0]: https://en.wikipedia.org/wiki/Linear-feedback_shift_register
Some of the variable names used: i, j, t, qu1, S, n, N, U, X, y1, y2, V I know others have already commented on this but I think it's worth laying out all of the cryptic variables and asking: are some of these shorthand for well known math concepts that make it unnecessary to have a more descriptive name? I understand the use of temporary value holders like `i`, but have no clue what some of the others might be used…
I don't have an answer, but I remember Go programmers on Quora swearing up and down that (the Go convention of) using single-letter variables is ingenius and leads to great code ... although none of them could give a single example.
Go convention is often short variable names, but the only place I know where single-letter variable names is encourage is for receiver methods. https://golang.org/doc/effective_go.html#methods
In that case the definition of the single-letter variable is literally a line or two of code away.
Earlier quoted context omitted.
I don't have an answer, but I remember Go programmers on Quora swearing up and down that (the Go convention of) using single-letter variables is ingenius and leads to great code ... although none of them could give a single example.
This is a bad take and odd place to criticize Go programmers. Go convention is often short variable names, but the only place I know where single-letter variable names is encourage is for receiver methods. https://golang.org/doc/effective_go.html#methods In that case the definition of the single-letter variable is literally a line or two of code away.
Earlier quoted context omitted.
Trivial algorithms (like one implemented in Python) slow down when k is close to n. Or when n is large, then it is not possible to use bitmap to mark dealt cards.
What's preventing someone from implementing a non-trivial algorithm in Python?
The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.