LINUX.ORG.RU

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

 ,


0

2

Код:

max' (x:[]) = x
max' (x:xs) = if x > max' xs then x else max' xs
Вызов кода
user@host $ ghci max.hs 
*Main> max' [1..21]
21
При этом откушивается под 200 мегабайт памяти. При 25-элементном списке мои два гига заканчиваются.

Собственно, с чего бы это так толсто?

★★★★★

user@host $ ghci --version
The Glorious Glasgow Haskell Compilation System, version 6.12.3
luke ★★★★★
() автор топика
Ответ на: комментарий от geekless

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

luke ★★★★★
() автор топика
Ответ на: комментарий от luke

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

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

x > max' xs

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

Norgat ★★★★★
()
Ответ на: комментарий от note173

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

note173 ★★★★★
()
Ответ на: комментарий от vvff
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 $ 

как-то так

luke ★★★★★
() автор топика
Ответ на: комментарий от Norgat

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

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

beka
()
Ответ на: комментарий от luke

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

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

Norgat ★★★★★
()
Ответ на: комментарий от beka

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

 625*25*8
125000
8 взято от балды, 4 на int, 4 на указатель. Порядок тот же в любом случае, это мегабайт.

luke ★★★★★
() автор топика

GHCi, version 7.2.1:

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


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

delete83 ★★
()
Ответ на: комментарий от AptGet

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

luke ★★★★★
() автор топика

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

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

qnikst ★★★★★
()
Ответ на: комментарий от luke

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

vvff
()
Ответ на: комментарий от qnikst

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

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

luke ★★★★★
() автор топика

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

KblCb ★★★★★
()
Ответ на: комментарий от vvff

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

beka
()
Ответ на: комментарий от AptGet

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

luke ★★★★★
() автор топика
Ответ на: комментарий от KblCb

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

luke ★★★★★
() автор топика
Ответ на: комментарий от qnikst

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

geekless ★★
()
Ответ на: комментарий от luke

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

KblCb ★★★★★
()
Ответ на: комментарий от KblCb

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

geekless ★★
()
Ответ на: комментарий от luke
 
#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: Не хаскеллист

AptGet ★★★
()
Ответ на: комментарий от luke

с точностью до ленивости (тоже важно) и полиморфизма (можно сделать через 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]

qnikst ★★★★★
()
Ответ на: комментарий от geekless

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

luke ★★★★★
() автор топика
Ответ на: комментарий от note173

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

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

Norgat ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.