Talk:One-pass algorithm

Computing Stub‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

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 its 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 n - 1 distinct numbers, followed by one of those numbers again. As it processes the last number it will have to remember the n - 1 numbers that have each occured once so far, but there is only room for n - 2. -Dmh 21:28, 4 January 2007 (UTC)[reply]