Однопроходной алгоритм

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

Примеры задач, решаемых однопроходными алгоритмами

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

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

Дан список чисел:

Найдите k крупнейших или наименьших элементов, k задано заранее.
Найдите сумму , среднее значение , дисперсию и стандартное отклонение элементов списка. См. также Алгоритмы расчета дисперсии .

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

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

Примеры задач, не решаемых однопроходными алгоритмами

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

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

Дан список чисел:

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

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

Ссылки

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

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[frankfurt-1] Швейкардт, Николь. «Однопроходной алгоритм» (PDF) . Проверено 1 июля 2021 г.

[sjsu-2] Поллетт, Крис (14 марта 2005 г.). «Одно- и двухпроходные алгоритмы» (PDF) . Проверено 1 июля 2021 г.

[eds-3] Швейкардт, Николь (2009), «Однопроходной алгоритм» , в LIU, LING ; ОЗСУ, М. ТЭМЕР (ред.), Энциклопедия систем баз данных , Бостон, Массачусетс: Springer US, стр. 1948–1949, doi : 10.1007/978-0-387-39940-9_253 , ISBN 978-0-387-39940-9 , получено 13 апреля 2021 г.

[pomdp-4] «Однопроходной алгоритм Сондика» . www.pomdp.org .

[1]

[2]

[3]

[4]