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

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

in pl1 by (160 points)
edited by | 145 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.5k points)

301 questions

289 answers

288 comments

769 users