Jump to content

Talk:One-pass algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]

Potential citations

[edit]

I'm not great at reading these sorts of in-depth computer science books/papers, but it seems like these references would be helpful in expanding the article further, if someone wants a crack at it:

Hope this helps //Lollipoplollipoplollipop::talk 05:38, 15 April 2021 (UTC)[reply]