Блог русскоязычной поддержки Wolfram Mathematica

Длина кодов, измеренная для 14 языков программирования

Перевод поста Джона Маклуна (Jon McLoone), International Business & Strategic Development, Wolfram Research, Inc.

Нажмите, чтобы скачать данный пост в виде ноутбука Mathematica...

Общее количество использованных в посте встроенных функций или символов: 116

Список имен используемых встроенных функций и символов в порядке их появления в коде:
CompoundExpression (;) | SetDelayed (:=) | Pattern (:) | BlankNullSequence (___) | Set (=) | Import | Sort | Select | ReplaceAll (/.) | Function (&) | And (&&, ∧) | StringMatchQ | Slot (#) | Not (!, ¬) | Alternatives (|) | RuleDelayed (:>, :->) | Blank (_) | String ("...") | StringReplace | Rule (->, ->) | Cases | DeleteCases | StringJoin (<>) | Condition (/;) | StringExpression (~~) | List ({...}) | Apply (@@) | Intersection (∩) | Map (/@) | If | FileExistsQ | Get (<<) | Monitor | Do | Part ([[…]]) | Span (;;) | DumpSave | Length | Block | Greater (>) | XMLElement | ToLowerCase | Position | Extract | MemberQ | Infinity | Equal (==) | First | ReplaceRepeated (//.) | Plus (+) | StringCount | Repeated (..) | StringLength | StringSplit | Complement | Characters | FromCharacterCode | Range | CharacterRange | Through | Take | ListPlot | AspectRatio | Automatic | AxesLabel | Style | Bold | Epilog | Dashing | Thick | Red | Line | PlotRange | All | ImageSize | Show | MovingMedian | SortBy | Mean | Plot | Times (*, ×) | Sqrt | PlotStyle | GraphicsGrid | Partition | Table | Frame | True | Axes | None | FrameLabel | Median | N | Power (^) | Drop | Floor (⌊...⌋) | Panel | Labeled | FontFamily | Grid | Transpose | Join | Prepend | Rotate | Pi (π) | Reverse | PadRight | Round | ItemStyle | Directive | Spacings | Dividers | Background | Orange | Alignment | Center

Оригинальный пост: Code Length Measured in 14 Languages
Перевод сделал Максим Сахаров, студент МГТУ им. Баумана
Адаптация кода: Осипов Роман, администратор Русскоязычной поддержки Wolfram Mathematica

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

После того как я отправил туда решения некоторых задач (например, метод “наводнения” (Flood filling) для заливки областей разной формы, вычисления углового среднего (Mean angle), а также суммирования цифр целого числа (Sum digits of an integer)) я понял, что этот ресурс предоставляет уникальную возможность количественно подтвердить гипотезу, которую я высказываю последние несколько лет — код написанный в Mathematica часто бывает короче чем эквивалентный код на других языках, благодаря, как его высокому уровню абстракции, так и встроенным вычислительным возможностям.

Вот что у меня получилось в итоге:

Код написанный в системе Mathematica обычно занимает меньше трети эквивалентного кода на других языках и часто лучше.

Чтобы предупредить возможные недовольные комментарии необходимо сказать что в данном вопросе существует множество внешних факторов. Всегда играет немаловажную роль, например, процесс создания задачи, личность человека решающего задачу, а также избирательность решения. Но если мы будем слишком много об этом задумываться, то так ничего и не сделаем!

Также необходимо сказать следующее — короткий код и хороший код это разные вещи. Но хороший короткий код лучше хорошего длинного кода и уж тем более плохой короткий код лучше плохого длинного кода!

Естественно я использовал Wolfram Mathematica, чтобы собрать необходимые для анализа данные.

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

закрыть

importOnce[args___] := importOnce[args] = Import[args];

Теперь импортируем ключевые веб страницы. Первая хранит список всех языков поддерживаемых проектом. Я использовал опцию “Hyperlinks” («Гиперссылки») в HTML Import и затем отсеял все ссылки неподходящего типа.

закрыть

languages = Sort@Select[ importOnce[ "http://rosettacode.org/wiki/Category:Programming_Languages", "Hyperlinks"], StringMatchQ[#, "http://rosettacode.org/wiki/Category:*"] && ! StringMatchQ[#, "*Programming*" | "*Languages*" | "*Encyclopedia*" | "*Cach*"] & /. x_String :> StringReplace[x, "http://rosettacode.org/wiki/Category:" -> ""]];

Для каждого языка существует специальная страница где содержатся выполненные задания поэтому сделаем следующее...

закрыть

getCompletedPageList[language_String] := Cases[DeleteCases[importOnce[StringJoin["http://rosettacode.org/wiki/Category:", StringReplace[language, " " -> "_"]], "Hyperlinks"], x_String /; StringMatchQ[x, StringExpression["*Category:*" | "*Reports:*" | "*Rosetta_Code*" | "*Language_Comparison_Table*" | "*Help:*" | "*User:*" | "*Special:*" | StringJoin["*", StringReplace[language, " " -> "_"]]]]], x_String /; StringMatchQ[x, "http://rosettacode.org/wiki/*"]]

... и модернизируем команду чтобы она принимала на вход список языков и выдавала задания выполненные на всех языках

закрыть

getCompletedPageList[langs_List] := Intersection @@ getCompletedPageList /@ langs

Следующий шаг необязателен но Вам придется столкнуться с медленным интернетом на каком либо шаге выполнения программы, поэтому я предпочитаю обходить эту проблему в самом начале систематически вызываю функцию Import для всех данных которые мне могут понадобиться. Также я сброшу данные на диск в компактном бинарном .mx файле, теперь я могу забрать их в любое удобное время не подключаясь к сайту вновь. Но пока этот код выполняется — самое время перекусить.

закрыть

If[FileExistsQ["I:\\Wolfram\\AllMathematicaBlog\\post_33\\RosettaCodeData.mx"], << "I:\\Wolfram\\AllMathematicaBlog\\post_33\\RosettaCodeData.mx", Monitor[Do[importOnce[current, "XMLObject"], {current, importOnce["http://rosettacode.org/wiki/Category:Programming_Tasks", "Hyperlinks"][[3 ;; -33]]}]; Do[getCompletedPageList[current], {current, languages}]; , current]; DumpSave["I:\\Wolfram\\AllMathematicaBlog\\post_33\\RosettaCodeData.mx", importOnce]];

Теперь когда мы собрали все необходимые данные, начнем анализ. Во-первых узнаем сколько тестовых задач было решено и отправлено сообществом пользователей Wolfram Mathematica.

закрыть

Length[getCompletedPageList["Mathematica"]]

Весьма неплохо. Больше всего задач было решено на языке Tcl — 701 задача. Но нам куда важнее знать сколько задач было решено не только в Mathematica но и с использованием других основных языков программирования. К примеру 495 задач решено одновременно на Си и в Mathematica:

закрыть

Length[getCompletedPageList[{"Mathematica", "C"}]]

Тяжелой задачей является извлечение правильной информации из написанных руками с информацией из разных источников страниц wiki. Правильно написанная страница хранит код в тэге <lang> с различными аргументами для разных языков.

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

закрыть

extractCode[path_, language_] := extractCode[path, language] = Block[{langPos, langhead, allheads, nexthead, codeText, codeXML, pageXML, posGreater, source, text}, posGreater[a_, b_] := a[[-1]] > b[[-1]]; pageXML = importOnce[path, "XMLObject"] /. XMLElement[tag_, b___] :> XMLElement[ToLowerCase[tag], b]; Null; langPos = Position[pageXML, "class" -> StringJoin[languageTag[language], " highlighted_source"]]; Null; If[Length[langPos] > 0, codeXML = (Extract[pageXML, #1[[1 ;; -3]]][[3]] & ) /@ langPos, langhead = Position[pageXML, XMLElement["h2", _, cts_] /; MemberQ[cts, language, Infinity]]; Null; If[Length[langhead] == 1, langhead = First[langhead]; Null; allheads = Sort[Position[pageXML, XMLElement["h2", _, _]]]; Null; nexthead = allheads /. {{a___, langhead} -> Infinity, {a___, langhead, n_, b___} -> n}; Null; codeXML = Extract[pageXML, Select[Position[pageXML, XMLElement["pre", {"class" -> "text highlighted_source"}, source_]], posGreater[#1, langhead] && posGreater[nexthead, #1] & ]], codeXML = ""]]; StringJoin @@ (codeXML //. {XMLElement["pre", {"class" -> "text highlighted_source"}, source_] -> source, XMLElement["br", _, _] -> "\n", XMLElement[_, _, {text___}] -> text})]

Если используется тэг <lang> то он чаще всего содержит имя языка в нижнем регистре без пробелов, но не всегда! Поэтому приходится обрабатывать некоторые отдельные случаи.

закрыть

languageTag[lang_String] := ToLowerCase[StringReplace[StringReplace[lang, "_" -> " "], {"C++" -> "cpp", "#" -> "sharp", "Common_Lisp" -> "Lisp", "Libery Basic" -> "lb", "Objective C" -> "objc", "BASIC" -> "qbasic", "UNIX Shell" -> "bash", "Visual Basic" -> "vb", " " -> "", "/" -> "", "-" -> ""}]];

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

Это мой код который извлекает мою реализацию метода “наводнения” (Flood filling) для заливки областей разной формы:

закрыть

example = extractCode["http://rosettacode.org/wiki/Bitmap/Flood_fill", "Mathematica"]

Далее нам необходима метрика для оценки длины кода. Обычно считается, что это количество строк кода:

закрыть

lineCount[str_] := StringCount[StringReplace[StringReplace[str, {" " -> "", "\t" -> ""}], "\n".. -> "\n"], "\n"] + 1;

Но так как на этот параметр существенно влияет разметка кода (в конце концов в Mathematica Вы можете в одной строчке написать сразу несколько команд), мы будем использовать в качестве метрики число символов которые не являются пробелами.

закрыть

characterCount[str_] := StringLength[StringReplace[str, {"\n" -> "", " " -> "", "\t" -> ""}]];

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

закрыть

tokenCount[str_String] := Length[DeleteCases[StringSplit[str, Complement[Characters[FromCharacterCode[Range[1, 127]]], CharacterRange["a", "z"], CharacterRange["A", "Z"], CharacterRange["0", "9"], {"."}]], ""]];

Применим каждую метрику для оценки моего кода решающего задачу метода “наводнения” (Flood filling) для заливки областей разной формы:

закрыть

Through[{lineCount, characterCount, tokenCount}[example]]

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

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

закрыть

compareLanguages[langList_List, metric_, path_] := (metric[extractCode[path, #1]] & ) /@ langList; compareLanguages[langList_List, metric_] := DeleteCases[(compareLanguages[langList, metric, #1] & ) /@ getCompletedPageList[langList], {___, 0, ___}]

Если мы сравним первые три задачи на языках Mathematica и Cи то увидим что в каждом случае Mathematica имеет преимущество по числу символов.

закрыть

Take[compareLanguages[{"Mathematica", "C"}, characterCount], 3]

Выведем все данные:

закрыть

ListPlot[compareLanguages[{"C", "Mathematica"}, characterCount], AspectRatio -> Automatic, AxesLabel -> (Style[#1, 14, Bold] & ) /@ {"C", "Mathematica"}, Epilog -> {Dashing[{0.01, 0.01}], Thick, Red, Line[{{0, 0}, {3000, 3000}}]}, PlotRange -> All, ImageSize -> 600]

На данном графике много лишнего шума но ясно одно — почти каждое решение в системе Mathematica короче, чем решение на языке Си. Некоторые выбросы вызваны тем что для одной задачи было предоставлено несколько решений которые мой код просто суммировал. Справиться с этим наилучшим образом позволит встроенная функция Median для усреднения и сглаживания.

Теперь мы видим интересную тенденцию. С ростом длины решения задач на языке Си растет и длина решения в Mathematica, однако эта зависимость нелинейна. Приблизительная формула имеет следующий вид , где c — число символов в решении на языке Си.

закрыть

Show[ListPlot[MovingMedian[SortBy[compareLanguages[{"C", "Mathematica"}, characterCount], Mean], 20]], Plot[5.5*Sqrt[x], {x, 0, 5000}, PlotStyle -> Thick], AxesLabel -> (Style[#1, 14, Bold] & ) /@ {"C", "Mathematica"}, ImageSize -> 600]

Схожее поведение наблюдается при сравнении с другими языками:

закрыть

GraphicsGrid[Partition[Table[ ListPlot[ MovingMedian[ SortBy[compareLanguages[{lang, "Mathematica"}, characterCount], Mean], 15], Frame -> True, PlotRange -> All, Axes -> None, FrameLabel -> {{Style["Mathematica", 14, Bold], None}, {Style[lang, 14, Bold], None}}, ImageSize -> 280], {lang, {"C++", "Python", "Java", "MATLAB"}}], 2]]

Это в целом неудивительно, так как некоторые задачи чрезвычайно просты. Существует разница от языка к языку между присваиванием значения переменной или организацией доступа к массиву. В больших задачах существует больше возможностей выиграть от высокого уровня абстракции языка Mathematica, к примеру в задаче, где необходимо реализовать игру сапер. Такая тенденция однако не будет продолжаться. Для больших задач соотношение будет становится более линейным при достижении стандартных размеров отдельных модулей кода в проекте.

На сайте перечислено 474 языка. Это слишком много для нашего анализа, и как следствие у нас будет слишком мало задач решенных на всех языках. Сосредоточимся на наиболее популярных языках и языках направленных на вычисления. Рассмотрим следующие из них:

закрыть

interesting = {"Mathematica", "Ruby", "Haskell", "Pascal", "Clojure", "MATLAB", "R", "JavaScript", "C sharp", "Python", "Common Lisp", "Java", "Fortran", "C++", "C"};

Чтобы представить данные в виде красивой таблицы  мне необходимо привести их к единому значению. Существует два подхода. Первый — привести все сравнения к отношению (длина кода на языке А) / (длина кода на языке В) и найти среднее значение по всем задачам. Другой подход заключается в предположении, что длина кода важна лишь на больших задачах и сделать все тоже самое но лишь для половины задач у которых средняя длина кода будет наибольшей.

закрыть

medianRatio[metric_, lang1_, lang2_] := Median[(N[#1[[2]]/#1[[1]]] & ) /@ DeleteCases[compareLanguages[{lang1, lang2}, metric], {___, 0, ___}]]; topMedianRatio[metric_, lang1_, lang2_] := Median[((N[#1[[2]]/#1[[1]]] & ) /@ Drop[#1, Floor[Length[#1]/2]] & )[SortBy[DeleteCases[compareLanguages[{lang1, lang2}, metric], {___, 0, ___}], Mean]]];

Для отображения результатов сравнения, создадим функцию, которая выдает таблицу сравнения:

закрыть

comparisonTable[title_, languages_List, metric_, ratio_] := Panel[Labeled[Style[title, 20, Bold, FontFamily -> "Arial"], Grid[Transpose[{Prepend[# & /@ interesting[[1 ;; -2]], "Большие чем 1 числа\nозначают, что код\nязыка сверху\n\ длиннее в это\nколичество раз\nязыка по горизонтали"]}~Join~ Transpose[{Rotate[#, Pi/2] & /@ Reverse[languages][[1 ;; -2]]}~ Join~(PadRight[#, Length[languages] - 1, ""] & /@ Table[Table[ Round[ratio[metric, languages[[i]], Reverse[languages][[j]]], 10^-2] // N, {j, 1, Length[languages] - i}], {i, 1, Length[languages] - 1}])]], ItemStyle -> Directive[{12, Bold, FontFamily -> "Arial"}], Spacings -> {0.6, 1}, Dividers -> {{1 -> True, 2 -> True, -1 -> True}, {1 -> True, 2 -> True, -1 -> True}}, Background -> {{None}, {2 -> Orange}}, Alignment -> {Center, Center}]]]

Наконец мы получили результаты по различным метрикам с использование двух описанных выше подходов.

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

закрыть

comparisonTable["Все задачи - Отношение количества символов", interesting, characterCount, medianRatio]

закрыть

comparisonTable["Все задачи - Отношение количества строк", interesting, lineCount, medianRatio]

закрыть

comparisonTable["Все задачи - Отношение количества токенов", interesting, tokenCount, medianRatio]

закрыть

comparisonTable["Большие задачи - Отношение количества символов", interesting, characterCount, topMedianRatio]

закрыть

comparisonTable["Большие задачи - Отношение количества строк", interesting, lineCount, topMedianRatio]

закрыть

comparisonTable["Большие задачи - Отношение количества токенов", interesting, tokenCount, topMedianRatio]

Несмотря на возможные неточности в данных — их источник является независимым (за исключением нескольких решений предоставленных мной), проблемы с кодом который не задумывался как короткий если это не оговорено в условии (например code golf), я думаю у нас получилось хорошее объективное сравнение. Если вы хотите отправить свою программу на Розеттский код просмотрите раздел нерешенных задач в системе Mathematica или улучшите уже существующие.

Не смотря на то что таблица “Большие задачи - Отношение количества строк” демонстрирует наиболее впечатляющие результаты для системы Mathematica, на мой взгляд “Большие задачи - Отношение количества символов” представляет наиболее объективные результаты. Как бы там ни было Mathematica предоставляет в среднем более короткий код чем другие рассмотренные языки. В среднем в пять — десять раз короче чем Си или С++ — что значит более быстрое время разработки, меньшую сложность кода и более легкую поддержку.

Блог принадлежит “Русскоязычной поддержке Wolfram Mathematica"©
При любом использовании материалов блога, ссылка на блог обязательна.
Создано с помощью Wolfram Mathematica 9