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

Вот уж говнокод, так говнокод. Всем говнокодам говнокод.

Как бы твой ник не перепутать с именем моего хоста?

Фееричненько. А reduce в вашей вселенной еше не изобрели?

Задача в данном случае — найти, собственно, причину, по которой святая рекурсия так много хавает. Для оптимизации есть ассемблер.

7.2.2 память не жрет, но думает долго.

Задача в данном случае — найти, собственно, причину, по которой святая рекурсия так много хавает.

Потому что написана плохо.

x > max' xs

Тут ты, фактически, на списке из 25 элементов будешь иметь 25 вложенных max', что-то мне подсказывает, что тут то ты и проседаешь по памяти...

А ответом на то, почему это происходит - иммутабельность данных.

Затрудняюсь посчитать количество проходов по списку — не 21! + 1 ли?

В этом вашем хаскеле, кстати, аргумент-аккумулятор не используют?

user@host $ free
             total       used       free     shared    buffers     cached
Mem:       2043200     580916    1462284          0      32592     270692
-/+ buffers/cache:     277632    1765568
Swap:      1951740      57416    1894324
user@host $ fg
ghci max.hs

*Main> max' [1..23]
23
*Main> 
[1]+  Stopped                 ghci max.hs
user@host $ free
             total       used       free     shared    buffers     cached
Mem:       2043200    1686112     357088          0      32732     270692
-/+ buffers/cache:    1382688     660512
Swap:      1951740      57416    1894324
user@host $ 

как-то так

625 вызовов функции. И чо?

а ещё я тормоз не могу понять, как при

*Main> max' [30..1]

он пытается вычислить max' []

Да, походу косяк в коде.

не, я ступил, [30..1] = []

Тут ты, фактически, на списке из 25 элементов будешь иметь 25 вложенных max

в том то и беда, что на списке из 25 элементов, у него будет 33554431 вложенных max'`ов.

625 вызовов функции. И чо?

А то, что нужно вспомнить про иммутабельность данных в фп. И про то, что у тебя каждый из вызовов max' будет хранить свой кусочек массива.

Не спорю, мне лень считать сколько именно их будет (голова гудит).

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

давай так. умножать и я умею. Два гига ну никак не получится.

 625*25*8
125000

теперь подробнее про 33554431

2^25-1

в чем разница между

max' [25,24..1]

и

max' [1..25]

?

GHCi, version 7.2.1:

*Main> max' [1..21]
21
it :: Integer
(2.70 secs, 142516060 bytes)
*Main>

Но алгоритм ваш, батенька, весьма далек от того, чему учат книги по программированию.

так, в 12 ночи на лоре делать нечего. Мозги не варят совершено. Можно про 2^25? А то с комбинаторикой у меня того, особенно в таком состоянии.

У мну 6-я версия.

А алгоритм сойдёт для первой проги на хаццкеле.

не верь ему, нет там 2^25

foldr1 max - для конечных списков.

и учить о том, что такое thunk и что такое tail recursion и для профилактики перенести свой под на c 1 в 1 и удивиться, почему так толсто и долго.

Добавь отладку и посмотри, как оно считает.

алсо, скомпилировав, возможности можно раздвинуть до [1..30], но всё равно он не может переварить этот код во что-то более приемлемое.

>и учить о том, что такое thunk и что такое tail recursion и для профилактики перенести свой под на c 1 в 1 и удивиться, почему так толсто и долго.

Раз такой умный напиши здесь код на сях 1 в 1.

Работает долго, но памяти съедает не больше 16 мегабайт. Обнови компилятор.

разница между ними в том, что в случае [1..25] у алгоритма будет максимальное время выполнения, в другом случае - минимальное. посмотри внимательнее на сам алгоритм!

Давай так. У меня есть ручка, бумажка и код на хаскеле. Как оценить уровень вложенности рекурсивного вызова?

Но вообще это очень плохой код.

а чего это в старом так?

localhost?

У меня фуражка слетела, поэтому я не могу приложить честь к голове, капитан.

ghc не может заменить два вызова max' xs на один вызов? У него ведь достаточно данных для поведения этой оптимизации.

На то он и старый. Твой код, сначала строит до жопы вычислений, которые только потом форсируются. И ты не поверишь, но им тоже нужна память. В общем ждём местных гуру, но предварительный диагноз — выстрел в ногу ленью. Разрешаю поругать старый ghc.

Если функция порождает новую копию данных на каждом вызове, то требования к памяти памяти — O(n^2) от длины списка. Но даже это не обхясняет, как список из 20 элементов может сожрать 200 метров.

 
#include <stdio.h>

int max(int *list, int size) {
	if (size == 1) return list[0];
	if (list[0] > max(&list[1], size-1))
		return list[0];
	else
		return max(&list[1], size-1);
}

int main () {
	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
		12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
		22, 23, 24, 25, 26, 27, 28, 29, 30 };
	int m = max(a, sizeof(a)/sizeof(int));

	printf("max: %d\n", m);

	return 0;
}

Вот так более понятно будет?

PS: Не хаскеллист

с точностью до ленивости (тоже важно) и полиморфизма (можно сделать через define, но честно лень

[code] #include <stdlib.h> #include <stdio.h>

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

int main(int argc, char *argv[]) { size_t vs = 25; unsigned int v[vs]; size_t i; if (argc <2) { error(«<2»); exit(EXIT_FAILURE); } srand(atoi(argv[1]));

for(i=0;i<vs;i++) { v = rand(); printf(«%u »,v); } printf(«\n»);

int result = max1((unsigned int *)v,vs); printf(«max: %i\n»,result);

exit(EXIT_SUCCESS); } [/code]

...а из 25 залезть в своп и убить всех человеков интерпретатор.

на каждой итерации вычисляем max 2 раза

на хаскеле понятнее. поменял шило на мыло.

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

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

Не имею ни малейшего понятия. Слово массив, в моём посте, не стоит понимать буквально.

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