Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
77 views

Ενώ το πρόγραμμά μου τρέχει αρκετά καλά στον υπολογιστή, στον grader το τελευταίο test case μου βγάζει Out of Space. Θεωρητικά το πρόγραμμά μου δημιουργεί δυο λίστες μεγέθους n και τις διατρέχει, οπότε νομίζω ότι δεν θα έπρεπε να έχει πρόβλημα με την μνήμη. Μήπως ξέρετε τι θα μπορούσε να πηγαίνει λαθος;

in pl1 by (160 points)
edited by | 77 views

1 Answer

0 votes

Το πρόβλημα οφειλόταν στο γεγονός ότι χρησιμοποιούσες κάποια κατηγορήματα που ενώ θα μπορούσαν να είναι ντετερμινιστικά (και πραγματικά επέστρεφαν μοναδική απάντηση), άφηναν πολλά branch points ανοιχτά. Για παράδειγμα (παραφράζω λίγο δικό σου κώδικα):

running_sum([X], [X]).
running_sum([X1, X2 | T], Result) :-
  R is X1 + X2,
  running_sum([R | T], Partial),
  append([X1], Partial, Result).

Το παραπάνω υπολογίζει σωστά το running sum σε μία μη κενή λίστα ακεραίων:

?- running_sum([1, 1, 1, 1, 1], Result).
Result = [1, 2, 3, 4, 5] ;
false.

Αν όμως θέλεις να το γράψεις καλύτερα, ώστε να χρειάζεται λιγότερη μνήμη, να είναι tail-recursive και επίσης ντετερμινιστικό:

running_sum(L, Result) :- running_sum(0, L, Result).

running_sum(R, L, Result) :-
  ( L = [] ->
      Result = []
  ; L = [H | T] ->
      NewR is R + H,
      Result = [NewR | Partial],
      running_sum(NewR, T, Partial)
  ).
by (9.4k points)

232 questions

224 answers

258 comments

2.8k users