Однопроходный алгоритм - One-pass algorithm

В вычислениях однопроходный алгоритм или однопроходный алгоритм - это алгоритм потоковой передачи, который считывает входные данные ровно один раз. Это достигается путем обработки элементов по порядку без неограниченной буферизации ; он считывает блок во входной буфер , обрабатывает его и перемещает результат в выходной буфер для каждого шага процесса. Однопроходный алгоритм обычно требует времени O ( n ) (см. Обозначение «большой O» ) и меньше O ( n ) памяти (обычно O (1)), где n - размер входных данных. Примером однопроходного алгоритма является частично наблюдаемый марковский процесс принятия решения Сондиком .

Примеры задач, решаемых с помощью однопроходных алгоритмов

Учитывая любой список в качестве входных данных:

  • Подсчитайте количество элементов.

Учитывая список чисел:

Дан список символов из алфавита из k символов, данный заранее.

  • Подсчитайте, сколько раз каждый символ появляется во входных данных.
  • Найдите наиболее или наименее частые элементы.
  • Отсортируйте список в соответствии с некоторым порядком символов (возможно, поскольку количество символов ограничено).
  • Найдите максимальный промежуток между двумя появлением данного символа.

Примеры задач, не решаемых с помощью однопроходных алгоритмов

Учитывая любой список в качестве входных данных:

  • Найдите n- й элемент с конца (или сообщите, что в списке меньше n элементов).
  • Найдите средний элемент списка. Однако это решается двумя проходами: проход 1 считает элементы, а проход 2 выбирает средний.

Учитывая список чисел:

  • Найдите медиану .
  • Найдите режимы (это не то же самое, что найти наиболее часто встречающийся символ из ограниченного алфавита).
  • Отсортируйте список.
  • Подсчитайте количество элементов больше или меньше среднего . Однако это можно сделать в постоянной памяти за два прохода: первый проход находит среднее значение, а второй - подсчет.

Вышеупомянутые двухпроходные алгоритмы по- прежнему являются алгоритмами потоковой передачи, но не однопроходными.

Рекомендации

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