(О разработке алгоритмов, их описании и программной реализации)
(Модель античного святилища Аполлона в Дельфах)
Почему я продолжаю использовать устаревшие виртовский Pascal и Delphi-7?
Этот вопрос мне часто задают мои коллеги, сослуживцы по работе и здесь на Хабре. Решил ответить сразу всем в этой заметке.
Мои научные интересы в основном принадлежат области математической (или, как еще называют — компьютерной) химии. Это применение теории графов к фундаментальным и прикладным задачам органической химии (немного подробнее см.).
Для решения этих задач я применяю уже известные алгоритмы, иногда их модифицирую, а иногда делаю новые. Решение научной задачи обычно предполагает последующую публикацию в рецензируемом научном издании. Еще до начала работ стоит подумать: в каком виде я собираюсь описать новый алгоритм?
В настоящее время можно выделить четыре распространенных способа такого описания.
1. Описание на естественном языке, пожалуй, самый легкий способ. Это древнейший способ. Евклид (около 300 года до н.э.) и Эратосфен (276 год до н. э.) его использовали. Переводы и пересказы описаний их знаменитых алгоритмов широко применяются по сей день. Но и новейшие алгоритмы часто описывают этим способом. Правда, математических формул в таких описаниях стало сильно больше, по сравнению с древними описаниями. Основной недостаток этого способа — многозначность многих слов естественных языков. Поэтому существует не малый риск, что автора поймут неоднозначно. И т.о. не смогут воспроизвести его алгоритм. А воспроизводимость — одно из основных условий научного метода.
2. Описание на псевдокоде. Тоже очень популярный способ. Тут можно выделить два подхода:
2.1. Изобретение оригинального псевдокода. Так Дональд Кнут для своей знаменитой монографии «Искусство программирования для ЭВМ» специально придумал компьютер MIX и ассемблер MIXAL. Тут явный недостаток — высокий порог входа. Для первого издания этой монографии в прошлом веке, такой подход, возможно, был оправдан. К настоящему времени создано много эмуляторов MIX, позволяющих увидеть, как работают коды из книги. Но для не очень большой статьи изобретение оригинального языка не представляется оправданным.
2.2. Использование для псевдокода упрощенной версии существующего ЯП. Про этот подход будет сказано ниже.
3. Описание на ЯП. По сути, это уже не описание алгоритма, а его реализация в виде программы. Здесь недостатки очевидны. Если читатель не знаком с применяемым ЯП, то ему может быть сложно (от слова «совсем») понять суть алгоритма. Детализированная публикация программы может вызвать сложности в бумажном издании — недостаток места. А места обычно нужно больше, чем в первых двух способах. И чтение всей программы целиком, потребует больше времени и внимания.
4. Описание с помощью блок-схемы. Этот способ уже довольно давно стал популярным. Еще Эдсгер Дейкстра его использовал в «Заметках по структурному программированию».
Для описаний небольших алгоритмов блок-схемы, безусловно, очень привлекательны своей наглядностью. Но, к сожалению, с ростом числа ветвлений и циклов блок-схема разрастается и повышается трудность восприятия. В случае бумажного представления формат бумаги может оказаться мал для блок-схемы. В связи с этим нужно упомянуть визуальный ЯП ДРАКОН, в котором предприняты меры по преодолению означенных неудобств. Однако применение специального ЯП может вернуть нас к способу 3.
Исходя из сказанного, я выбрал для себя способ 2.2. На мой взгляд, одним из наиболее подходящих для псевдокода является виртовский Pascal. Его, похоже, знают и помнят все программисты, а кто не знает — стесняется в этом признаться. Pascal-образный (Pascal-like) псевдокод интуитивно понятен (всем кто знаком, хотя с одним универсальным ЯП) и обычно хорошо структурирован, если нарочно не засорять его чем-то громоздким, и, конечно же, не использовать пресловутый goto. Для такого псевдокода доступны чекеры, и не только спелл-чекеры для правки комментариев, но и код-чекеры для кода. В роли последних выступают компиляторы и интерпретаторы Pascal. Например, очень удобен Dr Pascal. Превратить текст на псевдокоде в съедобный для транслятора обычно труда не составляет. Мне представляется очень важным, что Pascal — жестко типизированный ЯП, последовательно реализующий принципы защитного программирования. – На этапах разработки и проверки алгоритма, средства минимизации багов очень важны. А вот трюки, типа неявных преобразований бывают вредными.
Два слова про комментарии: считаю, что комментировать нужно уже в описании алгоритма. Причем комментировать достаточно подробно – это поможет поиску ошибок, и при написании статьи. Бывают трудные задачи, которые непонятно, как решать. Тогда я начинаю со способа 1. Записываю идеи решения в текстовой файл. Далее пытаюсь детализировать эти записи, выделить подзадачи и перейти к способу 2.2. Аналогично поступаю, если есть ТЗ. Правлю копию ТЗ с целью перейти к способу 2.2. Фразы от способа 1 оформляю комментариями. Такой прием помогает выбрать значимые имена. Если работа не на заказ, то сам пишу себе ТЗ. Описание алгоритма нужно и в случае, если не собираетесь его публиковать. Проходит время, и вы с удивлением смотрите на исходный код, реализующий алгоритм, который вам был когда-то совершенно понятен.
Еще про значимые имена – они очень важны, но комментарии не отменяют. Попробуйте впихнуть в значимое имя фразу: загрузить из архивного файла, записи для товарных вагонов, расшифровать их, пустые вагоны добавить в таблицу свободных вагонов. Получите довольно длинное имя, которое либо каждый раз безошибочно набирать, либо копировать, что может потребовать частые промотки текста. Код с такими много раз повторяющимися именами будет объемнее, чем код с единственным комментарием.
Следующим шагом после написания и описания нового алгоритма может быть его реализация и испытания полученной программы. Иногда это оправдано до доказательства корректности и теоретических оценок эффективности. — Зачем оценивать алгоритм, который врет. Для реализации использую IDE Delphi-7. Здесь у меня личная историческая причина. К примеру, если мой алгоритм на графах, то для испытаний нужно будет грузить графы. Их быстрее набирать в виде списка смежности, а для алгоритма нужна матрица смежности. Ну не писать же мне для каждого алгоритма процедуры трансляции списка в матрицу? — Понятно, что возьму эти процедуры из своего старого кода. Но почему Delphi-7, а не более новое? — К сожалению, проблемы несовместимости. Ну, а зачем с виртовского Pascal переносить на ОО Pascal Delphi? — Он ОО; зачастую даже для испытаний полезен или, даже, нужен GUI; иногда нужно испытать параллельный алгоритм и т. д. Использую не только свои старые процедуры I/O, но и, к примеру, реализацию поиска кратчайшего пути в графе, сортировку и т.д.
Но, конечно, «устарелость» Delphi-7 дает себя знать. OpenCV удалось применить и надписи в GUI Юникодом сделать (иначе под Windows 10 у моего любезного тестера не читались), а вот для CUDA пришлось переходить на C++. Отмечу, что когда программирую, то offline под Windows ХР SP 3 (с отсутствием Юникода в Delphi-7 проблем не возникает), а для online гружу другую ОС.
Говоря про испытания алгоритма, нужно отметить, что удачная работа программы — это хорошо, но, зачастую, не достаточно. Обычно нужно математически строгое доказательство.
Если лень или не удается строго доказать (самому или с чьей-то помощью), то иногда автор алгоритма объявляет его эвристическим. В общем, это может быть не страшно плохо. Есть задачи, для которых никто не нашел строгого решения. Есть такие, где ошибки не катастрофичны, например, в играх. Но есть и другие задачи. Например, поиск изоморфизма двух графов. Это известная открытая проблема, где нужно доказать, что эту задачу можно решить за полиномиальное время от числа вершин графа или, что такого решения быть не может. Притом, что открытой является и проблема P ?= NP. Предложено много эвристических алгоритмов поиска изоморфизма графов, только они никому не нужны.
После успешной проверки можно причесать программу. Сделать GUI удобным, подумать об оптимизации.
Здесь я написал про свой подход. Он, конечно, не единственный. Некоторые математики, не умея программировать и не зная ни одного ЯП, предлагают прекрасные алгоритмы для самых разных задач. Для описания алгоритма используют обычно способ 1 — естественный язык с большим количеством математических формул. Я же придерживаюсь взгляда, что CS — экспериментальная наука, разделяя мнения Аллена Ньюэлла и Герберта А. Саймона (Newell, Allen; Simon, H. A. (1976), «Computer Science as Empirical Inquiry: Symbols and Search» (1975 ACM Turing Award Lecture), Communications of the ACM, 19).
(Модель античного святилища Аполлона в Дельфах)
Почему я продолжаю использовать устаревшие виртовский Pascal и Delphi-7?
Этот вопрос мне часто задают мои коллеги, сослуживцы по работе и здесь на Хабре. Решил ответить сразу всем в этой заметке.
Мои научные интересы в основном принадлежат области математической (или, как еще называют — компьютерной) химии. Это применение теории графов к фундаментальным и прикладным задачам органической химии (немного подробнее см.).
Для решения этих задач я применяю уже известные алгоритмы, иногда их модифицирую, а иногда делаю новые. Решение научной задачи обычно предполагает последующую публикацию в рецензируемом научном издании. Еще до начала работ стоит подумать: в каком виде я собираюсь описать новый алгоритм?
В настоящее время можно выделить четыре распространенных способа такого описания.
1. Описание на естественном языке, пожалуй, самый легкий способ. Это древнейший способ. Евклид (около 300 года до н.э.) и Эратосфен (276 год до н. э.) его использовали. Переводы и пересказы описаний их знаменитых алгоритмов широко применяются по сей день. Но и новейшие алгоритмы часто описывают этим способом. Правда, математических формул в таких описаниях стало сильно больше, по сравнению с древними описаниями. Основной недостаток этого способа — многозначность многих слов естественных языков. Поэтому существует не малый риск, что автора поймут неоднозначно. И т.о. не смогут воспроизвести его алгоритм. А воспроизводимость — одно из основных условий научного метода.
2. Описание на псевдокоде. Тоже очень популярный способ. Тут можно выделить два подхода:
2.1. Изобретение оригинального псевдокода. Так Дональд Кнут для своей знаменитой монографии «Искусство программирования для ЭВМ» специально придумал компьютер MIX и ассемблер MIXAL. Тут явный недостаток — высокий порог входа. Для первого издания этой монографии в прошлом веке, такой подход, возможно, был оправдан. К настоящему времени создано много эмуляторов MIX, позволяющих увидеть, как работают коды из книги. Но для не очень большой статьи изобретение оригинального языка не представляется оправданным.
2.2. Использование для псевдокода упрощенной версии существующего ЯП. Про этот подход будет сказано ниже.
3. Описание на ЯП. По сути, это уже не описание алгоритма, а его реализация в виде программы. Здесь недостатки очевидны. Если читатель не знаком с применяемым ЯП, то ему может быть сложно (от слова «совсем») понять суть алгоритма. Детализированная публикация программы может вызвать сложности в бумажном издании — недостаток места. А места обычно нужно больше, чем в первых двух способах. И чтение всей программы целиком, потребует больше времени и внимания.
4. Описание с помощью блок-схемы. Этот способ уже довольно давно стал популярным. Еще Эдсгер Дейкстра его использовал в «Заметках по структурному программированию».
Для описаний небольших алгоритмов блок-схемы, безусловно, очень привлекательны своей наглядностью. Но, к сожалению, с ростом числа ветвлений и циклов блок-схема разрастается и повышается трудность восприятия. В случае бумажного представления формат бумаги может оказаться мал для блок-схемы. В связи с этим нужно упомянуть визуальный ЯП ДРАКОН, в котором предприняты меры по преодолению означенных неудобств. Однако применение специального ЯП может вернуть нас к способу 3.
Исходя из сказанного, я выбрал для себя способ 2.2. На мой взгляд, одним из наиболее подходящих для псевдокода является виртовский Pascal. Его, похоже, знают и помнят все программисты, а кто не знает — стесняется в этом признаться. Pascal-образный (Pascal-like) псевдокод интуитивно понятен (всем кто знаком, хотя с одним универсальным ЯП) и обычно хорошо структурирован, если нарочно не засорять его чем-то громоздким, и, конечно же, не использовать пресловутый goto. Для такого псевдокода доступны чекеры, и не только спелл-чекеры для правки комментариев, но и код-чекеры для кода. В роли последних выступают компиляторы и интерпретаторы Pascal. Например, очень удобен Dr Pascal. Превратить текст на псевдокоде в съедобный для транслятора обычно труда не составляет. Мне представляется очень важным, что Pascal — жестко типизированный ЯП, последовательно реализующий принципы защитного программирования. – На этапах разработки и проверки алгоритма, средства минимизации багов очень важны. А вот трюки, типа неявных преобразований бывают вредными.
Два слова про комментарии: считаю, что комментировать нужно уже в описании алгоритма. Причем комментировать достаточно подробно – это поможет поиску ошибок, и при написании статьи. Бывают трудные задачи, которые непонятно, как решать. Тогда я начинаю со способа 1. Записываю идеи решения в текстовой файл. Далее пытаюсь детализировать эти записи, выделить подзадачи и перейти к способу 2.2. Аналогично поступаю, если есть ТЗ. Правлю копию ТЗ с целью перейти к способу 2.2. Фразы от способа 1 оформляю комментариями. Такой прием помогает выбрать значимые имена. Если работа не на заказ, то сам пишу себе ТЗ. Описание алгоритма нужно и в случае, если не собираетесь его публиковать. Проходит время, и вы с удивлением смотрите на исходный код, реализующий алгоритм, который вам был когда-то совершенно понятен.
Еще про значимые имена – они очень важны, но комментарии не отменяют. Попробуйте впихнуть в значимое имя фразу: загрузить из архивного файла, записи для товарных вагонов, расшифровать их, пустые вагоны добавить в таблицу свободных вагонов. Получите довольно длинное имя, которое либо каждый раз безошибочно набирать, либо копировать, что может потребовать частые промотки текста. Код с такими много раз повторяющимися именами будет объемнее, чем код с единственным комментарием.
Следующим шагом после написания и описания нового алгоритма может быть его реализация и испытания полученной программы. Иногда это оправдано до доказательства корректности и теоретических оценок эффективности. — Зачем оценивать алгоритм, который врет. Для реализации использую IDE Delphi-7. Здесь у меня личная историческая причина. К примеру, если мой алгоритм на графах, то для испытаний нужно будет грузить графы. Их быстрее набирать в виде списка смежности, а для алгоритма нужна матрица смежности. Ну не писать же мне для каждого алгоритма процедуры трансляции списка в матрицу? — Понятно, что возьму эти процедуры из своего старого кода. Но почему Delphi-7, а не более новое? — К сожалению, проблемы несовместимости. Ну, а зачем с виртовского Pascal переносить на ОО Pascal Delphi? — Он ОО; зачастую даже для испытаний полезен или, даже, нужен GUI; иногда нужно испытать параллельный алгоритм и т. д. Использую не только свои старые процедуры I/O, но и, к примеру, реализацию поиска кратчайшего пути в графе, сортировку и т.д.
Но, конечно, «устарелость» Delphi-7 дает себя знать. OpenCV удалось применить и надписи в GUI Юникодом сделать (иначе под Windows 10 у моего любезного тестера не читались), а вот для CUDA пришлось переходить на C++. Отмечу, что когда программирую, то offline под Windows ХР SP 3 (с отсутствием Юникода в Delphi-7 проблем не возникает), а для online гружу другую ОС.
Говоря про испытания алгоритма, нужно отметить, что удачная работа программы — это хорошо, но, зачастую, не достаточно. Обычно нужно математически строгое доказательство.
Если лень или не удается строго доказать (самому или с чьей-то помощью), то иногда автор алгоритма объявляет его эвристическим. В общем, это может быть не страшно плохо. Есть задачи, для которых никто не нашел строгого решения. Есть такие, где ошибки не катастрофичны, например, в играх. Но есть и другие задачи. Например, поиск изоморфизма двух графов. Это известная открытая проблема, где нужно доказать, что эту задачу можно решить за полиномиальное время от числа вершин графа или, что такого решения быть не может. Притом, что открытой является и проблема P ?= NP. Предложено много эвристических алгоритмов поиска изоморфизма графов, только они никому не нужны.
После успешной проверки можно причесать программу. Сделать GUI удобным, подумать об оптимизации.
Здесь я написал про свой подход. Он, конечно, не единственный. Некоторые математики, не умея программировать и не зная ни одного ЯП, предлагают прекрасные алгоритмы для самых разных задач. Для описания алгоритма используют обычно способ 1 — естественный язык с большим количеством математических формул. Я же придерживаюсь взгляда, что CS — экспериментальная наука, разделяя мнения Аллена Ньюэлла и Герберта А. Саймона (Newell, Allen; Simon, H. A. (1976), «Computer Science as Empirical Inquiry: Symbols and Search» (1975 ACM Turing Award Lecture), Communications of the ACM, 19).
