καλύτερη υλοποίηση ουράς

Ξεκίνησε από Αναστάσης Κολιόπουλος, 23 Ιουν 2022, 05:39:15 ΜΜ

« προηγούμενο - επόμενο »

Αναστάσης Κολιόπουλος

Φέτος τελείωσα την τρίτη λυκείου και έχοντας μπει πολλές φορές στο στέκι θέλω να προτείνω κάτι που αφορά την υλοποίηση της ουράς (γνωρίζω ότι έχει σχολιαστεί σε προηγούμενα θέματα). Το υπουργείο πιστεύω ότι έχει δώσει έναν κώδικα χωρίς κάποια ιδιαίτερη λογική, καθώς η ουρά μέχρι να αδειάσει είναι μίας χρήσης κλπ κλπ. Αντίθετα με την στοίβα η οποία ακολουθεί, κατά την γνώμη μου, σωστή λογική καθώς προσαρμόζεται ο δείκτης top ανάλογα με τα στοιχεία της στοίβας, αγνοώντας τα υπόλοιπα που υπάρχουν στον πίνακα με τον οποίο η ίδια υλοποιείται. Έτσι ακολουθώντας την ίδια λογική και σκεφτόμενος ότι αυτή η προσέγγιση αντικατοπτρίζει περισσότερο την πραγματικότητα παραθέτω τους εξής κώδικες:

ΕΙΣΑΓΩΓΗ:

Αν rear = n τότε
  Γράψε "Γεμάτη ουρά"
αλλιώς
  rear <- rear + 1
  Διάβασε ουρά[rear]
τέλος_αν

ΕΞΑΓΩΓΗ:

Αν rear = 0 τότε
  Γράψε "Άδεια ουρά"
αλλιώς
  Γράψε "Εξάγεται το ",ουρά[1]
  Για i από 1 μέχρι rear - 1 ! Ολίσθηση στοιχείων της ουράς στις πρώτες θέσεις, όπως σε μία πραγματική κατάσταση ουράς
    ουρά <- ουρά[i+1]
  τέλος_επανάληψης
  rear <- rear - 1
τέλος_αν

Παρατηρήσεις:
i. Ο δείκτης rear αρχικοποιείται με τιμή μηδέν ( rear <- 0 ).
ii. Ο δείκτης front είναι περιττός.
iii. Γνωρίζω ότι η ολίσθηση υπάρχει στην άσκηση με το ταχυδρομείο αλλά ο κώδικας εκεί είναι αχρείαστα πολύπλοκος, γιαυτό και προτείνω έναν πιο απλό κώδικα.

akalest0s

Τον δείκτη της αριστερά "ουρά", εντός της Για, τον έχει πάρει για bbcode italics, οπότε δεν τον εμφάνισε.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

gpapargi

Παράθεση από: Αναστάσης Κολιόπουλος στις 23 Ιουν 2022, 05:39:15 ΜΜ Φέτος τελείωσα την τρίτη λυκείου και έχοντας μπει πολλές φορές στο στέκι θέλω να προτείνω κάτι που αφορά την υλοποίηση της ουράς (γνωρίζω ότι έχει σχολιαστεί σε προηγούμενα θέματα). Το υπουργείο πιστεύω ότι έχει δώσει έναν κώδικα χωρίς κάποια ιδιαίτερη λογική, καθώς η ουρά μέχρι να αδειάσει είναι μίας χρήσης κλπ κλπ. Αντίθετα με την στοίβα η οποία ακολουθεί, κατά την γνώμη μου, σωστή λογική καθώς προσαρμόζεται ο δείκτης top ανάλογα με τα στοιχεία της στοίβας, αγνοώντας τα υπόλοιπα που υπάρχουν στον πίνακα με τον οποίο η ίδια υλοποιείται. Έτσι ακολουθώντας την ίδια λογική και σκεφτόμενος ότι αυτή η προσέγγιση αντικατοπτρίζει περισσότερο την πραγματικότητα παραθέτω τους εξής κώδικες:

ΕΙΣΑΓΩΓΗ:

Αν rear = n τότε
  Γράψε "Γεμάτη ουρά"
αλλιώς
  rear <- rear + 1
  Διάβασε ουρά[rear]
τέλος_αν

ΕΞΑΓΩΓΗ:

Αν rear = 0 τότε
  Γράψε "Άδεια ουρά"
αλλιώς
  Γράψε "Εξάγεται το ",ουρά[1]
  Για i από 1 μέχρι rear - 1 ! Ολίσθηση στοιχείων της ουράς στις πρώτες θέσεις, όπως σε μία πραγματική κατάσταση ουράς
    ουρά <- ουρά[i+1]
  τέλος_επανάληψης
  rear <- rear - 1
τέλος_αν

Παρατηρήσεις:
i. Ο δείκτης rear αρχικοποιείται με τιμή μηδέν ( rear <- 0 ).
ii. Ο δείκτης front είναι περιττός.
iii. Γνωρίζω ότι η ολίσθηση υπάρχει στην άσκηση με το ταχυδρομείο αλλά ο κώδικας εκεί είναι αχρείαστα πολύπλοκος, γιαυτό και προτείνω έναν πιο απλό κώδικα.

Η σκέψη σου είναι απόλυτα λογική. Το ζήτημα είναι ότι έτσι αυξάνεται η πολυπλοκότητα σε μια εξαγωγή γιατί έχεις να κάνεις ολισθήσεις. Η λύση που χρησιμοποιείται σε μια στατική υλοποίηση (με πίνακα δηλαδή) είναι αυτή της κυκλικής ουράς. Δηλαδή μόλις φτάσει στο τέλος του πίνακα το επόμενο στοιχείο μπαίνει από μπροστά. Ουσιαστικά θα πρέπει να οριστεί η κίνηση των δεικτών και να βρεις για κάθε θέση ποια είναι η επόμενη.

Επίσης στην πραγματική ζωή (πχ στο ταμείο) κάνουν όταν βγαίνει ένας από την ουρά, κάνουν ΟΛΟΙ από ένα βήμα μπρος (είναι ας πούμε κάτι σαν παράλληλη επεξεργασία) ενώ εδώ τα κάνει όλα ο ίδιος.

alkisg

Ένα παράδειγμα ουράς από την πραγματικότητα που δυστυχώς χρειάστηκε να παρατηρήσω πρόσφατα είναι με τους τάφους.
Ένα νεκροταφείο έχει 100 θέσεις και ο παππάς ορίζει να μπαίνουν με τη σειρά οι νέοι νεκροί (βοηθάει στην ξεκούραση του χώματος).
Όταν φτάσουν στην 100 θέση δεν λένε "δεν χωράμε άλλους".
Ούτε βγάζουν όλους τους νεκρούς και κάνουν ολίσθηση.
Συνεχίζουν από τη θέση 1...

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

Αν όμως διδάσκουμε την θεωρία ουρών με πολυπλοκότητα Ο(Ν) αντί για Ο(1), να μην μας κακοφαίνεται μετά αν αργούν τα Windows και το Internet, εμείς οι ίδιοι φταίμε που τα διδάσκουμε λάθος...  ::)

Foto

Η χρήση ουράς έχει να κάνει με τη καθυστέρηση. https://youtu.be/bsk4WWtRx6M
Στα ηλεκτρονικά υπάρχει το ισοδύναμο του FIFO για ηλεκτρικά σήματα, τη γνωστή Delay Line. Το σήμα πρέπει να χρησιμοποιηθεί ως έχει με καθυστέρηση. Οπότε ένα κύκλωμα εκπέμπει το σήμα σαν ήχο και το λαμβάνει με καθυστέρηση συγκεκριμένη. Βλέπουμε στο παράδειγμα στο youtube ότι δεν υπάρχει καν μνήμη αλλά εκμετάλλευση της καθυστέρησης λόγω αλλαγής του ηλεκτρικού σήματος σε ηχητικό
Στους υπολογιστές μια διάταξη που έχει το ρόλο της καθυστέρησης μέσω μιας ουράς συμβαίνει στο πρόγραμμα που διαβάζει το πληκτρολόγιο. Η ανάγνωση του πληκτρολογίου γίνεται συνέχεια με προώθηση των τιμών των πλήκτρων σε μια ουρά (αυτή έχει μια μέγιστη τιμή πλήκτρων και αν πάει να ξεπεραστεί ακούμε ήχο που μας λέει ότι γέμισε). Ο λόγος που έχουμε αυτή τη καθυστέρηση είναι απλός. Το πρόγραμμα που θα χειριστεί, δηλαδή θα δώσει νόημα, στις τιμές των πλήκτρων που δώσαμε δουλεύει με το δικό του ρυθμό ανάγνωσης. Το ίδιο συμβαίνει με τις ουρές στη τράπεζα,, η καθυστέρηση βρίσκεται στο γκισέ, επειδή η κάθε εξυπηρέτηση έχει διαφορετικό χρόνο περάτωσης.
Τώρα σχετικά με τα νεκροταφεία, όταν γίνονται δύο ή περισσότερες κηδείες, υπάρχει ένας χώρος που μπαίνουν οι σωροί των νεκρών, με δωμάτια, και λόγω ότι κάθε κηδεία είναι προγραμματισμένη να γίνει στην ώρα της, η στάθμευση στο χώρο αυτό δεν γίνεται με FIFO, αλλά με αριθμό προτεραιότητας   Έτσι αν πούμε ότι έχουμε τρεις κηδείες με αριθμούς 1, 2 και 3, τότε η προσέλευση μπορεί να γίνει με οποιαδήποτε σειρά, σε όποιο κενό δωμάτιο αναμονής, και η εξαγωγή θα γίνει βάσει των συμφωνημένων αριθμών. Εδώ υπάρχει καθυστέρηση μεταξύ εισαγωγής και εξαγωγής αλλά και μια επιπρόσθετη λειτουργία αυτή της προτεραιότητας όχι λόγω εισαγωγής αλλά λόγω της τιμής (εδώ το όνομα του νεκρού, που του δώσαμε νούμερο). Εν τέλει και στις τράπεζες η ουρά παίζει με αριθμούς προτεραιότητας και οι θέσεις αναμονής είναι διάσπαρτες και όχι σε μια τυπική ουρά.

akalest0s

Παράθεση από: alkisg στις 24 Ιουν 2022, 09:20:03 ΠΜΑν όμως διδάσκουμε την θεωρία ουρών με πολυπλοκότητα Ο(Ν) αντί για Ο(1), να μην μας κακοφαίνεται μετά αν αργούν τα Windows και το Internet, εμείς οι ίδιοι φταίμε που τα διδάσκουμε λάθος...  ::)
;D ;D ;D golden post έχω πέσει από το γέλιο
Αν μπει κάποια στιγμή Python, θα διδάσκουμε πάλι ουρά με ολίσθηση, αλλά σε σύνταξη python, έτσι;
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

Αναστάσης Κολιόπουλος

Επισυνάπτω κώδικα κυκλικής ουράς, περιμένω τα σχόλια σας.

Εισαγωγή:

Αν (r = n και f = 1) ή (f - r = 1) τότε

  Γράψε 'Γεμάτη ουρά'

αλλιώς

  r ← r + 1

  Αν (r > n και f > 1) τότε ! Ο δείκτης r ξαναξεκινάει από την 1η θέση της ουράς

    r ← 1

  αλλιώς_αν (f = 0) τότε ! Εισαγωγή στοιχείου σε άδεια ουρά

    f ← 1

  Τέλος_αν

  Διάβασε q[r] ! Εισάγεται το...

Τέλος_αν

Εξαγωγή:

Αν (f = 0) και (r = 0) τότε

  Γράψε 'Άδεια ουρά'

αλλιώς

  Γράψε q[f]                                                    ! Εξάγεται το...

  f ← f + 1

  Αν (r = f - 1) τότε                                           ! Άδειασμα ουράς

    f ← 0

    r ← 0

  αλλιώς_αν (f > n) τότε      ! Ο δείκτης f ξαναξεκινάει από την 1η θέση της ουράς

    f ← 1

  Τέλος_αν

Τέλος_αν

Foto

#7
Κυκλική Ουρά (έστω 10 θέσεων σε πίνακα):
Έστω r (rear) και f (front)
Έστω r δείχνει από που θα εξάγουμε
Έστω f δείχνει την τελευταία  εισαγωγή ή (0 αν είναι κενή η ουρά)
Έστω οι θέσεις στην ουρά είναι από το 1 έως το 10, σε έναν πίνακα (η ΓΛΩΣΣΑ στους πίνακες ξεκινάει από το 1).
αρχικoπoίηση r : δίνουμε όποια τιμή θέλουμε, μας είναι αδιάφορο, μπορούμε να δώσουμε το 0
αρχικoπoίηση f : f = 0 (με μηδέν σημαίνει ότι η λίστα είναι άδεια)
α) Περίπτωση πρώτης εισαγωγής (f=0)
νέες τιμές r=1 και f=1
βάζουμε στη θέση 1 την τιμή που εισάγουμε
β) Περίπτωση εισαγωγής μιας μη πρώτης τιμής (f<>0)
β.1) Έλεγχος ουράς αν είναι γεμάτη
Όταν μια ουρά είναι γεμάτη τότε όλες οι θέσεις είναι πιασμένες. Έστω r=1 και f=10
H επόμενη θέση του f λόγω το mod τελεστή θα γίνει (f mod 10)+1 = 1 που πέφτει πάνω στο r (το +1 το βάζουμε έξω από τις παρενθέσεις για μετάθεση της αρχής στο 1, επειδή ο πίνακας ξεκινάει από 1 ενώ o τελεστής mod δίνει από 0 έως 9, για οποιαδήποτε ακέραια τιμή f). Επίσης μας βολεύει ο τύπος γιατί μας δίνει το κάθε επόμενο έτσι στο f=3 το (f mod 10)+1 θα δώσει το 4. Λάθος θα ήταν αν κάναμε αυτό (f + 1) mod 10, γιατί για το 3 δίνει το 4 αλλά στο 9 δίνει 0 που είναι εκτός θέσης στο πίνακα.
Έτσι αν (f mod 10)+1 = r έχουμε γεμάτη ουρά (f<>0).
β.2) Αν το fneo ως (f mod 10)+1 δεν είναι ίσο με το r (και δεν έχουμε f=0) τότε το f θα πάρει το fneo, και εκεί θα μπει η τιμή στην ουρά.
γ) Περίπτωση εξαγωγής της τελευταίας τιμής πριν η ουρά αδειάσει (f=r, f<>0). Όπως είδαμε στο α, η πρώτη τιμή μπαίνει με f=1 και r=1. Εδώ πράγματι έχουμε f=r και f<>0, άρα διαβάζουμε από f και κάνουμε f=0 και r=0.
δ) Περίπτωση εξαγωγής μιας μη τελευταίας τιμής (f<>r, f<>0).
Εφόσο δεν έχουμε περίπτωση γ, και δεν έχουμε άδεια ουρά (f=0) τότε:
Διαβάζουμε από τη θέση r και πάμε στο νέο r που θα είναι το (r mod 10)+1

Πώς εισάγουμε: Κοιτάμε αν είναι άδεια η ουρά οπότε έχουμε τη περίπτωση α, αν όχι τότε κοιτάμε αν δεν έχουμε γεμάτη ουρά (έλεγχος β.1) και αν όντως δεν είναι γεμάτη έχουμε τη περίπτωση β.2 (αλλιώς κάτι κάνουμε, πχ βγάζουμε ένα μήνυμα λάθους ή ότι μας πουν)
****Στην εισαγωγή η τιμή του f θα είναι διάφορη του μηδενός.
****Στην εισαγωγή η τιμή του r γίνεται 1 όταν η τιμή που εισάγουμε είναι η πρώτη στην ουρά.

Πώς εξάγουμε: Κοιτάμε την περίπτωση γ, αν δεν συμβαίνει να έχουμε τη τελευταία τιμή στην ουρά, πάμε στη περίπτωση δ, αν έχουμε άδεια ουρά βγάζουμε μήνυμα λάθους.
****Στην εξαγωγή η τιμή του r αλλάζει κυκλικά πάντα (ακόμα και να αδειάσει η κυκλική ουρά η τιμή της r μας είναι αδιάφορη, επειδή με την πρώτη εισαγωγή θα γίνει 1).
****Στην εξαγωγή η τιμή του f μπορεί να αλλάξει μόνο στη περίπτωση που έχουμε άδεια ουρά, και θα πάρει τη τιμή μηδέν.


Η παραπάνω περιγραφή έχει προτάσεις με **** σήμανση για περισσότερη κατανόηση. Δείτε ότι δεν υπάρχει πουθενά χρήση τελεστών σύγκρισης > και <. Υπάρχει το ίσον = και το διάφορο <>. Επίσης δείτε τη χρήση του τελεστή mod, και γιατί το +1 βγήκε εκτός παρένθεσης (και όχι πάνω στο f πριν την τέλεση της mod).
Βασική προϋπόθεση κατανόησης του αλγόριθμου της κυκλικής ουράς, με χρήση πίνακα είναι η αρχικοποίηση και οι τέσσερις περιπτώσεις, α,β,γ και δ, όπου οι πρώτες δυο αφορούν την εισαγωγή τιμής στην ουρά και οι επόμενες δυο την εξαγωγή τιμής από την ουρά. Δεν υπάρχει περίπτωση χρήση κυκλικής ουράς χωρίς το διαχωρισμό (με διακριτές εντολές) των τεσσάρων περιπτώσεων. Αν δεν τις βλέπετε τότε έχετε λάθος κώδικα!