Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Нет, давай критерий. Ты же мою программу хочешь сравнить, так что давай критерий, а не слова. Это я на слова имею право, если буду доказывать теорему о существовании — она по определению не говорит, как это найти. А ты готов программу сравнивать. Критерий давай!
S>>>Показываю, следим за руками: S>>>При запуске на 1 (одном) ядре, эта программа тратит X вычислительных ресурсов (временем я оперировать не буду, т.к. оно зависит много от чего еще). S>>>При этом непараллельная версия, которую ты привел, тратит X-delta ресурсов (например, потому что в ней нет WaitforMultipleObjects, нет динамического распределения памяти, да и вообще обращений к структурам chunk).
S>>>Значит, она заведомо хуже, чем теоретически достижимый предел.
PD>>Дай сначала определение ресурса (время тебя не устраивает, тогда что же это ?), тогда и поговорим. А пока это попытка доказать что-то с неопределенными утверждениями , используемыми для доказательства. S>Слив засчитан.
Твой ? Ты заявляешь, что программа тратит сколько-то ресурсов, а при этом отказываешься сказать, что же это такое — в твоем понимании. Что же она у тебя тратит в таком случае ? Пока ты это определение не дал, все твои разговоры о том, что она что-то тратит, выеденного яйца не стоят.
Здравствуйте, IT, Вы писали:
IT>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>А может, проще — для любой программы на языке ВУ существует эквивалентная программа на ассемблере, которая работает так же.
IT>JIT может пораждать разный код для разных железно/софтовых окружений. Отсюда следует простой вывод, что эквивалентная программа на ассемблере на твоём компьютере будет работать не так же на моём.
Хе-хе, батенька. А JIT — он что, дух святой ? Программа есть процесс (или несколько процессов), и в данном случае это неуправляемый процесс (потому что все процессы неуправляемые, других в Windows нет), частью которого является JIT, .Net FW или, к примеру, интерпретатор Бейсика древнего. И в этом смысле он ничем не отличается от некоей библиотечной функции, которую я могу вызвать. Эта функция мне данные каким-то образом преобразует, а JIT — тоже данные преобразует (байты IL) в другие данные, которые окажутся вдруг машинными командами , а поэтому он на них передаст управление.
Или ты считаешь, что я не могу без JIT написать самомодифицирующуюся программу ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Или ты считаешь, что я не могу без JIT написать самомодифицирующуюся программу ?
То есть вместо использования JIT ты напишеш свой?
Здравствуйте, prVovik, Вы писали:
V>Тем более, что и МС не гнушаются делать хелп в виде ASP.NET приложений. У них, правда, причины другие, но факт остается фактом.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, prVovik, Вы писали:
V>>Тем более, что и МС не гнушаются делать хелп в виде ASP.NET приложений. У них, правда, причины другие, но факт остается фактом.
ВВ>А где у MS такой хелп?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Твой ? Ты заявляешь, что программа тратит сколько-то ресурсов, а при этом отказываешься сказать, что же это такое — в твоем понимании. Что же она у тебя тратит в таком случае ? Пока ты это определение не дал, все твои разговоры о том, что она что-то тратит, выеденного яйца не стоят.
То есть тебе не очевидно, что твоя программа "с параллельностью", запущенная на одном ядре, будет менее эффективной, чем твоя же программа "без параллельности"? В каких бы терминах мы ни мерили — в секундах, в тактах, в байтах или еще в чем?
Ты уже определись — то ли ты крутой специалист по оптимизации программ, то ли необученный новичок.
Если первое — то непонятно, зачем тебе разжевывать, куда деваются такты и байты памяти при лишних вызовах WaitForMultipleObjects и new[].
Если второе — то я могу разжевать, но тогда загибы пальцев в духе "я читал Intel Pentuim IV Programming Guide" и необоснованные предположения о моей некомпетентности в этих вопросах нужно спрятать подальше.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, AndrewVK, Вы писали:
AVK>Смешно. Потрясающий ты человек, Павел Дворкин.
Ну и смейся на здоровье. Я , собственно говоря, во всех этих дискуссиях порой с одной целью участвую — посмеяться над фанатиками чего бы то ни было
AVK>Да я и не требую.
Ты — нет, верно, сорри. Это IT вообразил, что он командовать может. Я как-то вас обоих перестал разделять, а напрасно. Учту
>Только выглядят после этого твои слова, как бы это помягче, неубедительно.
Да бога ради. Для тебя одно неубедительно, для меня другое, а третьи лица пусть сравнивают и убеждаются.
PD>>Ну насчет каши — не нравится язык — дело твое. Я другой язык использовать не буду.
AVK>Кто бы сомневался.
А зря, между прочим. Не буду — означало для данной задачи. А в остальном я вполне свободен в выборе. Надо будет — буду писать на C# (писал уже, хоть и совсем немного), надо будет — и на VBA напишу (тоже чуть-чуть приходилось), более того — если окажется, что в данном случае лучше всего GW-Basic — напишу на нем, хоть и чертыхнусь в душе.
А вот тебя заставить писать на C/C++ и Win32, похоже, можно только под дулом пистолета
Еще раз, Андрей, пойми наконец. Я вовсе не противник шарпа, LINQ или ФП. Там где они уместны — да бога ради. Я вовсе не предлагаю на ассемблере доступ к таблице БД писать. Не надо мне приписывать того, что я не говорил. Но когда мне начинают заявлять, что некие высокоуровненые средства ну никак нельзя реализовать на уровне ниже — я просто не знаю, смеяться или плакать. Потому что кто-то же их реализовал, ибо процессор не умеет ни LISP, ни LinQ обрабатывать. Вот и все.
PD>> А описание — мне казалось , что я его дал.
AVK>Вот именно что казалось.
Ну каждый дает описание исходя из своего понимания того, как это дают. Если бы я это в форуме по Win32 написал — уверен, меня бы с полуслова поняли бы.
>>>поэтому я просто распараллелил вычисление сумм красных компонент по столбцам окна.
AVK>Компонент чего, rакого окна?
Компонент пикселей окна, красных. Окна любого, Windows.
>О чем вообще речь? Сравни свое "описание" с описанием IT. Ну хотя бы по объему. А с таким описанием я тебе могу дать точно такой же ответ: AVK>
Нет, не пойдет этот аргумент. Пусть даже ты прав, и можно было уточнить. Но текст программы приведен, и в нем (по крайней мере в непаралельной части) разберется любой мой студент за 1 минуту, даже если я вообще никакого описания не дам. несерьезно это. Ну а потом — я же дал тебе после этого более развернутое описание задачи, зачем опять муссировать это ?
AVK>Из комментариев еще можно понять, что у тебя там вроде бы есть еще и непараллельный алгоритм, но AsParallel реально параллелит только если есть несколько ядер. Впрочем, явно указать тоже не проблема:
Если ты не очень понимаешь Win32, это еще не причина, чтобы жаловаться. Я не лучше тебя знаю LinQ, но я не заявлял, что не пойму этот SELECT, что IT привел. Если не понимаю — мои проблемы.
AVK>А теперь сравни со своей простыней. Что там у нас осталось? Параллелить вкривь и вкось различными способами?
Если не сложно, объясни , почему вкривь и вкось, это раз, и откуда там различные способы, если там всего один. А второй вопрос — ты хоть понимаешь, что внутри твоего AsParallel зашита работа с потоками примерно так, как я и сделал. Не обязательно так, конечно, скорее там пул потоков, посмотрю как-нибудь. Ну нет в Win32 иного способа параллелить и нет в Windows ничего, что не проходио бы через Win32 (про OS/2 и POSIX умолчим).
>Все это задается начальными итераторами, теми, которые на вход AsParallel поступают. И тут тоже у шарпа с его итераторами возможностей по понятной и эффективной реализации всяких причудей будет больше, чем ты сможешь на С++ изобразить.
Итераторы в С++ существуют, а вообще это понятие языково-независимо. Распараллеливание тоже (не в С++, а в Win32). И никак нельзя распараллелить иначе, чем Win32 (или на худой конец native API) позволит. С этим-то хоть ты согласен ? Вот ответь прямо — да или нет ?
PD>>Дано окно Windows с неким рисунком в нем. Пройти по всем пиксельным столбцам клиентской области этого окна и найти для каждого столбца сумму R (красных) компонент пикселей , записать результаты в массив columnSum. Две реализации — в лоб без распараллеливания, и с распараллеливанием PD>>Реализация с распараллеливанием — создаются N потоков, где N — число процессоров (возвращает GetSystemInfo). Если процессоров 2, то один поток займется левой половиной окна, а другой правой. Если 3 — левой, средней и правой соответственно. И т.д.
AVK>Если это все, тогда в первый вариант вместо things подставляем: AVK>
AVK>from x in Enumerable.Range(0, Width)
AVK>from y in Enumerable.Range(0, Height)
AVK>select pixels[x, y]
AVK>
AVK>Ну и все вместе: AVK>
AVK>return
AVK> (
AVK> from x in Enumerable.Range(0, Width)
AVK> from y in Enumerable.Range(0, Height)
AVK> select pixels[x, y].Red
AVK> )
AVK> .AsParallel()
AVK> .Sum();
AVK>
Честно говоря, не слишком понял — что ты суммируешь и куда. Если это реализация моей задачи — где массив сумм по столбцам ?
Но то, что эту задачу ты распараллелишь, я и не сомневаюсь. Ты все же попробуй те 5 вопросов осилить. А это суммирование, конечно, распараллелить можно, задачка-то пустяковая.
AVK>А теперь я поработаю чуток предсказателем — ты все равно не напишешь пример IT в императивной форме.
Вообще-то я не очень понимаю — в чем разница. Он какие-то проценты считает на баз неких коллекций, а я суммы считаю на базе тоже, если хочешь, "коллекций — столбцов пикселей. Делить я не делю и не суммирую, верно, но так ли это важно ? Есть распараллеливание алгоритма, что тут особого-то.
Ну а если тебе так уж нужны именно эти проценты — обещать не могу, что сделаю в ближайшее время, но так и быть, постараюсь сделать. Но не торопи. Не до этого мне сейчас.
Здравствуйте, IT, Вы писали:
IT>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Я предложил свой код и продемонстрировал. Это мое право — предложить код, который я хочу для демонстрации.
IT>По этой логике моим ответом должно быть предложение ещё одного кода и задавание кучи не относящихся к теме вопросов. Извини, но это не диалог двух людей с высшим техническим образованием. Это тётки на базаре, кто кого перекричит. Я в этом участвовать не собираюсь.
Я тоже. Судя по всему, с тобой дискутировать лучше не надо.
Здравствуйте, Mirrorer, Вы писали:
M>Результаты в миллисекундах
M>478 M>489 M>487 M>492
M>машинка. Intel 1.73 ГГц
PD>>В релизе на моей машине (AMD Dual 4200+)
PD>>nTime1 == 2375 PD>>nTime2 = 1593
Приношу мои глубочайшие извинения, но мне и в голову не приходило, что кто-то станет сравнивать мои результаты со своими. Я привел их только для того, чтобы показать. что параллельный результат лучше, и насколько. Сравнивать же твои результаы с моими бессмысленно — сначала надо о размере окна договориться
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>И никак нельзя распараллелить иначе, чем Win32 (или на худой конец native API) позволит. С этим-то хоть ты согласен ? Вот ответь прямо — да или нет ?
Andrei F.,
AF>Допустим, у нас есть некоторый GUI с деревом. Развесистым таким деревом, на 10^n элементов. И пользователь где-то в глубине иерархии поменял название одного элемента. Как это будет выглядеть в рамках ФП?
Из сообщений z00n, я понял, что тебе недостаточно, что функциональные структуры данных существуют и работают. Тебя интересует, как будет происходить весь процесс, начиная с процедуры вндового цикла сообщений?
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Полностью абстрагируясь от эффективного вычисления процентов , отмечу лишь, что сделать код с помощью каких-то высокоуровненвых конструкций проще — можно, понятнее — тоже можно, а вот эффективнее — дудки. Потому что предельно эффективная программа — это наилучшим образом оптимизированная программа, написанная на ассемблере. А в этом самом ассемблере есть только презренные присваивания, if, с грехом пополам циклы, и ни одной лямбды
Как и следовало ожидать, провокационная тема ушла в глубокий флейм, перемежаемый пенисометрией.
Поскольку никто из нормальных людей в такие глубины веток не ныряет, напишу правильный ответ здесь.
Итак, не отвлекаясь на фигню, отвечаем на вопрос: "можно ли сделать код эффективнее с помошью каких-то высокоуровневых конструкций?".
Во-первых, нужно отметить, что вопрос про то, какой код исполняется эффективнее — ассемблерный или еще какой — не стоит. Как ты верно подметил в глубинах флейма, "процессор всё равно не умеет исполнять никакого другого кода, кроме ассемблерного".
Отлично, тогда что же мы сравниваем и с чем? Вот у нас одна программа (очевидно, ассемблерная), и вот другая программа. Очевидно, тоже ассемблерная. Одна из них может оказаться эффективнее другой. Какая же программа будет именно такой?
Для начала, нужно понять, что такое "более эффективная". Это не такой тривиальный вопрос, как кажется. Дело даже не столько в том, что количество тактов, потребляемое некоторой программой для решения некоторой задачи, зависит от массы сторонних факторов (например, насколько часто процессору приходится отвлекаться от нее на обслуживание чего-то другого), а в том, что сначала нужно определиться с тем, что такое "решение задачи".
В стародавние времена программы (и задачи) были одноразовыми. Нужно вам, скажем, посчитать число Пи до тысячного знака. Ок, пишем программу, которая считает число Пи; запускаем, дожидаемся результата — ок, задача решена. Очевидно, что второй раз нам считать число Пи уже не надо. (Если, конечно, мы не забыли вывести куда-то результат вычислений ). Опять же очевидно, что при многократном запуске расчета числа Пи эффективнее всех прочих будет программа, которая устроена примерно так (в терминах C++):
сout << "3.1415926...";
(Производители процессоров об этом в курсе; поэтому инструкция fldpi выполняется значительно быстрее, чем самый оптимизированный расчет суммы несложного ряда)
Cейчас мы подразумеваем под "задачей" семейство задач в том древнем смысле. То есть когда мы говорим "нужна программа для сортировки массива" мы подразумеваем, что одна и та же программа будет использоваться для сортировки различных массивов. А вовсе не для сортировки конкретного массива.
В чем сложность? В том, что раньше мы могли рассуждать об эффективности в терминах расходов памяти и тактов процессора, нужных для решения конкретной задачи. Нужно тебе X знаков после запятой в разложении Пи? Ок, это будет стоить N(X) тактов и потребует P(X) байт памяти.
Теперь так рассуждать нельзя — затраты в тактах и байтах существенным образом зависят от того, какие именно данные мы подали на вход. На пальцах: пузырек, запущенный на отсортированном массиве длины N выполнит N сравнений, 0 обменов и успокоится. На обратно отсортированных данных он выполнит N^2/2 сравнений и обменов.
Поэтому, говоря об эффективности, мы говорим о матожидании затрат при некотором распределении входных данных. Очень немногие программисты задумываются об этом распределении. К примеру, асимптотические оценки алгоритмов сортировки традиционно даются для равномерного распределения: все перестановки значений во входных данных считаются равновероятными.
Конечно же, в природе задач с равномерным распределением не существует.
На данном этапе мы уже поняли, что если мы беремся сравнивать две программы по эффективности, то нам нужно задатсья некоторым распределением входных данных. Если мы этого не сделаем, то сравнение не имеет смысла — в одних условиях выиграет программа А, в других — программа B.
Итак, критерий сравнения эффективности программ — это матожидание затрат памяти и тактов на решение одной из задач, заданных некоторым распределением.
Поговорим об идеальной эффективности.
В идеальном мире мы можем получить информацию о предполагаемом распределении, и выбрать ту программу, которая покажет наилучшие результаты именно для него.
В реальном мире такие оценки очень редко можно получить заранее, до запуска программы.
Как же нам быть в таком случае? Выбирать программу случайно?
Способ, очевидно, есть. Вместо того, чтобы подготовить одну программу, мы можем подготовить семейство программ, которые имеют одну и ту же семантику (например, все они сортируют любой массив), но отличаются характеристиками производительности для различных входных данных.
И только тогда, когда мы узнаем, какие же данные поступают к нам на вход, мы выбираем ту из программ, которая лучше подходит для конкретного случая.
Этот подход замечателен тем, что он не требует полной априорной информации о свойствах будущей задачи. Очевидно, что он обеспечит не худшую производительность, чем фиксированная программа на все случаи жизни.
Осталось понять, можно ли применить этот подход, оставаясь в рамках "наилучшим образом оптимизированной программы, написанной на ассемблере", и "можно ли сделать код эффективнее с помошью каких-то высокоуровневых конструкций". Об этом я напишу завтра, потому что сегодня пора домой
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Andrei F.,
AF>>Допустим, у нас есть некоторый GUI с деревом. Развесистым таким деревом, на 10^n элементов. И пользователь где-то в глубине иерархии поменял название одного элемента. Как это будет выглядеть в рамках ФП?
LCR>Из сообщений z00n, я понял, что тебе недостаточно, что функциональные структуры данных существуют и работают. Тебя интересует, как будет происходить весь процесс, начиная с процедуры вндового цикла сообщений?
Да, мне тоже. И хотя бы на примере кнопки, если можно.
Здравствуйте, Sergey J. A., Вы писали:
SJA>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Или ты считаешь, что я не могу без JIT написать самомодифицирующуюся программу ? SJA>То есть вместо использования JIT ты напишеш свой?
Нет, конечно, зачем ? Я напоминаю, речь же шла о теореме существования.
Здравствуйте, IT, Вы писали:
IT>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Или ты считаешь, что я не могу без JIT написать самомодифицирующуюся программу ?
IT>Картина Репина "Закат солнца в ручную". Ну-ну. Ты проценты распараллелить не в состоянии, какой нафиг JIT?
Ты же вроде обещал прекратить дискуссию, так ? Но почему-то продолжаешь ерничать. Причем с такой настойчивостью, что создается вречатление, что тебя сильно задели. Остынь и успокойся.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну каждый дает описание исходя из своего понимания того, как это дают. Если бы я это в форуме по Win32 написал — уверен, меня бы с полуслова поняли бы.
Проблема в аудитории, то есть? Понятно.
>>О чем вообще речь? Сравни свое "описание" с описанием IT. Ну хотя бы по объему. А с таким описанием я тебе могу дать точно такой же ответ: AVK>>
PD>Нет, не пойдет этот аргумент. Пусть даже ты прав, и можно было уточнить. Но текст программы приведен, и в нем (по крайней мере в непаралельной части) разберется любой мой студент за 1 минуту, даже если я вообще никакого описания не дам.
Логично, на то он и пример.
PD> несерьезно это.
Несерьезно, это не понимать, что читаемость кода и его близость к формулировке задачи — это самый важный параметр оценки качества этого самого кода. Конечно, на таком игрушечном кусочке вроде как можно и пережить то, что ты продемонстрировал, но когда кусочки станут побольше, соотношение объема изапутанности сохранится, если не увеличится, и вот тут то это будет совсем уже не фигня.
PD> Ну а потом — я же дал тебе после этого более развернутое описание задачи, зачем опять муссировать это ?
Ну а я — более подробное решение. В чем проблема то?
AVK>>Из комментариев еще можно понять, что у тебя там вроде бы есть еще и непараллельный алгоритм, но AsParallel реально параллелит только если есть несколько ядер. Впрочем, явно указать тоже не проблема:
PD>Если ты не очень понимаешь Win32, это еще не причина, чтобы жаловаться.
Вот, кстати, характерная твоя ошибка — говорим о дизайне кода, а ты даже не в состоянии привести пример без использования специфики Win32. Все я прекрасно понимаю, но разбираться в этом принципиально не хочу, потому что к обсуждаемому вопросу это отношения не имеет.
PD> Я не лучше тебя знаю LinQ
Ты вообще понимаешь разницу между конструкциями языка и API операционной системы? Мы здесь, еще раз напоминаю, обсуждаем именно конструкции языка, и ничто иное. Обойтись без LINQ для демонстрации возможностей ФП на шарпе нельзя в принципе, обойтись без Win32 для демонстрации того, что LINQ ничего не дает можно, и даже нужно.
PD>, но я не заявлял, что не пойму этот SELECT, что IT привел.
Конечно, в том и суть, что ты, ничего не зная ни про ФП, ни про LINQ, тем не менее понимаешь код, который IT привел.
AVK>>А теперь сравни со своей простыней. Что там у нас осталось? Параллелить вкривь и вкось различными способами?
PD>Если не сложно, объясни , почему вкривь и вкось, это раз
Не знаю, тебе захотелось по диагонали или еще как то там пиксели обсчитывать.
PD>, и откуда там различные способы, если там всего один.
В конце у тебя там вопросы под пунктами.
PD> А второй вопрос — ты хоть понимаешь, что внутри твоего AsParallel зашита работа с потоками примерно так, как я и сделал.
Понимаю. И что? Я тебе в который раз напоминаю — речь не о библиотеках и их возможностях, речь о языке программирования. AsParallel просто демонстрирует эти возможности, не более того.
PD> Не обязательно так, конечно, скорее там пул потоков, посмотрю как-нибудь. Ну нет в Win32 иного способа параллелить и нет в Windows ничего, что не проходио бы через Win32 (про OS/2 и POSIX умолчим).
Оторвись от замочной скважины и открой наконец дверь.
PD>Итераторы в С++ существуют, а вообще это понятие языково-независимо.
Под итераторами в C# здесь подразумеваются специальные возможности языка. Это частный случай продолжений (continuations), предназначенный для легкого и удобного создания сложных итераторов. В С++ такое эмулируют при помощи макросов, но качество решения получается при этом ниже плинтуса.
PD> Вот ответь прямо — да или нет ?
Отвечаю прямо — неважно. Не уводи от темы. Распараллеливание здесь в качестве примера, а не самоцель. Если не можешь съехать с Win32, я могу в примере заменить распараллеливание на, скажем, кеширование.
PD>Честно говоря, не слишком понял — что ты суммируешь и куда. Если это реализация моей задачи
Она.
PD> — где массив сумм по столбцам ?
Вот тебе с массивом, это еще проще:
return
(
from x in Enumerable.Range(0, Width)
select Enumerable.Range(0, Height).Sum(y => pixels[x, y])
)
.AsParallel()
.ToArray();
Обрати внимание, насколько просто оказывается поменять код.
PD>Ты все же попробуй те 5 вопросов осилить.
Смысл? Игрища с приоритетами потоков в контексте вопроса малоинтересны и непринципиальны (ну будет там какой нибудь доп.параметр у AsParallel()). А хитрые итераторы, как я уже сказал, не проблема вовсе.
PD> А это суммирование, конечно, распараллелить можно, задачка-то пустяковая.
Только даже на такой пустяковой задачке прекрасно видно, насколько твой императивнй код запутаннее.
AVK>>А теперь я поработаю чуток предсказателем — ты все равно не напишешь пример IT в императивной форме.
PD>Вообще-то я не очень понимаю — в чем разница. Он какие-то проценты считает на баз неких коллекций, а я суммы считаю на базе тоже, если хочешь, "коллекций — столбцов пикселей.
У него алгоритм намного сложнее, а, главное, там уровень косвенности выше.
PD> Делить я не делю и не суммирую, верно, но так ли это важно ? Есть распараллеливание алгоритма, что тут особого-то.
Ты сделай сперва без распараллеливания, и мы обсудим результат.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>
Если нам не помогут, то мы тоже никого не пощадим.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
). Опять же очевидно, что при многократном запуске расчета числа Пи эффективнее всех прочих будет программа, которая устроена примерно так (в терминах C++):
