One-pass algorithm

In computing, a one-pass algorithm or single-pass algorithm is a streaming algorithm which reads its input exactly once.[1] It does so by processing items in order, without unbounded buffering; it reads a block into an input buffer, processes it, and moves the result into an output buffer for each step in the process.[2] A one-pass algorithm generally requires O(n) (see 'big O' notation) time and less than O(n) storage (typically O(1)), where n is the size of the input.[3] An example of a one-pass algorithm is the Sondik partially observable Markov decision process.[4]

Example problems solvable by one-pass algorithms

Given any list as an input:

  • Count the number of elements.

Given a list of numbers:

Given a list of symbols from an alphabet of k symbols, given in advance.

  • Count the number of times each symbol appears in the input.
  • Find the most or least frequent elements.
  • Sort the list according to some order on the symbols (possible since the and after number of symbols is limited).
  • Find the maximum gap between two appearances of a given symbol.

Example problems not solvable by one-pass algorithms

Given any list as an input:

  • Find the nth element from the end (or report that the list has fewer than n elements).
  • Find the middle element of the list. However, this is solvable with two passes: Pass 1 counts the elements and pass 2 picks out the middle one.

Given a list of numbers:

  • Find the median.
  • Find the modes (This is not the same as finding the most frequent symbol from a limited alphabet).
  • Sort the list.
  • Count the number of items greater than or less than the mean. However, this can be done in constant memory with two passes: Pass 1 finds the average and pass 2 does the counting.

The two-pass algorithms above are still streaming algorithms but not one-pass algorithms.

References

  1. ^ Schweikardt, Nicole. "One-Pass Algorithm" (PDF). Retrieved 2021-07-01.
  2. ^ Pollett, Chris (2005-03-14). "One and Two Pass Algorithms" (PDF). Retrieved 2021-07-01.
  3. ^ Schweikardt, Nicole (2009), "One-Pass Algorithm", in LIU, LING; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems, Boston, MA: Springer US, pp. 1948–1949, doi:10.1007/978-0-387-39940-9_253, ISBN 978-0-387-39940-9, retrieved 2021-04-13
  4. ^ "Sondik's One-Pass Algorithm". www.pomdp.org.
Stub icon

This computer science article is a stub. You can help Wikipedia by adding missing information.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.