Что означает Алгоритм маляра Шлемиля?
Алгоритм маляра Шлемиля. Кто такой Шле-миль? Это малый из следующего анекдота:
Шлемиль устроился на работу маляром и должен был наносить разметку посредине дороги. В первый день он взял бочку краски и разметил 300 метров дороги. «Неплохо! - сказал босс. - Ты быстро работаешь!» И заплатил ему денежку.
На следующий день Шлемиль осилил только 150 метров. «Ну что ж, не так здорово, как вчера, но ты все равно быстро работаешь. 150 метров - это не мало», - сказал босс и заплатил ему денежку. Еще через день Шлемиль расчертил 30 метров дороги.
«Всего 30 метров!» - рассвирепел босс. - Это никуда не годится. В первый день ты сделал в десять раз больше. Что случилось?»
«Ничего не могу поделать, - говорит Шлемиль. - С каждым днем приходится все дальше и дальше уходить от бочки с краской».
Этот неважный анекдот в точности иллюстрирует механизм соединения строк в функции strcat. Поскольку функции приходится каждый раз просматривать всю результирующую строку и искать этот проклятый завершающий нуль, она работает гораздо медленнее, чем в действительности необходимо, и очень плохо масштабируется. Масса кода, с которым вы сталкиваетесь ежедневно, содержит эту проблему. Многие файловые системы реализованы таким образом, что при работе с ними не рекомендуется помещать в один каталог много файлов, т. к. это резко снижает производительность. Попробуйте открыть в Windows заполненную мусорную корзину, и вы увидите, сколько для этого требуется времени, которое явно увеличивается с ростом количества файлов нелинейным образом. Где-то там спрятался алгоритм маляра Шлемиля. Всякий раз, когда чувствуется, что время должно быть линейным, а оно оказывается порядка n-квадрат, ищите Шлемиля. Часто библиотеки функций скрывают от вас это обстоятельство. Сразу и не скажешь, что вызовы strcat, помещенные в цикл или просто расположенные один под другим, вопиют «n-квадрат!», хотя именно так оно и есть в действительности.
Именно из-за алгоритма Шлемиля некая программа могла иметь уязвимость в виде переполнения буфера. Это было главной причиной взломов и червей в те достопамятные времена, когда Microsoft Outlook еще не сделал хакинг доступным даже подросткам.
Шлемиль устроился на работу маляром и должен был наносить разметку посредине дороги. В первый день он взял бочку краски и разметил 300 метров дороги. «Неплохо! - сказал босс. - Ты быстро работаешь!» И заплатил ему денежку.
На следующий день Шлемиль осилил только 150 метров. «Ну что ж, не так здорово, как вчера, но ты все равно быстро работаешь. 150 метров - это не мало», - сказал босс и заплатил ему денежку. Еще через день Шлемиль расчертил 30 метров дороги.
«Всего 30 метров!» - рассвирепел босс. - Это никуда не годится. В первый день ты сделал в десять раз больше. Что случилось?»
«Ничего не могу поделать, - говорит Шлемиль. - С каждым днем приходится все дальше и дальше уходить от бочки с краской».
Этот неважный анекдот в точности иллюстрирует механизм соединения строк в функции strcat. Поскольку функции приходится каждый раз просматривать всю результирующую строку и искать этот проклятый завершающий нуль, она работает гораздо медленнее, чем в действительности необходимо, и очень плохо масштабируется. Масса кода, с которым вы сталкиваетесь ежедневно, содержит эту проблему. Многие файловые системы реализованы таким образом, что при работе с ними не рекомендуется помещать в один каталог много файлов, т. к. это резко снижает производительность. Попробуйте открыть в Windows заполненную мусорную корзину, и вы увидите, сколько для этого требуется времени, которое явно увеличивается с ростом количества файлов нелинейным образом. Где-то там спрятался алгоритм маляра Шлемиля. Всякий раз, когда чувствуется, что время должно быть линейным, а оно оказывается порядка n-квадрат, ищите Шлемиля. Часто библиотеки функций скрывают от вас это обстоятельство. Сразу и не скажешь, что вызовы strcat, помещенные в цикл или просто расположенные один под другим, вопиют «n-квадрат!», хотя именно так оно и есть в действительности.
Именно из-за алгоритма Шлемиля некая программа могла иметь уязвимость в виде переполнения буфера. Это было главной причиной взломов и червей в те достопамятные времена, когда Microsoft Outlook еще не сделал хакинг доступным даже подросткам.
Оставить свой ответ:
