#list #stack #prolog #overflow
#Список #стек #пролог #переполнение
Вопрос:
Привет, ребята, я новичок в Prolog. Я пытаюсь объединить 1000 элементов в классе 3 без повторения. Я выполнил код, но у меня проблема со стеком.
member(T, [T|R], R) :- !.
member(T, [_|L], R) :- member(T, L, R).
last_element([H], H) :- !.
last_element([H|[X]], X) :- !.
last_element([H|T], R) :- last_element(T, R).
macronutrienti(1).
macronutrienti(2).
macronutrienti(3).
and so on
percentuale_macronutrienti(Alimento, R) :-
macronutrienti(Alimento),
R = Alimento.
combina(NRAlimenti, RIS) :-
findall(PM, percentuale_macronutrienti(Alimento, PM), PMR),
f1(NRAlimenti, PMR, PMR, RIS), !.
f1(1, RParz, PMR, RParz) :- !.
f1(Index, RParz, PMR, RIS) :-
Index1 is Index - 1,
g2(RParz, PMR, RIS1, RIS1),
f1(Index1, RIS1, PMR, RIS).
f1(Index, RParz, PMR, RIS) :-
Index1 is Index - 1,
g1(RParz, PMR, RIS1, RIS1),
f1(Index1, RIS1, PMR, RIS).
g1([A|[TA]], A1, OldR, R) :-
q([A], L1, A1),
h1(A, L1, OldR, OldR), !.
g1([A|T], A1, Risultato, R) :-
q([A], L1, A1),
h1(A, L1, OldR, OldR),
append(OldR, TOldR,Risultato),
g1(T, A1, TOldR, R).
q(A, R, A1) :- last_element(A, LastElement), member(LastElement, A1, R).
g2([A|[TA]], A1, OldR, R) :-
q(A, L1, A1),
h2(A, L1, OldR, OldR), !.
g2([A|T], A1, Risultato, R) :-
q(A, L1, A1),
h2(A, L1, OldR, OldR),
append(OldR, TOldR, Risultato),
g2(T, A1, TOldR, R).
h1(_, [], _, _) :- !.
h1(Alimento, [Alimento1], [OldM], R) :- append([Alimento], [Alimento1], OldM).
h1(Alimento, [Alimento1|T1], [OldM|TOldM], NewM) :-
append([Alimento], [Alimento1], OldM),
h1(Alimento, T1, TOldM, NewM).
h2(_, [], _, _) :- !.
h2(Alimento, [Alimento1], [OldM], R) :- append(Alimento, [Alimento1], OldM).
h2(Alimento, [Alimento1|T1], [OldM|TOldM], NewM) :-
append(Alimento, [Alimento1], OldM),
h2(Alimento, T1, TOldM, NewM).
:- combinew(3,R).
Что не так? Заранее благодарю вас
Комментарии:
1. вероятно, пролог застрял в каком-то бесконечном цикле или поиске. используйте трассировку, чтобы изучить способ, которым prolog пытается найти решение.
2. Тот же код работает для 400 макроэлементов (n), но если я вставлю 1000 макроэлементов (n), пролог выйдет из стека. Проблема не в бесконечном цикле, а, я думаю, в количестве вызовов рекурсии.
3. в этом случае вы могли бы попытаться расширить стек: swi-prolog.org/pldoc/doc_for?object=set_prolog_stack/2
4. Я уже расширил стек, но проблема сохраняется. другая идея?
5. если вы не можете расширить его больше, я боюсь, что вам нужно улучшить производительность алгоритма, чтобы он не потреблял так много памяти
Ответ №1:
Вот гораздо более короткий код, который (я думаю) делает то же самое, что и ваш:
combine(N,L) :-
findall(PM, macronutrienti(PM), PMR),
findall(L0, combine0(N, PMR, L0), LL).
combine0(0, _, []) :- !.
combine0(I, PMR, [X|LR]) :-
member(X, PMR, PMRR),
I1 is I-1,
combine0(I1, PMRR, LR).
member(T, [T|R], R).
member(T, [_|L], R) :- member(T, L, R).
(Я немного изменил ваш member/3 предикат)
Однако это все еще не решает вашу проблему с переполнением стека. В принципе, если я правильно понял ваш вопрос, вы хотите извлечь все отсортированные подмножества длиной 3 из набора из 1000 элементов. Количество наборов, которые вы просматриваете, равно 1000! / (1000-3)!, то есть 997.002.000 списков длиной 3. Это довольно много, поэтому, если вам понадобится огромный стек.
Если вам не нужен полный список для продолжения, измените свой рабочий процесс, чтобы генерировать по одному такому элементу за раз, затем обработайте его немедленно и переходите к следующему.