Monthly Archives: Июль 2012

Один алгоритм раскраски графа

В этой записи я решил представить алгоритм, придуманный мной под впечатлением от распределённых (distributed) алгоритмов. Алгоритм строит (субоптимальную) правильную вершинную раскраску неориентированного графа. Алгоритм довольно прост и, возможно, был в том или ином виде представлен в литературе.

Алгоритм

  1. Построить первоначальную раскраску (необязательно правильную). Эвристика: построить раскраску в два цвета поиском в ширину (чётный фронт → цвет «0», нечётный фронт → цвет «1»).
  2. Пока есть конфликты, производить разрешение конфликтов.

Под конфликтами понимается наличие одинаково окрашенных вершин-соседей. Проверка «есть конфликты» перебирает все вершины и составляет список C троек (вершина v, количество конфликтов n, минимальный неконфликтный цвет c), отвечающий конфликтующим вершинам (n = количество соседей v, имеющих тот же цвет, что и v). Если вершину v перекрасить в цвет c, то конфликт будет разрешён (при условии сохранения прежних цветов соседями v). Если конфликтов нет, то список C будет пуст, и алгоритм закончит работу — будет получена правильная раскраска вершин графа.

«Разрешение конфликтов» производится следующим образом.

  1. Завести множество соседей перекрашенных вершин A := Ø.
  2. Упорядочить список конфликтов C по убыванию числа конфликтов n.
  3. Для каждой тройки (v, n, c) из C, если v не принадлежит A, то:
    1. Назначить вершине v цвет c.
    2. Пополнить A соседями v.

Свойства алгоритма

По завершении работы алгоритма получаем правильную вершинную раскраску. Необходимо доказать, что работа алгоритма завершится. Строгого доказательства я выполнять не стал. Однако, нетрудно заметить, что всего конфликтов может быть не больше, чем всего вершин в графе (N), за одно разрешение конфликтов разрешается как минимум один конфликт и не добавляется новых, поэтому достаточно N итераций цикла. Одна итерация цикла требует O(N + M) действий (для каждой вершины проверить всех её соседей). Отсюда можно сделать вывод, что алгоритм имеет сложность O(N(N + M)) ≤ O(N3).

Реализация

Была написана реализация алгоритма на C++, включающая набор простых графов для проверки. Для всех простых тестов алгоритм даёт оптимальную раскраску.

Langs: рассуждения

Нередко ведутся жаркие неконструктивные споры на тему «какой язык программирования лучше/хуже». В лучшем случае, они переходят в плоскость конкретных применений тех или иных языков, которые, как и любые инструменты, более уместны каждый для своего круга задач. Как известно, не следует забивать гвозди отвёрткой. Однако, если нет молотка, то можно забивать гвозди и кирпичом.

Существует определённый класс наиболее широко используемых (в компаниях-разработчиках ПО) языков, называемый «промышленные языки программирования». Обычно, их активно ругают адепты «новых» языков, не используемых столь же широко. Впрочем, когда (и если) база пользователей разрастётся, эти языки, в свою очередь, могут стать «промышленными» с такими же печальными для их репутации последствиями.

Старые же «промышленные» языки превращаются в этаких легендарных монстров: таковы Fortran, PL/I, COBOL и, возможно, VB/VBA (до .net). Современные примеры: C, C++, Java, C#, JavaScript и (особенно критикуемый) PHP. Возможно, один из главных недостатков промышленного программирования в том, что оно практически «выродилось» в довольно рутинную работу — склеивание мириад кусочков фреймворков в конечное «приложение».

Промышленные языки традиционно занимают верхние строчки рейтингов популярности (например, Tiobe). Проводя оценку этих рейтингов, не следует забывать проанализировать способ их расчёта.

Другие люди испытывают «аллергию» на языки, использовавшиеся для обучения: как правило, диалекты Basic и Pascal.

Как сказал Б. Страуструп: «there are only two kinds of languages: the kind everybody bitches about, and the kind nobody uses» (есть только два вида языков: те, которые все ругают, и те, которые никто не использует). Ругать не буду. Вместо этого попробую привести список интересных, с моей точки зрения, и при том, не слишком новых языков программирования (есть множество интересных языков, появившихся недавно, о них пока речь не идёт).

Итак, наиболее важный для меня язык — C++.  Основные достоинства C++ — это обширная база доступных библиотек любой направленности и наличие развитых оптимизирующих компиляторов (g++, clang, icc, msvc, pgi, open64, …) для большинства актуальных платформ, способных производить глубокую оптимизацию кода. Поэтому C++ обычно выбирают в случаях, когда важна высокая (и предсказуемая) производительность ПО (3D игры, вычислительно-тяжёлые задачи, управление автоматизированными системами).

Наблюдаемое постепенное снижение популярности C++ должно приостановиться с появлением существенно обновлённого стандарта 2011 года (жаль, не добавили концепты, хотя многие и так ругают за чрезмерное раздувание и без того немаленького стандарта) и релизом Microsoft Windows 8. К слову, по тому же рейтингу Tiobe видим очень высокую популярность C относительно C++. Не останавливаясь на возможных систематических ошибках статистики, способствующих указанной ситуации, замечу, что выбор C вместо C++ для написания нового ПО вряд ли целесообразен в большинстве случаев, кроме ряда ниш, в которых требуются особенно большая предсказуемость и легковесность «чистого C»: написание элементов ядра ОС, драйверов, firmware, ПО для встраиваемых систем и DSP.

У C и C++ много общих проблем, отчасти  следующих из их кросс-платформенности и относительной низкоуровневости, и C++ добавляет свою специфику. Тем не менее, при соблюдении определённой культуры, он может обеспечить прирост производительности труда программиста относительно C без последствий для качества продукта.

C++ искушает программиста чрезмерно обобщать код, выстраивая библиотеки шаблонов. Потом это всё начинает ломаться, что весьма огорчает и, видимо, даёт свой вклад в нелестные отзывы о C++. KISS — жизненно необходимый принцип при программировании в C++.

Довольно интересно (для программистов на C++) выглядит пока ещё относительно малопопулярный и малоизвестный язык D, разрабатывавшийся компанией Digital Mars именно как замена C++ с отказом от совместимости с C (как полагают авторы D, стремление сохранить эту совместимость внесло немалый вклад в сложность программирования на C++).

D решает многие из характерных проблем C++, выглядит проще и логичнее. Хотя, способы решения этих проблем порой вызывают негативные оценки. К сожалению, в виду низкой популярности, качество компиляторов D (dmd, gdc и clang D), количество доступных библиотек и открытого кода, да и просто литературы весьма отстаёт от таковых для C++. А. Александреску недавно опубликовал книгу по D: «Язык программирования D». Есть плагин для Visual Studio, позволяющий добавить к её языкам язык D: Visual D. Сайт, посвящённый D.

Я не могу не упомянуть семейство языков Н. Вирта (к которым относится и не любимый многими Pascal). Интерес могут представлять языки на основе Oberon-2: собственно Oberon-2007 , Component Pascal и Zonnon (Active Oberon). Что необычно, так это постепенное уменьшение сложности и объёма описаний языков, создаваемых Виртом (Algol W → Pascal → Modula → Modula-2 → Oberon → Oberon-2). Изначально Oberon разрабатывался вместе с интерактивной средой (аналогично Smalltalk). Пример ОС написанной на Active Oberon: A2. Возможно, с точки зрения обучения программированию «с нуля», языки семейства Oberon — это не такой уж плохой выбор?

Хотя, может быть полезнее использовать для этого Eiffel, основные отличительные черты которого — прямая поддержка контрактов функций (пред- и постусловия) и инвариантов классов, а также интересная модель (множественного) наследования.

Среди «скриптовых» языков с динамической типизацией я хотел бы выделить два языка: Lua и Python. Оба языка активно используются как скриптовые, т.е. встраиваются в приложения, например, в игры для реализации высокоуровневой логики, элементов AI или даже управления пользовательским интерфейсом. Это удобно, так как можно быстро вносить изменения, не производя повторную компиляцию кода. Оба языка имеют минималистичный синтаксис. Lua отличается особенной легковесностью и скоростью выполнения байткода. Не помню, чтобы видел сравнение с JavaScript «на стероидах», но программы на Lua обычно выполняются гораздо быстрее аналогов на Python и Ruby.

К слову, о «стероидах». Авторы виртуальных машин JavaScript идут на множество ухищрений, вплоть до распознавания в коде характерных образцов и JIT-подмены их глубоко оптимизированными на низком уровне реализациями, поэтому высокая скорость в таких случаях не является гарантией такой же высокой скорости на другом коде, особенно, если он в каком-то смысле необычен.

В свою очередь, сейчас Python широко применяется и как основной язык разработки приложений. Обычно его любят за то, что можно быстро набросать и выполнить некий код (например, желая быстро создать прототип), не разбираясь со множеством низкоуровневых деталей и не решая множества мелких проблем, не имеющих прямого отношения к делу.

Благодаря относительной простоте старта, Python и Lua нередко рекомендуют в качестве первых языков программирования.

В качестве первого языка программирования часто рекомендуется JavaScript, потому что для работы с ним достаточно современного браузера. Можно сразу начать делать что-нибудь интересное (вплоть до 3D средствами WebGL). Отмечу, что внешне гораздо привлекательнее смотрится CoffeeScript — язык, транслируемый в JavaScript.

Но я бы хотел упомянуть ещё три группы языков, менее популярных, нежели рассматривавшиеся выше.

Первая группа — это набирающие популярность функциональные языки. Если вы пользуетесь Visual Studio и желаете познакомиться с ними, то удобно начать с F#, поддерживаемом Visual Studio 2010 и новее. Лично мне интересны следующие три представителя функциональных языков.

Erlang — язык, предназначенный для реализации больших устойчивых к ошибкам распределённых систем с параллельной работой отдельных узлов, весьма удачно реализующий акторную модель. Erlang не самый сложный в изучении ФЯ, обладающий синтаксисом, который иногда находят «архаичным». Имеется общедоступная opensource реализация.

Haskell — язык-знамя ФП. Интересен двумя особенностями: высокой чистотой с точки зрения функционального программирования, насыщенностью различными идеями, благодаря чему эффективен в качестве учебного пособия (покрывает множество вопросов, в этом он напоминает C++), и наличием компилятора в машинный код (GHC), что позволяет рассматривать Haskell как язык, подходящий для написания вычислительно интенсивных программ.

SBCLреализация компилятора Common Lisp в машинный код с широкими возможностями низкоуровневой оптимизации. Что ещё к этому можно добавить?

Две оставшихся группы языков таковы, что о них слышал не каждый современный программист. Они интересны хотя бы с точки зрения развития программистских способностей. Тексты программ на этих языках с непривычки довольно тяжело читать. Для того, чтобы осознать их гибкость и внутреннюю красоту, требуется изучить хотя бы несколько примеров.

Forth-подобные языки. Среди них есть и объектно-ориентированный язык с динамической типизацией — Factor (реализация).

APL/FP-подобные языки. Листингом на таком языке можно ввести в замешательство тех, кто уже привык к C++ или Perl. К сожалению, сейчас это семейство языков занимает позицию чуть ли не эзотерических языков. Тем не менее, это реальные языки, с помощью которых можно решать реальные задачи. Кратко об идеях, заложенных в языке Дж.Бэкуса FP, можно прочитать на Википедии. Современный язык этого типа с общедоступной реализациейJ. Язык «заточен» на работу с массивами.

Наконец, последнее замечание касательно обучения программированию. На мой взгляд, существует две основных крайности.

Можно дать «нюхнуть пороху» — обрушить на обучающегося весь груз относительно низкоуровневого языка, с одной стороны, со всей его сложностью и тысячью исключений из общих правил, с другой стороны, со всем его богатством идей и решений (и «костылей», конечно же).

Теоретически, те, кто выплывет, будет способен быстро освоить многие другие языки и быстро начать работать (со многими «если»). Например, освоив C и C++, сравнительно легко перейти на Java, C#, Objective C. Хотя, человек, привыкший к C++, наверняка будет сначала плеваться от того же C# — вроде синтаксис так знаком, а за ним скрывается совсем другой язык.

Сюда же можно отнести (уже ставший историей) Basic на ранних микрокомпьютерах. Существует поколение программистов, начинавших с него в детстве (к ним отношусь и я сам). В своё время Э.Дейкстра негативно (хотя и с юмором) отзывался о тогдашнем BASIC (ещё более раннем; кстати, это прообраз скриптовых языков, можно сказать, первый из них), но существует и другое мнение (ещё). Некоторое сходство (по духу) с тем Basic, как мне показалось, демонстрирует язык Euphoria (по простоте сравним с Lua).

Можно же наоборот, максимально оберегать обучающегося от технических деталей и проблем. Пытаться раскрыть саму суть программирования и вычислений. Теоретики любят для этого использовать Scheme (далее следует глубокое погружение в матан «computer science»).

Также к этой крайности ближе обычное обучение языкам Lua, Python и Ruby. Более того, существуют языки и среды программирования (например, на основе Logo), нацеленные именно на обучение (в том числе, младших школьников или даже дошкольников — вплоть до отказа от написания кода).

Лично я склоняюсь к тому, что для обучения профессиональных программистов полезнее быть ближе к первой крайности : ).

Программирование — это ремесло, и лучшие его образцы становятся искусством. Его нелегко заковать в узкие рамки логичной, но обезличенной теории.

Ещё несколько ссылок «на засыпку».
Yet another list of languages worth studying.
Why use Erlang.
Play with Lua: turning a Lua program into an executable.

YAPLC: mainstream generations

It seems to me it was this way (in «industrial mainstream»).

60‘ ad-hoc calculations, procedural programming (Fortran)
70‘ standardized, structural programming, databases (COBOL, PL/I)
80‘ portable assembly, system programming, libraries, 4GL, micros boom (C, Pascal, SQL, Basic)
90‘ object-based/oriented programming (C++, VB, Object Pascal)
00‘ managed static-typed languages, heavily-OO frameworks (Java, C#)
10‘ dynamic-typed languages, still mostly OOP-like (Python, Ruby, JS)
20functional programming? asynchronous/massive parallelism? native code renaissance?

What languages will see mainstream use in 20’s? Probably, it will be «hybrids» based upon current ones (and possibly bearing the same names).