[haskell][быдлокод]Максимум от списка

P.S. Ассемблерщик

И не знаешь C? Плохо. Добавь принты и посмотри как вызывается max.

Компилер Цэ не сможет выполнить оптимизацию вида

int tmp = max1(vals+1,rest-1); 
if (rest) {
  if (*vals>tmp) { return *vals; }
  else { return tmp; }
} else { return *vals; }

Компилятору хаскеля такую оптимизацию провести ничего не мешает.

если честно, то я не понял сути именно этой оптимизации

Это снижает время выполнения с O(n^2) до O(n)

Я знаю Си. Вкуривать в код дольше, чем в хаскельный.

Наврал. Кажись, неоптимизированный вариант имеет время выполнения не O(n^2), а O(2^n)

Объясните, почему 2^n?

Для одного элемента функция выполняется 1 у.е. времени. Для двух — 1 единицу и еще два вызова самой себя с урезанным списком.

T(1) = 1
T(n) = 1 + 2 * T(n-1)

Компилятору хаскеля такую оптимизацию провести ничего не мешает.

ну хацкель не лисп, и ghci не претендует на то, чтобы быть компилятором, он енмип просто интерпретирует без лишних оптимизаций.

Скомпилированная версия на тройку порядков лучше: (написаны ненулевые значения)

Haskell

 \time -v ./1
25
	Command being timed: "./1"
	User time (seconds): 0.62
	System time (seconds): 0.00
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.62
	Maximum resident set size (kbytes): 8528
	Minor (reclaiming a frame) page faults: 602
	Voluntary context switches: 1
	Involuntary context switches: 3
	Page size (bytes): 4096

C

	Command being timed: "./a.out 25"
	User time (seconds): 0.17
	System time (seconds): 0.00
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.17
	Maximum resident set size (kbytes): 1808
	Minor (reclaiming a frame) page faults: 157
	Voluntary context switches: 1
	Involuntary context switches: 5
	Page size (bytes): 4096

нормальная версия haskell

	Command being timed: "./2"
	Percent of CPU this job got: 0%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
	Maximum resident set size (kbytes): 6400
	Minor (reclaiming a frame) page faults: 470
	Voluntary context switches: 1
	Involuntary context switches: 3
	Page size (bytes): 4096

и ghci не претендует на то, чтобы быть компилятором, он енмип просто интерпретирует без лишних оптимизаций.

Скомпилировал, запустил для 35-ти элементов. Окончания работы программы не дождался. Вывод: не только ghci, но ghc оптимизировать этот код не может.

Ёбанный стыд...

У твоей функции сложность не менее O(n!)

А, всё. Формулка понятная.

И чо?

И то, что странно удивлятся, почему оно так дохрена жрёт и почему так медленно работает

Теперь, господа, другой вопрос. Почему в 7.x всё работает? Встроенная оптимизация?

Я понимаю, мой анонимный друк, ты учил ТА и проч. Но мы люди тёмные, дискретку не ботали, сходу сложность алгоритма оцениваем как O(n^2(

а зачем такой код оптимизировать? и главное как - принудительно включить мемоизацию?

Почему в 7.x всё работает?

4.2.

http://paste.pocoo.org/show/551583/ более адекватная версия на с

	Command being timed: "./a.out"
	User time (seconds): 0.00
	System time (seconds): 0.00
	Percent of CPU this job got: ?%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
	Maximum resident set size (kbytes): 1744
	Minor (reclaiming a frame) page faults: 153
	Voluntary context switches: 1
	Involuntary context switches: 3
	Page size (bytes): 4096
	Exit status: 0

пруф (почти пруф) у nebm51

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

7.0.2 не оптимизирует адекватно, префикс с 7.4 мне сейчас пробовать лень.

а зачем такой код оптимизировать?

Странный вопрос. Компилятор ничего не знает о том, насколько код — говнокод. Ему всё равно, что оптимизировать. Я говорю лишь о том, что компилятор знает. А знает он, что сабжевая функция не имеет побочных эффектов, и код можно переписать так:

max' (x:[]) = x
max' (x:xs) = let n = max' xs in if x > n then x else n

У меня пруф перед глазами в консоли.

Хаскель-комьюнити не лишено некоторого раздражения на всякий быдлокод.

Хвостовую рекурсию в хаскеле не изобрели что ли?

Не, просто ТС тайное искусство хвостовой рекурсии еще не постиг.

Не заметил сразу два рекурсивных вызова :)

можно подумать, что с одним рекурсивным вызовом она там будет

с правильно сделанным — будет.

Да, я что-то совсем плохо распарсил :D

Ему всё равно, что оптимизировать.

Позволю себе не согласиться с данным тезисом. Только я бы не использовал слово на букву «г»: скажем так, есть `the proper way to do things` и оптимизация которая проводится вокруг них. С точки зрения `the proper way` - нам изначально необходимо всего лишь из списка получить единственное атомарное значение, и в ФП делается это просто с помощью свертки: (*):

maximum :: (Ord a) => [a] -> a
maximum []  =  errorEmptyList "maximum"
maximum xs  =  foldl1 max xs

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

__
* (с) Data.List

GHC не делает common subexpression elimination бо может привести к space leaks. (На каком языке я пишу???).

http://www.haskell.org/haskellwiki/GHC:FAQ#Subexpression_Elimination

На каком языке я пишу???

На руглише.

max' (x:xs) = if x > max' xs then x else max' xs

Use the `let', Luke!

т.е. регулярные вызовы одной и той же функции с одними и теми же аргументами - то, можно самому включить мемоизоцию

Дело не этом, дело в том, что оба вхождения (max x) - это один узел графа, а значит, считаться он должен только однажды.

max' [1 .. 21]

SSC догадался бы заменить на 21 в compile time :)

SSC догадался бы заменить на 21 в compile time :)

А max' [1 .. 50] он тоже бы догадался бы заменить в compile time, и добросовестно бы компилировал до второго пришествия?

Sufficiently Smart Compiler это такая шутка.

Ну и да, искать максимум списка [a .. b], b >= a в runtime нет смысла.

Ну и да, искать максимум списка [a .. b], b >= a в runtime нет смысла.

Суть такова^W^WДело в том, что алгоритм, составленный ТСом, имеет экспоненциальную вычислительную сложность. Поэтому считать его в compile time — мягко говоря, не совсем удачная идея.

Вообще это интересный, хотя и «философский», вопрос: где та граница, после которой «оптимизации» превращаются в частичное выполнение программы компилятором, чего программист совсем не хотел. В языках типа Си оптимизации в принципе не могут зайти настолько далеко. А вот высокоуровневых языках, совсем другое дело.

Хвостовая рекурсия — вот решение задачи.

Поэтому считать его в compile time — мягко говоря, не совсем удачная идея.

Я об этом и не говорю, я о том, что для всех тех f для которых структурной индукцией доказывается некое свойство максимальности (минимальности) можно делать замену f [a .. b] => b (=> a). Ну и делать это должен гипотетический SSC, да.

З.Ы. если a и b - переменные, то тоже. Правда, тут нужно ещё equality для a и b выводить, либо взять списки с длиной в типе.

либо взять списки с длиной в типе.

Хотя, это тут ни при чём (позволяет написать тотальные maximum / minimum, но не поможет в случае такой замены - всё равно нужно equality).

А, понял, что ты имеешь ввиду. Да, компилятор, имеющий такие познания, явление чисто гипотетическое.

Охрененно. Чтобы так превращать алгоритм линейной сложности в алгоритм экспоненциальной...

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

Собственно, это первый случай, когда я вижу быдлокод на хаскеле.

А ты думал, если пишешь на хаскеле, то код автоматически становится самым оптимальным и безошибочным?

qnikst

с правильно сделанным — будет

А можно пример того, как в данном случае сделать правильно?

Дотнетовские языки и на жвм

А лучше, чтобы оно у юзера при каждом запуске вычислялось?

Собственно, это первый случай, когда я вижу быдлокод на хаскеле.

А что, собственно, быдлкодного? Программа новичка. Алгоритм экспоненциальный, потому что без циклов непривычно.

если хочется записать явно, то как-то так:

max' [] = error "empty"
max' (x:xs) = inner x xs
  where
    inner c [] = c
    inner c (x:xs) = if c>x then max' c xs else max' x xs