Quote:
Originally Posted by gaming_mouse
candy, i don't see any way you could avoid having all N^2 numbers in memory at some point, since you have to have one of each randomly distributed across all the cells, and even if you are filling the cells on demand you have to keep track of which have been filled so you don't re-use the same number. but maybe i'm a bad internet nerd?
Assuming that all you care is that every result be computed and you're willing to wait till it's done, you're correct. But sometimes we care about the order in which things are computed and may not even care about some results. And you may need some results back quickly. For example, you may need the following to run instantly:
var arr = makeRandom2DArray(50000);
var n1 = arr(15325, 32455);
var n2 = arr(8634, 24423);
var n3 = arr(34342, 5454);
var n4 = arr(1264, 3);
maybe you're done after this. Or maybe you need all results eventually, but need specific results before your application appears frozen. Now, it's equally easy to make things super-efficient for the sparse case where only a few results are ever used. But a naive implementation of the sparse/lazy array will be terrible if the user needs everything.
The hard problem is how do you go smoothly from the sparse to dense such that on an amortized and asymptotic basis, you haven't made it any worse than the naive implementation.