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 ...
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 a memory used to temporarily store data 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 a ...
, 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
Sum most commonly means the total of two or more numbers added together; see addition.
Sum can also refer to:
Mathematics
* Sum (category theory), the generic concept of summation in mathematics
* Sum, the result of summation, the additio ...
, 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 '' ari ...
, 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 number ...
and standard deviation 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 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.
* 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 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 '' ari ...
. 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 just one). In most models, these algorithms have access t ...
but not one-pass algorithms.
References