Τεράστιο memory usage στην qssort, python

Question

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

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

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

Comments

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

---

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

Answer 1

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

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

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

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

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