Алгоритм маляра Шлемиэля

Материал из свободной русской энциклопедии «Традиция»
(перенаправлено с «Маляр Шлемиэль»)
Перейти к: навигация, поиск

Алгори́тм маляра́ Шлемиэ́ля — неэффективный алгоритм действий, связанный с заметным (нелинейным) ростом усилий по мере возрастания объёма работ.

Название алгоритму дал Джоэл Спольски в 2001 году в статье «Back to Basics» (в русском переводе — «Назад, к основам»), процитировав следующий анекдот:

Aquote1.png Маляр Шлемиэль подрядился красить пунктирные осевые линии на дорогах. В первый день он получил банку краски, поставил её на дорогу, и к концу дня покрасил 300 метров осевой линии. «Отлично! — сказал прораб. — Быстро работаешь!» — и заплатил ему копейку.

На следующий день Шлемиэль покрасил 150 метров. «Мда, это, конечно, не так здорово, как вчера, но приемлемо», — сказал прораб и заплатил ему копейку.

На следующий день Шлемиэль покрасил 30 метров. «Всего лишь 30! — заорал прораб. — Это никуда не годится! В первый день было в десять раз больше! В чём дело?»

«Ничего не могу поделать, — говорит Шлемиэль. — Каждый день я ухожу всё дальше и дальше от банки!»

Aquote2.png

Как подметил Джоэл Спольски, подобные неэффективные алгоритмы нередко используется при обработке нуль-терминированных строк и других подобных структур данных, в которых размер строки не известен заранее (например, файлов XML).