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

Ενώ το πρόγραμμα μου βγάζει σωστά και γρήγορα αποτελέσματα στα πρώτα test cases, στα δύο τελευταία υπάρχει πρόβλημα με το memory usage. Πιο συγκεκριμένα, στο τελευταίο, όταν το τρέχω στον υπολογιστή μου, ακόμα και μετά από χρήση 28gb ram (και αρκετή ώρα) δεν βγάζει αποτέλεσμα. Το προτελευταίο case, που επίσης έχει πρόβλημα στον grader, βγάζει (σωστό) αποτέλεσμα στα 9gb στον υπολογιστή μου.

Από όσο έχω δει υπάρχουν και άλλοι φοιτητές με το ίδιο πρόβλημα.

Δεν ξέρω αν μπορώ να συζητήσω τον αλγόριθμο μου, αλλά έχετε κάποιο hint για το τι μπορούμε να κάνουμε;

in pl1 by (330 points) | 335 views
0

Έχω το ίδιο πρόβλημα μόνο στο τελευταίο case. Χρησιμοποιώ generators αλλά και πάλι στο τελευταίο τα σκάει η μνήμη. Αν το έχεις λύσει το πρόβλημα, τι έχεις αλλάξει στο κομμάτι της υλοποίησης;

+2

Καλησπέρα. Η λύση ήταν αλλαγή στον αλγόριθμό μου, ώστε να μην "επισκέφτομαι" ξανά καταστάσεις που έχω ήδη επισκεφτεί στο παρελθόν.

1 Answer

0 votes

Ένα πρόγραμμα καταναλώνει πολλή μνήμη συνήθως για δύο πιθανούς λόγους:

  1. Πραγματικά χρειάζεται πολλή μνήμη, βάσει του αλγορίθμου που έχει
    επιλεγεί.
  2. Δε χρειάζεται πραγματικά πολλή μνήμη, αλλά κάποια
    προγραμματιστική επιλογή που έχει γίνει καταλήγει να καταναλώνει
    πολλή μνήμη.

Στην περίπτωση αυτής της ερώτησης, το πρόβλημα ήταν το (1), όπως εξηγεί το σχόλιο του ερωτώντα:

Η λύση ήταν αλλαγή στον αλγόριθμό μου, ώστε να μην "επισκέφτομαι" ξανά καταστάσεις που έχω ήδη επισκεφτεί στο παρελθόν.

Προφανώς αν εξετάζεις ξανά και ξανά τις ίδιες καταστάσεις, το "μέτωπο" του BFS σου μεγαλώνει ανεξέλεγκτα γιατί σε μια κατάσταση μπορείς να φτάσεις με πάρα πολλούς διαφορετικούς τρόπους.

by (9.5k points)

301 questions

289 answers

288 comments

769 users