?

Log in

No account? Create an account

Меняю память на время, торг уместен - Общество дровосеков Бердичева по изучению Мишны

May. 31st, 2017

12:00 pm - Меняю память на время, торг уместен

Previous Entry Share Next Entry

Когда деревья были большими, а память в компьютерах - маленькой, дети развлекались написанием программ на языке BASIC. Язык был простой и незамысловатый, но с появлением пиксельной графики на микрокомпьютерах и, соответственно, операторов отрисовки точек, отрезков и дуг окружностей или эллипсов, какая-то добрая душа добавила в язык и оператор закраски замкнутой области (PAINT или FILL).

Ну а что ж, надо же как-то удобно рисовать закрашенные кружочки и многоугольнички?

Одни разработчики были умные. Они решили сделать так: перед рисованием контура фигуры программист должен сказать "приготовься закрашивать то, что я сейчас буду рисовать", а после окончания рисования контура - "давай закрашивай". Фигура при этом должна быть "выпуклая по горизонтали", т.е. пересечение любой горизонтальной прямой и контура должно быть не более чем две точки или отрезка (а если кто не читает инструкции, тот ССЗБ). Процедура закраски должна всего лишь запоминать, какие были самая левая и самая правая точки контура в каждой строке экрана, и по заключительной команде закрасить всё между ними.
Алгоритм простой, памяти много не требует, но рисовать таким образом, например, кремлевскую стену довольно утомительно.

Другие разработчики были хитрые. Они решили сделать так: операция закраски будет пытаться красить любые фигуры, пользуясь стеком или очередью для запоминания, в какие закоулки нужно не забыть зайти, а если фигура окажется слишком сложная, и алгоритму потребуется больше временной памяти, чем есть, то программа или вылетит по ошибке нехватки памяти (если основное качество разработчика было laziness), или фигура не докрасится до конца (если основное качество разработчика было impatience) или машина зависнет/рестартует (если основное качество разработчика было hubris).
Алгоритм простой, быстрый, но перекрашивать таким образом, например, случайно сгенерированный лабиринт довольно рискованно.

Третьи разработчики были добрые. Они решили сделать так: операция закраски будет пытаться красить любые фигуры, пользуясь фиксированным количеством памяти, а если фигура окажется слишком сложная, то нефиг было программисту выпендриваться — подождёт.
Алгоритм совершенно бешеный, и описание на естественном языке, и псевдокод; и на многосвязных фигурах медленный, как моя жизнь. Курсор бегает по лабиринту кругами, как крыса, а толку через час по чайной ложке (скажем, для закраски квадрата 50х50 с 13% случайно расставленных точек может потребоваться больше 100 тысяч шагов).
В псевдокоде особенно восхищает вот это:

cur, mark, and mark2 each hold either pixel coordinates or a null value
         NOTE: when mark is set to null, do not erase its previous coordinate value.
               Keep those coordinates available to be recalled if necessary.

(Поняли теперь, как nullable references должны быть устроены?)

Самое смешное, что алгоритм всё же действительно работает.

This entry was originally posted at http://spamsink.dreamwidth.org/1051338.html. Please comment there using OpenID.

Comments:

From:pigdeon
Date:May 31st, 2017 09:04 pm (UTC)
(Link)
В большинстве архитектур существовал "приоритетный порядок обхода", поэтому распространение получили именно алгоритмы со сканированием строки. Они, кстати, могут быть адаптированы для ограниченной памяти за счёт большего числа проверок. Я также видел разновидность алгоритма со "спиральной" заливкой, когда проверка идет вдоль контура залитого поля. Наблюдать за его работой было любопытно, хотя и утомительно.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 31st, 2017 09:17 pm (UTC)
(Link)
Алгоритмы со сканированием строки тоже пользуются стеком или очередью, требующими потенциально O(height*width) памяти.
Разновидность алгоритма со "спиральной" заливкой - это в точности то, что я описываю как третий вариант. Именно "любопытно, хотя и утомительно".

А вот сочетания "спиральной" заливки и сканирования строк, чтобы памяти требовалось линейное количество, и работало относительно быстро на фигуре любой сложности, я не встречал.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:May 31st, 2017 09:26 pm (UTC)
(Link)
Практически пасхальная история. Только разработчики должны делиться на мудрых (первые), нечестивых (у которых функция закраски взрывается), несмышленых (у которых она возвращается недокрасив) и неспособных задавать вопросы (последние).

https://toldot.ru/articles/articles_18265.html
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 31st, 2017 09:45 pm (UTC)
(Link)
А у кого возвращает ошибку - тот глава седера?
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:May 31st, 2017 09:49 pm (UTC)
(Link)
Об этом надо проконсультироваться у раввина :)
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:June 1st, 2017 05:21 am (UTC)

Определение

(Link)
Если количество шагов алгоритма превышает количество точек, им рисуемых, то он точно плохой!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 1st, 2017 05:55 am (UTC)

Re: Определение

(Link)
Кто б спорил, но вот пишут же, что была коммерческая реализация.
(Reply) (Parent) (Thread)
[User Picture]
From:hirelingofnato
Date:June 1st, 2017 06:32 am (UTC)
(Link)
К чему такие сложности? В GDL все гораздо удобнее.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 1st, 2017 06:40 am (UTC)
(Link)
Речь про восьмибитные компьютеры с 64 Кб памяти.
(Reply) (Parent) (Thread)