Pull to refresh

Comments 82

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

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

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

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
Жаль нет C#… Хотелось бы увидеть его на общем фоне (думаю будет что-то типа Java).
Да, у него абсолютно такой же граф получился
Думаете при использовании лямбда выражений будет тоже самое?
        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));
        }

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

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

Да, пример рабочий, правда использует ту-же сортировку, что и в Хаскелле, то есть капельку отличающуюся от совсем классической.
Чуть ниже привел пример где убраны несколько эллементов, типа одноразово используемых sMin и sMax.
Или чуть более изящно, но думаю граф не изменится.
        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)));
        }
Можно его еще немного урезать, но уже читерскими методами:
        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, который добавит только новые связи.

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

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

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

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

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

Из функциональных здесь я только по Erlang вакансии встречал.
Я знаю как минимум 1 коммерческий проект выполненный на K в России, т.е. с этим проектом я лично знаком. Есть большие подозрение что помимо него были другие, но конечно очень мало. На Erlang'е проектов гораздо больше. K берут из-за того что на нем офигительно быстро можно считать всякие OLAP, а Erlang потому что он не то что железобетонный, он вообще нерушим, что важно для приложений с 5ю девятками. А Haskell ничем таким, кроме самого языка, не засветился :( Но сам язык отличный, спору нет.
Да, примером я его указал не как язык круче или еще что. А как пример минимума кода
Ну может быть, может быть… Но на еще один Хаскелл моего энтузиазма уже не хватит :-D
Странно, что вы Perl упустили? довольно лаконично:
image
Да, пожалуй можно его поместить там же, где C и PHP.
UFO just landed and posted this here
Почему-же, я вполне ожидал увидеть Haskell или ocaml. Выразительная сила этих языков вполне себе хороша.
Модифицировал функцию для 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
При этом погонял код в профайлере и выяснил, что мой код в 3 раза медленнее кода из теста автора и в 73(!!!) раза медленнее встроенной функции sort.
Надо понимать различия между реализацией функции и вызовом функции. Во многих языках qsort реализован, но сравниваются именно реализации, а не вызовы.
Переработал исходник на 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
С текстовым вариантом чаще работать приходится, чем с графом :)
Абсолютно согласен! Но вы же должны понимать, что все, что представляется в данном топике имеет чисто спортивный интерес.
Кстати, если переписать на PHP 5.3 (с замыканиями), то думаю график еще уменьшился бы.
Подсмотрел, что нахваливаемый всеми 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
>> что программа уважаемого автора (точнее GraphViz) не учитывает в качестве слов последовательности меньшие по длине, чем 2 буквы
Там можно и 1 букву выбрать в комбо боксе.
Тогда у Haskell будет совершенно иной граф.
Вы-то строили при 2.
Вот я и пытаюсь выправить положение :)
UFO just landed and posted this here
Да, красивый получился:



А выбран был другой наверное потому, что этот код не совсем типичен для питона.
Почему это нетипичен? List comprehensions широко применяются. Другое дело, что так сортировать изменяемый список (массив по сути) никто в здравом уме не будет, но тогда для любого языка типичным кодом будет вызов одной функции стандартной библиотеки :-)
Переделал реализацию заново, с минимальным использованием функций 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
Кстати, хотелось бы выступить в защиту Фортрана!
На той странице — это единственная нерекурсивная реализация алгоритма. Отсюда и сложность!
а в руби сортировка делается не по методу quick? тогда будет выглядеть аналогично хаскелю
не пойму, почему в одних случаях использовали готовые qsort, а в других шаманили сортировку вручную?
В каких случая готовую qsort использовали? Все отграфленные варианты — это реализации qsort, а не его использование
это не вызов готового qsorta, а рекурсия
Так и знал, что Хаскель всех уделает. %)

Clean тоже был бы на высоте.
На Clean получился бы абсолютно чистый граф :)
интереснее все таки смотреть на что-нибудь типа CFG/DFG, ибо программист читающий программу в первую очередь интересуется именно тем, как идёт управление и текут данные, а не то как часто слово then стоит рядом со словом if
Раньше писями мерялись, теперь красотой графов ;)
Давайте код на эрланге — дам граф :)
так на указанной вами странице он есть ))
qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).
Ну слава богу, а то я уже испугался, что будет что-то страшное :)
UFO just landed and posted this here
UFO just landed and posted this here
Весь этот эксперимент — сплошной brainfuck :)
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.
Sign up to leave a comment.

Articles