Content-Type: text/shitpost

Abigail has presented a convincing argument that the sampling algorithm I asked for does not exist.

Suppose the algorithm has read the first !!N!! items. It does not yet know how many there will be in all; there might be !!2N!!. But if there are !!2N!!, there is a positive probability that the !!N!! it has read are exactly the !!N!! it will emit, and the only way it can do this is if it has retained all !!N!! in memory.

But if it has retained all !!N!! in memory, and then discovers that there are no more to read, it has exceeded the memory bounds. (Or rather, it must since the argument is the same for all !!N!!.)

This rules out not only a sublinear memory bound, but any result that would use less memory than reading all the items into a buffer.