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 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)

Potential citations

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:

• The Art of Computer Programming, chapter 1.4.3 Coroutines http://broiler.astrometry.net/~kilian/The_Art_of_Computer_Programming%20-%20Vol%201.pdf
• Comparison of Several Algorithms for Computing Sample Means and Variances https://www.jstor.org/stable/2286154
• Approximate Medians and other Quantiles in One Pass and with Limited Memory http://www.cs.umd.edu/~samir/498/manku.pdf
• Algorithms for Computing the Sample Variance: Analysis and Recommendations http://www.cs.yale.edu/publications/techreports/tr222.pdf
• Also seems possible to find a lot of papers called some variation of "A one pass algorithm for [problem]". Worth adding those problems with citations to the examples section? E.g.:
  • One-Pass Algorithms for Some Generalized Network Problems https://pubsonline.informs.org/doi/abs/10.1287/opre.14.5.914
  • An Integer One-Pass Algorithm for Voxel Traversal https://diglib.eg.org/handle/10.2312/10078
  • One-pass Algorithms for Large and Shifting Data Sets https://www.researchgate.net/publication/44385001_One-pass_Algorithms_for_Large_and_Shifting_Data_Sets
  • A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data http://www.vldb.org/conf/1997/P346.PDF
  • A complexity-efficient and one-pass image compression algorithm for wireless capsule endoscopy https://pubmed.ncbi.nlm.nih.gov/26410489/

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