Talk:One-pass algorithm

There's a subtle point here regarding buffering, but I believe that my definition and examples are OK.

Strictly speaking, one-pass would appear to mean you read the input once. But that would seem to allow for simply making an in-memory copy and doing whatever you like as many times as you like. So an algorithm is only meaningfully one-pass if it's buffer space is independent of the input size. I forget whether there is a more exact term for this.

Knuth's Art of Computer Programming has a long section on sorting and such using tapes. While the technology is obsolete, the idea that you might have a list of things longer than fits in memory is still valid (e.g., you have a gazillion bytes in a database table but only half a gazillion bytes of disk to use for virtual memory -- for that matter if VM is ridiculously large then the swapping is essentially the same as multiple passes).

So when I assert that, say, finding the modes can't be done one-pass, I believe that's right, but the counterexample is a bit subtle: Take n two elements larger than will fit in available memory. Any general-purpose mode-finding algorithm that only reads the input once will run out of memory on (say) a list that consists of some permutation of 1 .. n - 1 followed by some number in that range, because as it processes the last number it will have to remember that n - 1 numbers have each occured once so far. -Dmh 21:28, 4 January 2007 (UTC)