Программистская графофилия и языки программирования

    Продолжение и, скорее всего, окончание моего исследования про графы из текстов.
    Мне подсказали страницу, где есть реализация одного алгоритма (QuickSort) на разных языках программирования, а значит есть отличная возможность сравнить графы этих «одинаковых» программ.
    Под катом полученные графы для языков: C, C++, Java, Visual Basic, Delphi, Python, Php, Prolog, Fortran, Ruby, Haskell, Algol, Mathematica, Asm.
    Попробуйте не заглядывая под кат угадать, какой граф будет наиболее красивым и какой самым страшным?



    Самым страшным языком программированияграфом я провозглашаю Фортрановский (сама программа, надо признать, была еще страшнее графа):


    Ненамного лучше него, правда, выглядит граф Visual Basic, хотя кода там гораздо меньше:


    А вот граф Algol-а (хоть и выглядит запутано, но тут есть определенная кластеризация):


    Следом можно поставить Delphi (а тут кластеризации нет вообще):


    Удивительно неплохо на их фоне смотрится ассемблер:


    Java почему-то подкачала. Я думал ее граф будет красивее, а получилось это:


    Вот граф одной из реализаций на Python:


    А вот реализация на C++ с шаблонами и итераторами. Удивительно, но неплохо выглядит:


    Дальше идут примерно одинаковые по красоте на мой взгляд графы.
    Prolog:


    Ruby:


    Php:


    C (вот уж не думал, что C и Php окажутся рядом, да и вообще чем-то похожи):


    Очень интересно выглядит граф языка Mathematica:


    Ну и наконец победитель, которого наверняка никто не угадал — это язык Haskell. Идеал минимализма:


    Upd: А вот и ссылка на новую книгу про Haskell, которая выйдет только в ноябре. Но уже сейчас авторы выложили ее в открытый доступ в онлайне. Кто еще не знаком с этим красивым языком — могут познакомиться бесплатно.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 82

      +4
      Спасибо, интересно было посмотреть.
      Да, действительно «Haskel» никто не угадал, добавте к «Haskel» еще одну 'l'. (:
      А если серьезно, то, наверное, большенство отгадало, haskell единственный чисто функциональный язык в списке.
        +24
        А теперь давайте проанализируем, почему же получились такие результаты? Наверное дело не совсем в «функциональности» языка, а в его «многословности». На java часто поступают жалобы из-за ее verbose style, что мы и увидели на графе — слегка запутанная семантика. А структурированность ассемблера не так уж удивительна, ведь операторов в нем не так уж и много и они часто используются. Судя по всему подобные графы — это репрезентация какой-то что ли поэтичности :) как в примере с «Анчаром» Пушкина. Следовательно, языки с наиболее красивыми графами — более поэтичны и душа поет, когда на них пишешь :)
          +1
          Лучший комментарий к исследованию :)
            0
            а что там с Анчаром, просветите, пожалуйста
              0
              В моем предыдущем посте про анчар было — у стихов Пушкина самые красивые графы получались, почему-то :)
            +2
            Да, угадать было несложно, Хаскель немногословен и функционален. Но есть маленькое но.

            qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qosrt (filter (>= x) xs)

            Это немножко не тот quick sort, что у остальных языков.
            Его можно почти прямо переписать на другие языки, если там есть лямбды, выглядеть будет пострашнее, но всё равно.
            К сожалению, быстрого алгоритма и при этом красивого я не видел.
              0
              Переносы убрались (как их в коде проставить?)
              qsort [] = []
              qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>= x) xs)
                0
                в чем ето непонравится?
                quicksort [] = []
                quicksort (s: xs) = quicksort [x|x < — xs, x < s] ++ [s] ++ quicksort [x|x < — xs, x >= s]
                0
                где в графе хаскельного варианта лямбды?
                по какому принципу строились эти графы?
                  0
                  Наверное такой вариант будет лучше и быстрее. Не знаю. Но на глаз памяти он меньше должен есть :)

                  quicksort x =
                      quicksort' x []
                      where
                        quicksort' [] y     = y
                        quicksort' [x] y    = x:y
                        quicksort' (x:xs) y = part xs [] [x] []  
                            where
                              part [] l e g = quicksort' l (e ++ (quicksort' g y))
                              part (z:zs) l e g 
                                  | z > x  = part zs l e (z:g) 
                                  | z < x  = part zs (z:l) e g 
                                  | z == x = part zs l (z:e) g
                  
                  0
                  Жаль нет C#… Хотелось бы увидеть его на общем фоне (думаю будет что-то типа Java).
                    +1
                    Да, у него абсолютно такой же граф получился
                      +2
                      Думаете при использовании лямбда выражений будет тоже самое?
                              public static IEnumerable<double> s(IEnumerable<double> arr)
                              {
                                  if(arr.Count()<=1)
                                      return arr;
                                  var c = arr.First();
                                  var sMin = arr.Where(x => x < c);
                                  var sMax = arr.Where(x => x > c);                        
                                  return s(sMin).Union(new []{c}).Union(s(sMax));
                              }

                      Думаю граф будет не очень ужасным
                        +1
                        Это рабочий пример?

                        Вот его граф, не так уж и хорош, как на Хаскеле :)

                          0
                          Да, пример рабочий, правда использует ту-же сортировку, что и в Хаскелле, то есть капельку отличающуюся от совсем классической.
                          Чуть ниже привел пример где убраны несколько эллементов, типа одноразово используемых sMin и sMax.
                          +2
                          Или чуть более изящно, но думаю граф не изменится.
                                  public static IEnumerable<double> s(IEnumerable<double> arr){
                                      var c = arr.FirstOrDefault();
                                      return arr.Count() <= 1 ? arr : s(arr.Where(x => x < c)).Union(new[] { c })
                                          .Union(s(arr.Where(x => x > c)));
                                  }
                            0
                            Не, граф стал тоже поизящнее :)

                              +2
                              Можно его еще немного урезать, но уже читерскими методами:
                                      IEnumerable<double> sort(IEnumerable<double> a){
                                          double c = a.FirstOrDefault();
                                          return a.Count() <= 1 ? a : sort(a.Where(x => x < c)).Union(new[]{ c })
                                              .Union(sort(a.Where(x => x > c)));
                                      }

                              Таким образром сортировка становится private членом класса, становится нестатической.
                              К тому-же парсер не далует однобуквенные сочетания — заменяем имя массива.
                              Ну и вместо удобного var можно использовать double, который добавит только новые связи.

                              По идеи граф станет не таким кластеризованным (тут видно два кластера — обьявление функции и ее реализация), но число вершин станет меньше.
                                0
                                Да, теперь кластеризации нет. Реализация простая и прямая:

                            0
                            Воо. Таки я ошибся, граф куда лучше явавского.
                              0
                              Это из-за того, что c# 3.0, да ещё и с использованием linq.
                              На 2.0 все было бы практически аналогично.
                                –3
                                Прогрессируют :)
                                  0
                                  Прогресс, на то и прогресс, чтобы становиться лучше себя и других.
                          0
                          С Фортрантом не угадал, а насчет Хаскела — был уверен, что он будет первый
                            –3
                            Ух, откуда вы все про Хаскел знаете? :)
                              0
                              Ну так тут не просто кодеры собрались, а как по другому без хаскела?
                                –3
                                Я про хаскел только название слышал :)
                                А так — все по старинке, C да C++
                                  +1
                                  Ну это вы зря, попробуйте хаскел, lisp, SICP почитайте, мозги очень будут вам благодарны
                                    –3
                                    lisp изучал и даже писал что-то на нем давным давно. Из других языков изучаю более востребованные на мой взгляд — из .net, java, ActionScript и т.п.
                                    А для вникания в Хаскел, лисп и SICP нужно гораздо больше времени, чем для простых языков. А времени всегда не хватает
                                      0
                                      Результат себя «окупает» — качественно измененяется мышление, «востребованные» языки же языки количественно увеличивают знание «синтаксисов».
                                        0
                                        Ага, здесь уже была статья — крик души, человека, изучившего хаскель и страдающего от того, что теперь ему приходится писать на грубом сишарпе, что его нежной душе сугубо противно :).
                                          0
                                          Яблоко познания отдало горечью )) Такое тоже бывает.
                            0
                            Угадал оба! Но скорее не в силу экстрасенсорных способностей, а потому что по невнимательности не заметил ассемблер и алгол :). Ну а с хаскеллом все ясно было с самого начала.
                              0
                              а брейнфак не учавствовал по причине явного преимущества — отсутствии слов?
                                –3
                                Почему, там есть слова — из плюсов :)
                                Я его за красивый язык не посчитал сразу и не стал проверять.
                                  0
                                  тогда и в хаскеле есть «слова из плюсов». по хорошему надо все операторы преобразовать в слова, чтобы та софтина нарисовала честный граф.
                                    –3
                                    Можно попробовать, но тогда графы позапутаннее будут.
                                +1
                                Хаскелл однозначно рулит… Последние месяца три разбираюсь, и все больше начинаю влюбляться.

                                Однако, все еще немного дергает из-за плотности упаковки информации в коде. Монады, стрелки, list comprehentions… Это все просто такие крутые способы запихнуть максимум алгоритма в минимум кода. Изучать язык надо поаккуратней и подольше.
                                  0
                                  Посмотрите язык K :) Причем это вполне коммерческий язык
                                    0
                                    Да ну его в болото! Во-первых, пропиетарный, во-вторых, еще более редкий, чем даже сравнительно маргинальный Хаскелл.

                                    Хотя вот про Гуй на Вики пишут, что очень круто и просто пишется. Сие есть истина, не знаешь?
                                      0
                                      Не сказал бы что более редкий, он (точнее Q + Kdb) имхо более востребован чем Хаскел. Хотя и там и там проектов кот наплакал.

                                      А Гуй на нем не представляю как нарисовать… для кнопочек и прочих окон там разве чтото есть?
                                        0
                                        Даже не знаю, как вообще можно сравнивать промышленную потребность в таких редких языках по России :-) Но на слуху вроде больше Хаскелл.

                                        Из функциональных здесь я только по Erlang вакансии встречал.
                                          0
                                          Я знаю как минимум 1 коммерческий проект выполненный на K в России, т.е. с этим проектом я лично знаком. Есть большие подозрение что помимо него были другие, но конечно очень мало. На Erlang'е проектов гораздо больше. K берут из-за того что на нем офигительно быстро можно считать всякие OLAP, а Erlang потому что он не то что железобетонный, он вообще нерушим, что важно для приложений с 5ю девятками. А Haskell ничем таким, кроме самого языка, не засветился :( Но сам язык отличный, спору нет.
                                        0
                                        Да, примером я его указал не как язык круче или еще что. А как пример минимума кода
                                          0
                                          Ну может быть, может быть… Но на еще один Хаскелл моего энтузиазма уже не хватит :-D
                                    +2
                                    Странно, что вы Perl упустили? довольно лаконично:
                                    image
                                      0
                                      Да, пожалуй можно его поместить там же, где C и PHP.
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        Почему-же, я вполне ожидал увидеть Haskell или ocaml. Выразительная сила этих языков вполне себе хороша.
                                          +1
                                          Модифицировал функцию для PHP, сделав ее более лаконичной:
                                          function mine_quicksort($seq) {
                                          	$length = count($seq);
                                          	if ($length == 0) {
                                          		return $seq;
                                          	}
                                          	$x = $y = array();
                                          	$k = array_shift($seq);
                                          	$x = array_filter($seq, create_function('$s', 'return $s <= '.$k.';'));
                                          	$y = array_diff($seq, $x);
                                          	return array_merge(mine_quicksort($x), array($k), mine_quicksort($y));
                                          }

                                          … что, однако, не повлияло, как мне показалось, на красивость графа:
                                          image
                                            +1
                                            При этом погонял код в профайлере и выяснил, что мой код в 3 раза медленнее кода из теста автора и в 73(!!!) раза медленнее встроенной функции sort.
                                              0
                                              Зато короче и красивее :)
                                            –2
                                            Зачем модифицировать функцию на PHP если Like most PHP sorting functions, sort() uses an implementation of Quicksort?

                                            Так что на PHP граф будет эквивалентен Haskell.
                                              0
                                              Надо понимать различия между реализацией функции и вызовом функции. Во многих языках qsort реализован, но сравниваются именно реализации, а не вызовы.
                                              +1
                                              Переработал исходник на PHP и получил вот это:
                                              function mine_quicksort($seq) {
                                              	$f = array('count', 'array_shift', 'array_filter', 'create_function', 'array_diff', 'array_merge', 'mine_quicksort');
                                              	$l = $f[0]($seq);
                                              	$r = $seq;
                                              	if ($l != 0) {
                                              		$x = $y = array();
                                              		$k = $f[1]($seq);
                                              		$x = $f[2]($seq, $f[3]('$s', 'return $s <= '.$k.';'));
                                              		$y = $f[4]($seq, $x);
                                              		$r = $f[5]($f[6]($x), array($k), $f[6]($y));
                                              	}
                                              	return $r;
                                              }

                                              Теперь граф выглядит так:
                                              image
                                                0
                                                С текстовым вариантом чаще работать приходится, чем с графом :)
                                                  0
                                                  Абсолютно согласен! Но вы же должны понимать, что все, что представляется в данном топике имеет чисто спортивный интерес.
                                                  Кстати, если переписать на PHP 5.3 (с замыканиями), то думаю график еще уменьшился бы.
                                                0
                                                Подсмотрел, что нахваливаемый всеми Haskell добивается такого графа за счет того, что программа уважаемого автора (точнее GraphViz) не учитывает в качестве слов последовательности меньшие по длине, чем 2 буквы. Соответственно, модифицировал исходник и получил вот что:
                                                function q($s) {
                                                	$f = array('count', 'array_shift', 'array_filter', 'create_function', 'array_diff', 'array_merge');
                                                	$l = $f[0]($s);
                                                	$r = $s;
                                                	if ($l != 0) {
                                                		$x = $y = $m = array();
                                                		$k = $f[1]($s);
                                                		$x = $f[2]($s, $f[3]('$s', 'return $s <= '.$k.';'));
                                                		$y = $f[4]($s, $x);
                                                		$m[] = $k;
                                                		$r = $f[5](q($x), $m, q($y));
                                                	}
                                                	return $r;
                                                }

                                                Правда, получился уже какой-то ассемблер.
                                                Вот результат:
                                                image
                                                  0
                                                  >> что программа уважаемого автора (точнее GraphViz) не учитывает в качестве слов последовательности меньшие по длине, чем 2 буквы
                                                  Там можно и 1 букву выбрать в комбо боксе.
                                                    0
                                                    Тогда у Haskell будет совершенно иной граф.
                                                    Вы-то строили при 2.
                                                    Вот я и пытаюсь выправить положение :)
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    0
                                                    Да, красивый получился:



                                                    А выбран был другой наверное потому, что этот код не совсем типичен для питона.
                                                      +2
                                                      Почему это нетипичен? List comprehensions широко применяются. Другое дело, что так сортировать изменяемый список (массив по сути) никто в здравом уме не будет, но тогда для любого языка типичным кодом будет вызов одной функции стандартной библиотеки :-)
                                                    +1
                                                    Переделал реализацию заново, с минимальным использованием функций PHP.
                                                    Заранее предупреждаю: это чисто спортивный интерес, реализовывать quicksort на PHP (да еще и так!) не нужно!
                                                    Получилась вообще какая-то вакханалия…
                                                    function q($s) {
                                                    	$l = count($s);
                                                    	$r = $s;
                                                    	if ($l != 0) {
                                                    		$x = $y = $r = array();
                                                    		$d = $f = 0;
                                                    		$k = $s[0];
                                                    		for($i=1; $i < $l; $i++) {
                                                    			if($s[$i] <= $k) {
                                                    				$x[] = $s[$i];
                                                    				$d++;
                                                    			} else {
                                                    				$y[] = $s[$i];
                                                    				$f++;
                                                    			}
                                                    		}
                                                    		$a = q($x);
                                                    		$b = q($y);
                                                    		for($i=0;$i<$d;$i++){
                                                    			$r[] = $a[$i];
                                                    		}
                                                    		$r[] = $k;
                                                    		for($i=0;$i<$f;$i++){
                                                    			$r[] = $b[$i];
                                                    		}
                                                    	}
                                                    	return $r;
                                                    }

                                                    Ну и результат:
                                                    image
                                                      +3
                                                      Кстати, хотелось бы выступить в защиту Фортрана!
                                                      На той странице — это единственная нерекурсивная реализация алгоритма. Отсюда и сложность!
                                                        0
                                                        а в руби сортировка делается не по методу quick? тогда будет выглядеть аналогично хаскелю
                                                        не пойму, почему в одних случаях использовали готовые qsort, а в других шаманили сортировку вручную?
                                                          0
                                                          В каких случая готовую qsort использовали? Все отграфленные варианты — это реализации qsort, а не его использование
                                                            0
                                                            это не вызов готового qsorta, а рекурсия
                                                            0
                                                            Так и знал, что Хаскель всех уделает. %)

                                                            Clean тоже был бы на высоте.
                                                              0
                                                              На Clean получился бы абсолютно чистый граф :)
                                                              0
                                                              интереснее все таки смотреть на что-нибудь типа CFG/DFG, ибо программист читающий программу в первую очередь интересуется именно тем, как идёт управление и текут данные, а не то как часто слово then стоит рядом со словом if
                                                                0
                                                                Раньше писями мерялись, теперь красотой графов ;)
                                                                  0
                                                                  интересно было-бы эрланг посмотреть. ))
                                                                    0
                                                                    Давайте код на эрланге — дам граф :)
                                                                      0
                                                                      так на указанной вами странице он есть ))
                                                                      qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).
                                                                        +1
                                                                        Вот, красота:

                                                                          0
                                                                          спасибо ))
                                                                            0
                                                                            Ну слава богу, а то я уже испугался, что будет что-то страшное :)
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                          –4
                                                                          Весь этот эксперимент — сплошной brainfuck :)
                                                                          0
                                                                          Scala нумбер уан:
                                                                          def sort(xs: Array[Int]): Array[Int] = 
                                                                            if (xs.length <= 1) xs 
                                                                            else { 
                                                                              val pivot = xs(xs.length / 2) 
                                                                              Array.concat( 
                                                                                sort(xs filter (pivot >)), 
                                                                                xs filter (pivot ==), 
                                                                                sort(xs filter (pivot <))) 
                                                                            } 
                                                                          


                                                                          Ну и второй вариант в Haskell-стиле с pattern matching
                                                                          def qsort(xs: List[Int]): List[Int] = {
                                                                              xs match {
                                                                                  case List() => xs
                                                                                  case _ =>  qsort(for(x <- xs.tail if x < xs.head) yield x) ::: List(xs.head) ::: qsort(for(x <- xs.tail if x >= xs.head) yield x)
                                                                              }
                                                                          }
                                                                          


                                                                          Можно сделать и нумбер 3 — примерно как Java/C.

                                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                          Самое читаемое