Άσκηση 1 | ΜΕΘ υπό διαρκή πίεση | Ερώτηση περί χρόνου εκτέλεσης της ML

Question

Θέλω να ρωτήσω κάτι σχετικά με την πρώτη άσκηση. Το testcase longest.in14 στην ML δεν γίνεται δεκτό λόγω υπέρβασης χρονικού ορίου στον grader. Στον υπολογιστή μου ενδεικτικά όταν τρέχω την λύση μας στην ML με είσοδο το testcase longest.in14 χρειάζεται 6.7 sec. Η λύση μας, αν δεν κάνουμε λάθος, είναι γραμμικής πολυπλοκότητας και δεν χρησιμοποιούμε πουθενά τον τελεστή @ μεταξύ λιστών, μονάχα τον ::. Επίσης δεν χρησιμοποιήσαμε Array αλλά λίστες.

Πρόσφατα είχατε πει σε διάλεξη ότι τα χρονικά όρια για την ML θα αλλάξουν, μετά από ερώτηση κάποιου συμφοιτητή μου. Η ερώτηση μου είναι αν ο χρόνος εκτέλεσης των 6.7 sec είναι αποδεκτός για αυτό το testcase. Επίσης για την βελτίωση του χρόνου να δοκιμάσουμε να χρησιμοποιήσουμε arrays αντί για λίστες;

Ερώτημα προς τους συμφοιτητές μου:

Έχει καταφέρει κανείς να περάσει το longest.in14 στον grader;

Comments

Ναι, έχω καταφέρει να περάσω το testcase (Longest 14) με ~0.3 sec χρόνο εκτέλεσης.

---

Χρησιμοποίησες array ή λίστες; Επίσης δεν ξέρω αν έχει σημασία αλλά εγώ έγραψα το πρόγραμμα σε SML/NJ.

---

Χρησιμοποίησα και Array και λίστα. Κι εγώ σε SML/NJ έγραψα το πρόγραμμα.

---

Οκ ευχαριστώ. Θα δοκιμάσω μάλλον μερικά πράγματα με array και θα δω...

---

Το έλυσα τελικά χρησιμοποιώντας Array (και σε μερικά σημεία λίστες) και στο grader το longest.in14 πήρε 0.11 sec.

Έχω ένα ερώτημα προς τους καθηγητές του μαθήματος:

Στην τελική υποβολή να παραδώσω την πιο γρήγορη λύση που χρησιμοποιεί array και δεν έχει τόσο συναρτησιακό χαρακτήρα ή να να παραδώσω την πιο αργή λύση που χρησιμοποιεί λίστες και έχει πιο έντονο συναρτησιακό χαρακτήρα;

---

Δες το edit στην απάντησή μου για την εφικτότητα της λύσης χωρίς arrays. Παράδωσε όποια λύση σου θέλεις, η χρήση array ή όχι δεν επηρεάζει το βαθμό σου.

Answer 1

Ανεξαρτήτως αν κάποιος το έχει περάσει ή όχι, τα χρονικά όρια των ασκήσεων στο μάθημα των #pl1 διαμορφώνονται ανά πρόβλημα και ανά γλώσσα. Συνήθως, το χρονικό όριο είναι $c \cdot T$, όπου T ο χρόνος που κάνει η λύση των διδασκόντων στο μεγαλύτερο test case και $c \ge 1$ κάποια κατάλληλη σταθερά. Η τιμή του $c$ συνήθως είναι κάτι μεταξύ 5 και 10. Επομένως, όπως είπαμε και στο μάθημα, μην αγχώνεστε πολύ αν χάνετε το τελευταίο test case.

Edit: Η λύση των διδασκόντων (SMLNJ), με απλή λίστα και όχι array, τρέχει το test case 14 σε ~ 0.1418 secs.