Αυτός ο έξυπνος αλγόριθμος μπορεί να επιταχύνει τα προγράμματά σας και να εμπνεύσει την εργασία σας με πίνακες.
Η εκτέλεση πράξεων σε ακολουθίες αριθμών και χαρακτήρων είναι μια κρίσιμη πτυχή του προγραμματισμού. Ο αλγόριθμος συρόμενου παραθύρου είναι ένας από τους τυπικούς αλγόριθμους για να γίνει αυτό.
Είναι μια κομψή και ευέλικτη λύση που έχει βρει το δρόμο της σε πολλούς τομείς. Από τη χειραγώγηση συμβολοσειρών έως τις διασχίσεις πινάκων και τη βελτιστοποίηση απόδοσης, αυτός ο αλγόριθμος μπορεί να παίξει ρόλο.
Λοιπόν, πώς λειτουργεί ο αλγόριθμος του συρόμενου παραθύρου και πώς μπορείτε να τον εφαρμόσετε στο Go;
Κατανόηση του αλγόριθμου του συρόμενου παραθύρου
Υπάρχουν πολλούς κορυφαίους αλγόριθμους που είναι χρήσιμο να γνωρίζετε ως προγραμματιστής και το συρόμενο παράθυρο είναι ένα από αυτά. Αυτός ο αλγόριθμος περιστρέφεται γύρω από μια απλή ιδέα διατήρησης ενός δυναμικού παραθύρου σε μια ακολουθία δεδομένων, για την αποτελεσματική επεξεργασία και ανάλυση υποσυνόλων αυτών των δεδομένων.
Μπορείτε να εφαρμόσετε τον αλγόριθμο κατά την επίλυση υπολογιστικών προβλημάτων που περιλαμβάνουν πίνακες, συμβολοσειρές ή ακολουθίες δεδομένων.
Η βασική ιδέα πίσω από τον αλγόριθμο του συρόμενου παραθύρου είναι να ορίσετε ένα παράθυρο σταθερού ή μεταβλητού μεγέθους και να το μετακινήσετε στα δεδομένα εισόδου. Αυτό σας επιτρέπει να εξερευνήσετε διαφορετικά υποσύνολα εισόδου χωρίς περιττούς υπολογισμούς που μπορούν να εμποδίσουν την απόδοση.
Ακολουθεί μια οπτική αναπαράσταση του πώς λειτουργεί:
Τα όρια του παραθύρου ενδέχεται να προσαρμόζονται ανάλογα με τις απαιτήσεις του συγκεκριμένου προβλήματος.
Εφαρμογή του αλγόριθμου συρόμενου παραθύρου στο Go
Μπορείτε να χρησιμοποιήσετε ένα δημοφιλές πρόβλημα κωδικοποίησης για να μάθετε πώς λειτουργεί ο αλγόριθμος του συρόμενου παραθύρου: εύρεση του μεγαλύτερου αθροίσματος ενός υποπίνακα με δεδομένο μήκος.
Ο στόχος αυτού του προβλήματος δείγματος είναι να βρεθεί η υποπίνακας μεγέθους κ των οποίων τα στοιχεία αθροίζονται στη μεγαλύτερη αξία. Η συνάρτηση λύσης έχει δύο παραμέτρους: τον πίνακα εισόδου και έναν θετικό ακέραιο που αναπαριστά κ.
Έστω ο πίνακας δειγμάτων αριθμοί, όπως δείχνει ο παρακάτω κώδικας:
nums := []int{1, 5, 4, 8, 7, 1, 9}
Και ας είναι το μήκος του δευτερεύοντος πίνακα κ, με τιμή 3:
k := 3
Στη συνέχεια, μπορείτε να δηλώσετε μια συνάρτηση για να βρείτε το μέγιστο άθροισμα υπο-πίνακες με μήκος k:
funcmaximumSubarraySum(nums []int, k int)int {
// body
}
Ίσως νομίζετε ότι το παράθυρο πρέπει να είναι ένας πίνακας που αποθηκεύει αντίγραφα των στοιχείων-στόχων. Αν και αυτή είναι μια επιλογή, δεν αποδίδει καλά.
Αντίθετα, χρειάζεται απλώς να ορίσετε τα όρια του παραθύρου για να το παρακολουθείτε. Για παράδειγμα, σε αυτήν την περίπτωση, το πρώτο παράθυρο θα έχει έναν δείκτη έναρξης 0 και ένας τελικός δείκτης του κ-1. Κατά τη διαδικασία ολίσθησης του παραθύρου, θα ενημερώσετε αυτά τα όρια.
Το πρώτο βήμα για την επίλυση αυτού του προβλήματος είναι να ληφθεί το άθροισμα του πρώτου υποπίνακα μεγέθους k. Προσθέστε τον ακόλουθο κώδικα στη συνάρτησή σας:
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
Ο παραπάνω κώδικας δηλώνει τις απαραίτητες μεταβλητές για τον αλγόριθμο και βρίσκει το άθροισμα του πρώτου παραθύρου στον πίνακα. Στη συνέχεια αρχικοποιείται maxSum με το άθροισμα του πρώτου παραθύρου.
Το επόμενο βήμα είναι να σύρετε το παράθυρο με επανάληψη μέσω του αριθμοί πίνακας από ευρετήριο κ στο τέλος. Σε κάθε βήμα της ολίσθησης του παραθύρου:
- Εκσυγχρονίζω Παράθυρο Άθροισμα προσθέτοντας το τρέχον στοιχείο και αφαιρώντας το στοιχείο στο Παράθυρο Έναρξη.
- Εκσυγχρονίζω maxSum αν η νέα τιμή του Παράθυρο Άθροισμα είναι μεγαλύτερο από αυτό.
Ο παρακάτω κώδικας υλοποιεί το συρόμενο παράθυρο. Προσθέστε το στο maximumSubarraySum λειτουργία.
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
Όταν ολοκληρωθεί ο βρόχος, θα έχετε το μεγαλύτερο άθροισμα maxSum, το οποίο μπορείτε να επιστρέψετε ως αποτέλεσμα της συνάρτησης:
return maxSum
Η πλήρης λειτουργία σας θα πρέπει να μοιάζει με αυτό:
funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}// slide window forward
windowStart++
}
return maxSum
}
Μπορείτε να ορίσετε μια κύρια συνάρτηση για να ελέγξετε τον αλγόριθμο, χρησιμοποιώντας τις τιμές του αριθμοί και κ από παλαιότερα:
funcmain() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
Η έξοδος σε αυτή την περίπτωση θα είναι 19, που είναι το άθροισμα του υποπίνακα [4, 8, 7], που είναι ο μεγαλύτερος.
Τώρα μπορείτε να εφαρμόσετε την ίδια τεχνική σε παρόμοια προβλήματα, ακόμη και σε άλλες γλώσσες, όπως ο χειρισμός επαναλαμβανόμενων στοιχείων μέσα σε ένα παράθυρο χρησιμοποιώντας ένα Χάρτης κατακερματισμού Java, για παράδειγμα.
Οι βέλτιστοι αλγόριθμοι έχουν ως αποτέλεσμα αποτελεσματικές εφαρμογές
Αυτός ο αλγόριθμος αποτελεί απόδειξη της δύναμης των αποτελεσματικών λύσεων όταν πρόκειται για επίλυση προβλημάτων. Το συρόμενο παράθυρο μεγιστοποιεί την απόδοση και εξαλείφει τους περιττούς υπολογισμούς.
Η πλήρης κατανόηση του αλγόριθμου του συρόμενου παραθύρου και της εφαρμογής του στο Go σάς εξοπλίζει για να αντιμετωπίσετε σενάρια πραγματικού κόσμου κατά τη δημιουργία εφαρμογών.
