In computing, a one-pass algorithm or single-pass algorithm is a

streaming algorithm In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically one-pass algorithm, just one. These algorithms are desi ...

which reads its input exactly once. It does so by processing items in order, without unbounded buffering; it reads a block into an

input buffer In computer science, a data buffer (or just buffer) is a region of memory used to store data temporarily while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device (such as ...

, processes it, and moves the result into an output buffer for each step in the process. 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. An example of a one-pass algorithm is the Sondik

partially observable Markov decision process A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process (MDP). A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot ...

Example problems solvable by one-pass algorithms

Given any list as an input: * Count the number of elements. Given a list of numbers: * Find the ''k'' largest or smallest elements, ''k'' given in advance. * Find the sum,

mean A mean is a quantity representing the "center" of a collection of numbers and is intermediate to the extreme values of the set of numbers. There are several kinds of means (or "measures of central tendency") in mathematics, especially in statist ...

variance In probability theory and statistics, variance is the expected value of the squared deviation from the mean of a random variable. The standard deviation (SD) is obtained as the square root of the variance. Variance is a measure of dispersion ...

and

standard deviation In statistics, the standard deviation is a measure of the amount of variation of the values of a variable about its Expected value, mean. A low standard Deviation (statistics), deviation indicates that the values tend to be close to the mean ( ...

of the elements of the list. See also

Algorithms for calculating variance Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical insta ...

. 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 ''n''th 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 The median of a set of numbers is the value separating the higher half from the lower half of a Sample (statistics), data sample, a statistical population, population, or a probability distribution. For a data set, it may be thought of as the “ ...

. * Find the

modes Mode ( meaning "manner, tune, measure, due measure, rhythm, melody") may refer to: Arts and entertainment * MO''D''E (magazine), a defunct U.S. women's fashion magazine * ''Mode'' magazine, a fictional fashion magazine which is the setting fo ...

(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

. 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 In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically one-pass algorithm, just one. These algorithms are desi ...

but not one-pass algorithms.

References

{{DEFAULTSORT:One-Pass Algorithm Streaming algorithms