Δημοσιεύτηκε: 30 Ιουν 2011, 19:27
arkanoid έγραψε:migf1 έγραψε:Επειδή python δεν γνωρίζω, έχω μια απορία: υπάρχει κάποιος ιδιαίτερος λόγος που το sum υπολογίζεται σε ξεχωριστό loop και όχι μαζί με τα min και max στο αρχικό loop? Αυτή η υλοποίηση κάνει τον διπλάσιο χρόνο να εκτελεστεί!
Σίγουρα η υλοποίηση μου δεν είναι η καλύτερη ή η κομψότερη, αλλά διπλάσιο χρόνο εκτέλεσης από το να ήταν όλα σε μία επανάληψη, δεν κάνει. Και οι δύο υλοποιήσεις είναι O(n), αφού και στις δύο περιπτώσεις για κάθε στοιχείο του πίνακα γίνεται το ίδιο πλήθος ενεργειών, γραμμικό ανάλογα με την είσοδο του αλγόριθμου. Μάλλον δε χρειάζεσαι παραπάνω εξηγήσεις όμως, αφού μιλάς για χρόνους εκτέλεσης θα τα γνωρίζεις αυτά. Πάντως γενικότερα συμφωνώ, στο ότι θα ήταν καλύτερα όλα σε μία επανάληψη, αφού θα ήταν πιο απλός και ευανάγνωστος ο κώδικας.
Δεν έχεις δίκιο. Στις compiled γλώσσες ισχύει αυτό που λες. Στην python κάθε for-loop έχει κάποιο overhead. Μικρό μεν, αλλά μετρήσιμο δε. Δοκίμασε να μετρήσεις τον χρόνο εκτέλεσης βάζοντας τη sum μέσα στο πρώτο loop και θα δεις ότι είναι πιο σύντομο. O πιο εύκολος τρόπος είναι με ipython και timeit)
Σχετικά με τη len(), αν και δεν έκανα μετρήσεις πιστεύω ότι θα είναι πιο γρήγορο από το να το κανεις με custom counter, γιατί ο κώδικας πίσω από τη len είναι σε C και εκτελείται πιο γρήγορα από ότι το for loop σε python.