Масштабируемый алгоритм (Scalable Algorithm)
Алгоритм обработки данных называется масштабируемым, если его вычислительные затраты растут прямо пропорционально увеличению объема обрабатываемых данных. Т.е. при увеличении объема данных, например, в два раза количество вычислительных операций также увеличивается вдвое.
Кроме того, в аналитических технологиях масштабируемость подразумевает следующие свойства алгоритма:
- Однопроходность – алгоритм должен использовать не более одного прохода базы данных, при этом желательно, чтобы проход был завершён досрочно.
- Возможность отсечения по времени – алгоритм должен быть способен выдать наилучшее на данный момент решение в любой момент, даже если процесс вычислений не доводится до естественной остановки.
- Прерываемость и продолжаемость – алгоритм должен предусматривать возможность временной приостановки и продолжения работы. Промежуточные результаты должны быть сохраняемы с возможностью дальнейшего продолжения вычислений, а возможно и с использованием новых данных.
- Ограниченность по объему требуемой памяти – алгоритм должен работать в пределах ограниченного объема памяти компьютера, выделяемого пользователем.
- Однонаправленность – при проходе базы данных последовательность считывания записей производится только в одном направлении. Такой режим работы называется режимом однонаправленного указателя, когда указатель движется только вперед и без возможности обратного перемещения.
Особенно важным является свойство масштабируемости для алгоритмов, используемых при анализе Больших данных и в машинном обучении, где объем обучающих данных может быть очень велик.