One-pass algorithm: Difference between revisions
From EverybodyWiki Bios & Wiki
Moved page from wikipedia:en:One-pass algorithm (history) |
m remove duplicates internal links |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 6: | Line 6: | ||
{{Refimprove|date=April 2021}} | {{Refimprove|date=April 2021}} | ||
In computing, a '''one-pass algorithm''' or '''single-pass algorithm''' is a [[streaming algorithm]] which reads its input exactly once | In computing, a '''one-pass algorithm''' or '''single-pass algorithm''' is a [[streaming algorithm]] which reads its input exactly once.<ref name="frankfurt"/> It does so by processing items in order, without unbounded [[Buffer (computer science)|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.<ref name="sjsu"/> A one-pass algorithm generally requires ''O''(''n'') (see [[Big O Notation|'big O' notation]]) time and less than ''O''(''n'') storage (typically ''O''(1)), where ''n'' is the size of the input.<ref name="eds"/> An example of a one-pass algorithm is the Sondik partially observable [[Markov decision process]].<ref name="pomdp"/> | ||
==Example problems solvable by one-pass algorithms== | ==Example problems solvable by one-pass algorithms== | ||
| Line 16: | Line 16: | ||
* Find the [[summation|sum]], [[mean]], [[variance]] and [[standard deviation]] of the elements of the list. See also [[Algorithms for calculating variance]]. | * Find the [[summation|sum]], [[mean]], [[variance]] and [[standard deviation]] of the elements of the list. See also [[Algorithms for calculating variance]]. | ||
Given a list of symbols from an alphabet of ''k'' symbols, given in advance | 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. | * Count the number of times each symbol appears in the input. | ||
* Find the most or least frequent elements. | * Find the most or least frequent elements. | ||
| Line 25: | Line 25: | ||
Given any list as an input: | 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 ''n''th element from the end (or report that the list has fewer than ''n'' elements). | ||
* Find the middle element of the list. | * 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: | Given a list of numbers: | ||
| Line 31: | Line 31: | ||
* Find the [[mode (statistics)|modes]] (This is not the same as finding the most frequent symbol from a limited alphabet). | * Find the [[mode (statistics)|modes]] (This is not the same as finding the most frequent symbol from a limited alphabet). | ||
* Sort the list. | * Sort the list. | ||
* Count the number of items greater than or less than the | * 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 | The two-pass algorithms above are still streaming algorithms but not one-pass algorithms. | ||
== References== | == References== | ||
<references/> | <references> | ||
<ref name="eds">{{Citation|last=Schweikardt|first=Nicole|title=One-Pass Algorithm|date=2009|url=https://doi.org/10.1007/978-0-387-39940-9_253|work=Encyclopedia of Database Systems|pages=1948–1949|editor-last=LIU|editor-first=LING|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_253|isbn=978-0-387-39940-9|access-date=2021-04-13|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref> | |||
<ref name="frankfurt">http://www.tks.informatik.uni-frankfurt.de/schweika/downloads/EncycDBS_OnePassAlgos.pdf{{Dead link|date=May 2026 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> | |||
<ref name="sjsu">http://www.cs.sjsu.edu/faculty/pollett/157b.12.05s/Lec14032005.pdf</ref> | |||
<ref name="pomdp">{{Cite web|url=http://www.pomdp.org/tutorial/sondik.html|title=Sondik's One-Pass Algorithm|website=www.pomdp.org}}</ref> | |||
</references> | |||
{{cs-stub}} | {{cs-stub}} | ||
| Line 45: | Line 50: | ||
[[Category:Streaming algorithms]] | [[Category:Streaming algorithms]] | ||
{{Source Wikipedia}} | {{Source Wikipedia}} | ||
{{Kept on Wikipedia|Biggest version}} | |||
Latest revision as of 05:09, 18 August 2026
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:
- Find the k largest or smallest elements, k given in advance.
- Find the sum, mean, variance and standard deviation of the elements of the list. See also Algorithms for calculating variance.
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 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
- ↑ http://www.tks.informatik.uni-frankfurt.de/schweika/downloads/EncycDBS_OnePassAlgos.pdf[permanent dead link]
- ↑ http://www.cs.sjsu.edu/faculty/pollett/157b.12.05s/Lec14032005.pdf
- ↑ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER, eds., "One-Pass Algorithm", 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
- ↑ "Sondik's One-Pass Algorithm". www.pomdp.org.
 | This computer science article is a stub. You can help EverybodyWiki by expanding it. |
This article "One-pass algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:One-pass algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
|
This page exists already on Wikipedia. |
