ΣΥΓΚΡΙΣΗ ΑΠΟΔΟΣΗΣ ΑΛΓΟΡΙΘΜΩΝ MAXIMUM SUB ARRAY SUM ΣΤΗΝ
PYTHON
ΑΝΔΡΕΑΣ ΚΟΣΚΙΝΑΣ
1080211
17/3/2023
Περιγραφή του προβλήματος:
Το πρόβλημα του Maximum Sub Array Sum, είναι ένα εξαιρετικά γνωστό πρόβλημα στον
τομέα της ανάπτυξης λογισμικού, η βάση του είναι η εύρεση ενός συνεχόμενου υποπίνακα
εντός ενός μεγαλύτερου του οποίου το άθροισμα των στοιχείων του είναι το μέγιστο
δυνατό.
Για την επίλυση του συγκριμένου προβλήματος έχουν αναπτυχθεί πολλές υλοποιήσεις με
διαφορετική αλγοριθμική πολυπλοκότητα, μερικές από αυτές είναι:
• Αλγόριθμος δοκιμής συνδυασμών, πολυπλοκότητας O(n^3)
• Αλγόριθμος δοκιμής συνδυασμών, πολυπλοκότητας O(n^2)
• Αλγόριθμος Divide and Conquer, πολυπλοκότητας O(nlog(n))
• Αλγόριθμος Kadane, πολυπλοκότητας Ο(n)
Προσέγγιση της ανάλυσης:
Σκοπός της παρούσας εργασίας είναι η ανάλυση και των 4ων αλγορίθμων τόσο στον χρόνο
επίλυσης προβλημάτων πεπερασμένου μεγέθους ,όσο και η εύρεση του μεγίστου δυνατού
μεγέθους που μπορούν να επιλύσουν εντός πεπερασμένου χρονικού διαστήματος 1sec.
Για την ανάλυση υλοποιήθηκαν και οι 4 αλγόριθμοι με χρήση Python, ενώ
συμπεριλήφθηκαν και οι κατάλληλες συναρτήσεις ελέγχου και χρονομέτρησης.
Κώδικας:
Αλγόριθμος O(n^3):
Ο συγκεκριμένος αλγόριθμος είναι εξαιρετικά απλός. Ο τρόπος λειτουργίας του είναι ο
εξής:
1. Ο πρώτος δείκτης i δείχνει την αρχή της αναζήτησης, μετέπειτα η άθροιση ξεκινάει
να γίνεται από αυτό το στοιχείο μέχρι το τέλος του πίνακα, για αυτή την διάσχιση
υπεύθυνος είναι ο δείκτης j.
2. Αν το αποτέλεσμα της άθροισης είναι μεγαλύτερο από το προηγούμενο τότε η τιμή
του ανατίθεται στην msum.
3. Τα δεδομένα θέσης και το άθροισμα επιστρέφονται στην συνάρτηση ελέγχου.
Αποτελέσματα επιδόσεων αλγορίθμου O(n^3):
Πλήθος δεδομένων Χρόνος εκτέλεσης
10 0.48ms
100 2.4ms
1000 2sec
2000 15.75sec
Αλγόριθμος O(n^2):
Ο συγκεκριμένος αλγόριθμος είναι εξίσου απλός. Ο τρόπος λειτουργίας του είναι ο εξής:
1. Ο δείκτης i δείχνει την αρχή της άθροισης.
2. Ο δείκτης j διατρέχει όλα τα στοιχεία τα οποία πρόκειται να αθροιστούν.
3. Στην επόμενη επανάληψη η μεταβλητή tmp μηδενίζεται και η διαδικασία
επαναλαμβάνεται.
4. Αν σε οποιαδήποτε επανάληψη το αποτέλεσμα είναι μεγαλύτερο από το
προηγούμενο ανατίθεται στην μεταβλητή msum, ενώ στις start, end είναι οι δείκτες
της αρχής και του τέλους του maximum sub array
Αποτελέσματα επιδόσεων αλγορίθμου O(n^2):
Πλήθος δεδομένων Χρόνος εκτέλεσης
10 12μs
100 0.346ms
1000 37ms
2000 150ms
Αλγόριθμος O(nlog(n)) Divide and Conquer:
Ο αλγόριθμος πολυπλοκότητας O(nlog(n))είναι αναδρομικός ο τρόπος λειτουργίας του
είναι ο εξής:
1. Όταν καλείτε εκτός από το array το οποίο πρέπει να λειτουργήσει χρειάζεται το
αρχικό και το τελικό index του διανύσματος.
2. Μετέπειτα γίνεται έλεγχος αν τα 2 indexes είναι διαφορετικά.
3. Έπειτα υπολογίζεται το μέσο του διαστήματος.
4. Και στη συνέχεια σπάμε το διάστημα σε μικρότερα υποπροβλήματα.
5. Ο αλγόριθμος crsss_sum είναι υπεύθυνος για την εύρεση του μέγιστου υποπίνακα
εντός των κατακτημένων διαστημάτων.
6. Ο αλγόριθμος crsss_sum έχει πολυπλοκότητα O(n).
Αποτελέσματα O(nlog(n)) Divide and Conquer:
Πλήθος δεδομένων Χρόνος εκτέλεσης
10 25.9μs
100 0.2015ms
1000 2.31ms
2000 4.79ms
Αλγόριθμος O(n) Kadane:
Ο τρόπος λειτουργίας του είναι ο εξής:
1. Ο αλγόριθμος διατρέχει την λίστα μόνο μια φορά, προσθέτοντας κάθε στοιχείο
που βρίσκει, όσο το άθροισμα μεγαλώνει αναθέτει την νέα τιμή για σύγκριση
με την προηγούμενη και το τρέχων index στο “end”.
2. Αν το “tmp” γίνει αρνητικό παραλείπει το τρέχων βήμα και συνεχίζει στο
επόμενο εν σειρά index.
Αποτελέσματα O(n) Kadane’s:
Πλήθος δεδομένων Χρόνος εκτέλεσης
10 6μs
100 13.4μs
1000 97.7μs
2000 192.5μs
Εύρεση μέγιστου πλήθους αριθμών επεξεργάσιμων εντός
πεπερασμένου χρόνου:
Για την εύρεση του μέγιστου πλήθους αριθμών επεξεργάσιμων εντός πεπερασμένου
χρόνου χρησιμοποιήθηκε επαναληπτική μέθοδος στην οποία λαμβανόταν ένα αρχικό
μέγεθος λίστας, δοκιμαζόταν ο αλγόριθμος και σε περίπτωση που ο χρόνος εκτέλεσης του
ήταν μικρότερος του ζητούμενου αυξανόταν το μέγεθος της λίστας, με αυτό τον τρόπο η
ακρίβεια του υπολογισμού της μέγιστης δυνατής χωρητικότητας του κάθε αλγορίθμου
εντός πεπερασμένου χρόνου ενός δευτερολέπτου βρίσκεται με ακρίβεια τουλάχιστον ενός
δεκαδικού ψηφίου. Σημαντικό κριτήριο της ταχύτητας εκτέλεσης του συγκεκριμένου
τμήματος, είναι η βελτιστοποίηση των μεγεθών τόσο της αρχικής λίστας όσο και του
βήματος αύξησης, οι παράμετροι βελτιστοποιήθηκαν για τον συγκεκριμένο υπολογιστή που
γράφτηκε ο κώδικας.
Ενδεικτικό τμήμα κώδικα
Η μέγιστη χωρητικότητα του συστήματος σε FLOPS είναι:
823,7 GFLOPS @ 6 cores.
823,7 GFLOPS / 6 cores ~ = ~ 137 GFLOPS @core.
Για τον αλγόριθμο O(n) Kadane:
Αφού η διάσχιση κάθε λίστας στον αλγόριθμο του Kadane έχει πολυπλοκότητα O(n)
Έχουμε 137GFLOP = n => n = 137*10^9 θεωρητικούς αριθμούς.
Στην πράξη έχουμε 10.500.000.
O(n)
0,25
0,2
0,15
0,1
0,05
0
0 500 1000 1500 2000 2500
Για τον αλγόριθμο O(nlog(n)) Divide and Conquer:
137 GFLOP = nlog2(n) => n = 4,82 * 10^9 θεωρητικούς αριθμούς.
Στην πράξη έχουμε 340.000.
O(nlog(n))
6
0
0 500 1000 1500 2000 2500
Για τον αλγόριθμο O(n^2):
137 GFLOP = n^2 => n = 370.135 θεωρητικούς αριθμούς.
Στην πράξη έχουμε 5.200.
O(n^2)
160
140
120
100
80
60
40
20
0
0 500 1000 1500 2000 2500
Για τον αλγόριθμο O(n^3):
137 GFLOP = n^3 => n = 5.155 θεωρητικούς αριθμούς.
Στην πράξη έχουμε 800.
O(n^3)
180000
160000
140000
120000
100000
80000
60000
40000
20000
0
0 500 1000 1500 2000 2500
-20000
Τελικά οι μέγιστες χωρητικότητες διαμορφώνονται ως εξής:
Αλγόριθμος Θεωρητικά Πειραματικά
O(n^3) 5.155 800
O(n^2) 370.135 5.200
O(nlog(n)) 4,82 * 10^9 340.000
O(n) 137*10^9 10.500.000
ΚΟΣΚΙΝΑΣ ΑΝΔΡΕΑΣ
1080211
