Однопроходный алгоритм - One-pass algorithm
В вычислениях однопроходный алгоритм или однопроходный алгоритм - это алгоритм потоковой передачи, который считывает входные данные ровно один раз. Это достигается путем обработки элементов по порядку без неограниченной буферизации ; он считывает блок во входной буфер , обрабатывает его и перемещает результат в выходной буфер для каждого шага процесса. Однопроходный алгоритм обычно требует времени O ( n ) (см. Обозначение «большой O» ) и меньше O ( n ) памяти (обычно O (1)), где n - размер входных данных. Примером однопроходного алгоритма является частично наблюдаемый марковский процесс принятия решения Сондиком .
Примеры задач, решаемых с помощью однопроходных алгоритмов
Учитывая любой список в качестве входных данных:
- Подсчитайте количество элементов.
Учитывая список чисел:
- Найдите k наибольших или наименьших элементов, k заданных заранее.
- Найдите сумму , среднее значение , дисперсию и стандартное отклонение элементов списка. См. Также « Алгоритмы расчета дисперсии» .
Дан список символов из алфавита из k символов, данный заранее.
- Подсчитайте, сколько раз каждый символ появляется во входных данных.
- Найдите наиболее или наименее частые элементы.
- Отсортируйте список в соответствии с некоторым порядком символов (возможно, поскольку количество символов ограничено).
- Найдите максимальный промежуток между двумя появлением данного символа.
Примеры задач, не решаемых с помощью однопроходных алгоритмов
Учитывая любой список в качестве входных данных:
- Найдите n- й элемент с конца (или сообщите, что в списке меньше n элементов).
- Найдите средний элемент списка. Однако это решается двумя проходами: проход 1 считает элементы, а проход 2 выбирает средний.
Учитывая список чисел:
- Найдите медиану .
- Найдите режимы (это не то же самое, что найти наиболее часто встречающийся символ из ограниченного алфавита).
- Отсортируйте список.
- Подсчитайте количество элементов больше или меньше среднего . Однако это можно сделать в постоянной памяти за два прохода: первый проход находит среднее значение, а второй - подсчет.
Вышеупомянутые двухпроходные алгоритмы по- прежнему являются алгоритмами потоковой передачи, но не однопроходными.
Рекомендации
- ^ Швейкардт, Николь. «Однопроходный алгоритм» (PDF) . Проверено 1 июля 2021 .
- ^ Поллетт, Крис (2005-03-14). «Одно- и двухпроходные алгоритмы» (PDF) . Проверено 1 июля 2021 .
- ^ Швейкардт, Николь (2009), ЛИУ, ЛИНГ; Озсу, М. ТАМЕР (ред.), « Однопроходный алгоритм» , Энциклопедия систем баз данных , Бостон, Массачусетс: Springer US, стр. 1948–1949, DOI : 10.1007 / 978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, получено 2021-04-13
- ^ "Однопроходный алгоритм Сондика" . www.pomdp.org .