The "highest score" version of the random selection algorithm reminds me of a similar algorithm for parallel graph coloring:
Each graph node gets assigned a random number as a score. While there are uncolored nodes, assign a new color to all nodes with a score higher than all its neighbors. Repeat until all nodes are colored.
In each iteration, no two adjacent nodes are chosen, since one would have a higher score than the other (assuming some tie-breaking scheme), and therefore all nodes chosen in an iteration can be assigned the same color.
Using the score comparisons to decide which nodes to color in each iteration allows the algorithm to parallelize nicely since every node can be checked fully independently based on the read-only scores.
The algorithm doesn't make any optimality guarantees for the coloring, but it is intuitive and has minimal synchronization, so it works well with large numbers of cores.
This expert-to-expert format exposes a particularly rich seam of historical context and technical information.
I understand not every influential long-timer can sit an interview for 3+ hours. Nevertheless, you are, perhaps, uniquely positioned to do this type of thing well, and I welcome whatever further contributions you're willing to make to posterity in this vein.
If we do happen to go through an LLM-induced Dark Age in programming, then may this oeuvre fuel the Rennaissance.
I worked out how to generalize this for weighted randomness, which is to let
float score = pow(random_float(), 1.0/weight)
with the downsides of needing to compute the pow and increased bias due to floating point precision.
If w is an integer, score=x^(1/w) gives a distribution equivalent to performing w rolls and taking the best value, and you can verify that it works for non-integers with some integration.
The 1/count version is still probably better if you need weighted randomness, since it just does a replacement with probability weight/total_weight_so_far, which is just a couple multiplies instead of a pow.
The "highest score" version of the random selection algorithm reminds me of a similar algorithm for parallel graph coloring:
Each graph node gets assigned a random number as a score. While there are uncolored nodes, assign a new color to all nodes with a score higher than all its neighbors. Repeat until all nodes are colored.
In each iteration, no two adjacent nodes are chosen, since one would have a higher score than the other (assuming some tie-breaking scheme), and therefore all nodes chosen in an iteration can be assigned the same color.
Using the score comparisons to decide which nodes to color in each iteration allows the algorithm to parallelize nicely since every node can be checked fully independently based on the read-only scores.
The algorithm doesn't make any optimality guarantees for the coloring, but it is intuitive and has minimal synchronization, so it works well with large numbers of cores.
I heard about this algorithm from this post, which has some more details: https://developer.nvidia.com/blog/graph-coloring-more-parallelism-for-incomplete-lu-factorization/
This expert-to-expert format exposes a particularly rich seam of historical context and technical information.
I understand not every influential long-timer can sit an interview for 3+ hours. Nevertheless, you are, perhaps, uniquely positioned to do this type of thing well, and I welcome whatever further contributions you're willing to make to posterity in this vein.
If we do happen to go through an LLM-induced Dark Age in programming, then may this oeuvre fuel the Rennaissance.
Neat algorithm!
I worked out how to generalize this for weighted randomness, which is to let
float score = pow(random_float(), 1.0/weight)
with the downsides of needing to compute the pow and increased bias due to floating point precision.
If w is an integer, score=x^(1/w) gives a distribution equivalent to performing w rolls and taking the best value, and you can verify that it works for non-integers with some integration.
The 1/count version is still probably better if you need weighted randomness, since it just does a replacement with probability weight/total_weight_so_far, which is just a couple multiplies instead of a pow.
If you wanted the T-SQL pseudocode:
SELECT TOP(1) Thing
FROM Things
WHERE IsValid = 1
ORDER BY NEW_ID()
For SQL newbies, the above code is better thought as running in the following logical order:
FROM, WHERE, ORDER, TOP, SELECT