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 just one). In most models, these algorithms have access t ...

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, 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 There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value (magnitude and sign) of a given data set. For a data set, the ''arithme ...

variance In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its population mean or sample mean. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers ...

and

standard deviation In statistics, the standard deviation is a measure of the amount of variation or dispersion of a set of values. A low standard deviation indicates that the values tend to be close to the mean (also called the expected value) of the set, while ...

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 instab ...

. 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 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 In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...

. * Find the

modes Mode ( la, modus 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 ...

(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 but not one-pass algorithms.

References

{{DEFAULTSORT:One-Pass Algorithm Streaming algorithms