Θέμα: Καλύτερη υλοποίηση ουράς

[Vangelis]

Ένα πολύ ταιριαστό είναι αυτό που είπα πιο πριν, "καθιστή ουρά τράπεζας με καρέκλες". Όταν καθόμαστε σε καρέκλες δεν κάνουμε ολίσθηση.
Επίσης και αυτό με τα νούμερα προτεραιότητας ταιριάζει μια χαρά. Δεν υπάρχει ολίσθηση στα νούμερα προτεραιότητας.
Και σίγουρα μπορούμε να βρούμε πολλά παραδείγματα ακόμα, π.χ. ουρά παιδιών στο "γύρω-γύρω" στην παιδική χαρά που είναι από μόνο του κυκλικό κλπ.

Αυτό δεν ισχύει, απλά επιλέχθηκαν ακατάλληλα παραδείγματα, και επιπρόσθετα προσαρμόστηκαν με λάθος τρόπο. Θα πω κάτι που θα ακουστεί πολύ κουφό, αλλά με δεύτερη σκέψη ισχύει.

Ο πρώτος άνθρωπος που μπαίνει στην "όρθια ουρά ολίσθησης" το πρωί στην τράπεζα, δεν διασχίζει ακριβώς τον ίδιο διάδρομο με αυτόν που μπαίνει αργότερα που γίνεται η λειτουργία της ολίσθησης; Γιατί αυτούς που μπήκαν αργότερα τους "περνάμε" από όλες τις θέσεις του πίνακα, ενώ τον πρώτο τον "τηλεμεταφέρουμε" κατευθείαν στην πρώτη θέση;
Αν μοντελοποιούμε τον φυσικό κόσμο, τότε θα έπρεπε να γράψουμε σε κώδικα και τη δική του διάσχιση του διαδρόμου:

ΓΙΑ ι ΑΠΟ Ν ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
  Α[ι] <- άνθρωπος
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αυτή είναι η "ολίσθηση" που γίνεται στον φυσικό κόσμο, ενώ εμείς την αναφέρουμε ως:
  Α[1] <- άνθρωπος
...σαν αυτός να μη διέσχισε το διάδρομο αλλά να τηλεμεταφέρθηκε στη θέση 1.

Εννοείται όμως ότι ΔΕΝ θέλουμε τέτοια μοντελοποίηση. Όπως δεν θέλουμε να αναφέρουμε τη "διάσχιση του 1ου ανθρώπου", έτσι δεν θέλουμε να αναφέρουμε και την "διάσχιση=ολίσθηση των επόμενων που μπήκαν λίγη ώρα αργότερα".

Επιπρόσθετα, η λύση του συμπληρωματικού τεύχους δεν κάνει καν συνεχή ολίσθηση, όπως γίνεται στην τράπεζα, δηλαδή κάθε φορά που εξυπηρετείται ένας άνθρωπος που κάνουν όλοι ένα βήμα μπροστά. Κάνει μόνο μια μαζική ολίσθηση όταν rear=N, με πολλά βήματα μπροστά, που δεν αντιστοιχεί.

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

[alkisg]

Στο παράδειγμα με τις καρέκλες δεν θα γίνει καμία μετακίνηση. Μάλιστα οι πελάτες δεν πρέπει καν να σκέπτονται "είμαι τρίτος στη σειρά κλπ". Δεν έχουν μυαλό / επεξεργαστές, είναι απλά "δεδομένα" στο πρόβλημα αυτό. Αν τους παρομοιάσουμε με CPUs, τότε δεν μιλάμε πια για ουρές αλλά για παράλληλο προγραμματισμό με Ν επεξεργατές.

Θα χρειαστεί όμως να παρομοιάσουμε την CPU με έναν ταξιθέτη. Με το που μπαίνει κάποιος πελάτης στην τράπεζα, τον τοποθετεί στην κατάλληλη καρέκλα (=θέση "rear" του πίνακα), ενώ όταν είναι ώρα να φύγει κάποιος από την ουρά και να πάει στο ταμείο, παίρνει αυτόν από τη θέση "front".

Είναι αντίστοιχο με το bubble sort, που τους κάνουμε ένα σχηματάκι για να τους εξηγήσουμε. Κι εδώ θα χρειαστεί μια μικρή εξήγηση για το "mod N", την κυκλική θεώρηση των καρεκλών.

Θεωρώ ότι είναι λάθος να διδάξουμε ολίσθηση στις ουρές. Με τον όρο "ολίσθηση" εννοούμε να απασχολήσουμε την CPU Ν φορές σε μία Εισαγωγή. Δηλαδή αν μια ουρά έχει 1 τρις στοιχεία, και μπει ένα ακόμα, η διαφορά είναι αν θα μετακινηθούν 1 τρις στοιχεία ή κανένα. Το Ο(1) με το Ο(Ν) είναι μέρα με τη νύχτα.

[thaaanos]

από τις τρεις υλοποιήσεις, του βιβλίου είναι νομίζω η χειρότερη,

προσωπικά δεν βλέπω κανένα πρόβλημα, με την κυκλική ουρά -είναι η πιο 'καθαρη'- και την απλή χρήση του τελεστή mod. Αν μη τι  άλλο να δείξουμε και σε τι χρησιμεύει...
Τώρα για ολίσθηση δεν το συζητάω καν
παραθέτω συνημμένα.
Αυτό που με προβλημάτισε είναι οι έλεγχοι για γεμάτη/άδεια δομή, ευθύνη του χρήστη; η της δομής;

[junior]

Παραθέτω εδώ, ένα pdf που έχω, σαν εναλλακτική στο σχολικό βιβλίο. Θα το παραλλάξω, για f=1, r=0, αν δεν βρω κάποιο εμπόδιο (ακόμη σπάω το κεφάλι μου, τι στο καλό με κόλλησε προχθές).
Πιο πολύ το βάζω μήπως κάποιος βοηθηθεί από τη χρήση του, δεν ξέρω αν συνεισφέρει κάτι στη κουβέντα γενικότερα περί υλοποίησης. Θα προτιμούσα αυτό, παρά αυτό που έχουμε στο βιβλίο. Αν βλέπετε κάτι λάθος, είμαι όλος αυτιά.. 

Βάζω και μια εικονίτσα, για πιο γρήγορο τσεκ, μην το κατεβάζετε τσάμπα, όσοι δεν το χρειάζεστε.

Μήπως στην προτεινόμενη υλοποίηση της εισαγωγής ΜΕ ολίσθηση έχει γίνει κάποιο λάθος ;

ΑΝ r = N ΤΟΤΕ               ! Αν r στο τέλος του πίνακα
  ΑΝ f > 1 ΤΟΤΕ              ! αλλά υπάρχει χώρος
    k <- 1
    ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r
      Q[k] <- Q             !ολίσθηση
      k <- k + 1               !    >>
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ       !Στο τέλος της επανάληψης η μεταβλητή k θα έχει τιμή +1 παραπάνω από το σύνολο των στοιχείων της ουράς
    f <- 1
    r <- k                  !οπότε εδώ ο δείκτης r δείχνει όχι στο τέλος της ουράς αλλά σε +1
    r <- r + 1            ! εισαγωγή
    Q[r] <- input       !      >>
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ " Ουρά γεμάτη, αδυναμία εισαγωγής "
  ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ …
 
Μήπως το σωστό θα ήταν

ΑΝ r = N ΤΟΤΕ              ! Αν r στο τέλος του πίνακα
  ΑΝ f > 1 ΤΟΤΕ            ! αλλά υπάρχει χώρος
    k <- 0
    ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r
      k <- k + 1                !ολίσθηση
      Q[k] <- Q             !    >>
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ   
    f <- 1             
    r <- k             
    ΔΙΑΒΑΣΕ input         !εισαγωγή
    r <- r + 1                !    >>
    Q[r] <- input           !   >>
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ " Ουρά γεμάτη, αδυναμία εισαγωγής "
  ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ …

[mousipower]

Τυχαία πέτυχα την ωραία "θεωρητική" συζήτηση που κάνετε από πέρσι για την προσέγγιση-υλοποίηση που πρέπει να κάνουμε σε μια ουρά. Εγώ μόλις τελείωσα τη λύση των ασκήσεων  σε ουρές αποτρέποντας τους μαθητές μου να κοιτούν τα εκτρώματα των "ενδεικτικών " ευτυχώς λύσεων του βιβλίου της ουράς ειδικά στην άσκηση 6 .
Πέρυσι αποφύγαμε την ολίσθηση με οδηγίες άνωθεν φέτος σε επικοινωνία με τον σύμβουλο,  το έθεσε πολύ ευγενικά, πρέπει να την εξηγήσουμε-υλοποιήσουμε οπότε αναγκαστικά την εξήγησα.
Η κοινή λογική με αναγκάζει να αναφέρω ότι η υλοποίηση μιας "κυκλικής ουράς" είναι αρκετά δυσκολοχώνευτη υπόθεση για τους  μαθητές, ειδικά με την τηλεκπαίδευση, μιας και δεν μπορώ να δω τον τρόμο και την απόγνωση στα πρόσωπά τους τη ώρα που θα την εξηγώ. Μπορώ όμως να υλοποιήσω μια ολίσθηση η οποία βασίζεται στην πρακτική που χρησιμοποιούν καθημερινά στη ζωή τους: δεν περιμένουμε να γεμίσει η ουρά (στην εισαγωγή) και τότε να μετακινήσουμε  όλη την ουρά στις άδειες θέσεις στην αρχή της ουράς, αν υπάρχουν, αλλά με την εξυπηρέτηση (στην εξαγωγή) του πρώτου της ουράς μετακινούνται όλοι μια θέση μπροστά και έτσι ο δείκτης front είναι πάντα 1! και προσέχουμε να αλλάξουμε rear <-- rear - 1.
Από τη ζωή βγαλμένο και γλιτώνουμε τους μαθητές μας από μια επίπονη διαδικασία, εκτός αν η κουβέντα γίνεται αποκλειστικά για την δική μας επάρκεια οπότε ζητώ συγνώμη δεν θέλω να  θεωρηθώ εξυπνάκιας (άλλωστε είμαι πολύ γέρος γι' αυτό).
Παραθέτω τρείς λύσεις που έχω δώσει στα παιδιά μου και θα ήθελα feedback αν θεωρεί κάποιος ότι υπάρχει κάποια χοντράδα ή κάτι πραγματικά μου ξέφυγε και λόγω ηλικίας δεν το βλέπω. Προσπαθώ να είμαι όσο πιο κοντά στην εισαγωγή-εξαγωγή του βιβλίου σελ. 26 και φυσικά δεν υπάρχει ποτέ περίπτωση να ελέγξω front > rear προτιμώ να πάω σε μια γραμματεία να συμπληρώνω φύλλα excel, αυτό δυστυχώς είναι μπηχτή για τις απείρου κάλλους "ενδεικτικές" λύσεις που  τους το δώσαν και σε βιβλίο..
Υ.Γ. Για να αποφύγουμε τα 5 και 6 φωλιασμένα επίπεδα ελέγχων σε ουρές - στοίβες  είναι απαραίτητο να διδάσκονται  πρώτα τα  υποπρογράμματα, γιατί μετά από 2 -3 σελίδες πρόγραμμα έχουν χάσει όλα τα Τελος_αν και Τέλος_επανάληψης και πάντα ξεχνάνε να κλείσουν κάτι.(θυμάμαι στη σχολή μάς λέγανε μέχρι 3 επίπεδα να κατεβαίνουμε στο 4ο καιγόμαστε). Σίγουρα  θα ξανακάνω 2 ασκήσεις με χρήση διαδικασιών αργότερα για να σπάσει αυτό το "σεντόνι".
Αν σας κούρασα συγνώμη, θα ξαναμπώ στη τρύπα μου και θα σας αφήσω ήσυχους να συνεχίσετε να "ψάχνεστε", καλό είναι να έχεις όρεξη. Καλή δύναμη!!

[mousipower]

Αφού δεν το διόρθωσε κανείς το ξαναστέλνω διορθωμένο και τέλος....

[mousipower]

Ο ΔΑΙΜΩΝ του τυπογραφείου ξαναχτύπησε και φυσικά λείπει ένα ΤΕΛΟΣ_ΑΝ, αυτά που έλεγα (πάνω από 3 επίπεδα κάνει τζιζ)  ..

[Γιάννης Αναγνωστάκης]

Μετακινήθηκε σε άλλο thread..

[tsioulak]

Τυχαία πέτυχα την ωραία "θεωρητική" συζήτηση που κάνετε από πέρσι για την προσέγγιση-υλοποίηση που πρέπει να κάνουμε σε μια ουρά. Εγώ μόλις τελείωσα τη λύση των ασκήσεων  σε ουρές αποτρέποντας τους μαθητές μου να κοιτούν τα εκτρώματα των "ενδεικτικών " ευτυχώς λύσεων του βιβλίου της ουράς ειδικά στην άσκηση 6 .
Πέρυσι αποφύγαμε την ολίσθηση με οδηγίες άνωθεν φέτος σε επικοινωνία με τον σύμβουλο,  το έθεσε πολύ ευγενικά, πρέπει να την εξηγήσουμε-υλοποιήσουμε οπότε αναγκαστικά την εξήγησα.
Η κοινή λογική με αναγκάζει να αναφέρω ότι η υλοποίηση μιας "κυκλικής ουράς" είναι αρκετά δυσκολοχώνευτη υπόθεση για τους  μαθητές, ειδικά με την τηλεκπαίδευση, μιας και δεν μπορώ να δω τον τρόμο και την απόγνωση στα πρόσωπά τους τη ώρα που θα την εξηγώ. Μπορώ όμως να υλοποιήσω μια ολίσθηση η οποία βασίζεται στην πρακτική που χρησιμοποιούν καθημερινά στη ζωή τους: δεν περιμένουμε να γεμίσει η ουρά (στην εισαγωγή) και τότε να μετακινήσουμε  όλη την ουρά στις άδειες θέσεις στην αρχή της ουράς, αν υπάρχουν, αλλά με την εξυπηρέτηση (στην εξαγωγή) του πρώτου της ουράς μετακινούνται όλοι μια θέση μπροστά και έτσι ο δείκτης front είναι πάντα 1! και προσέχουμε να αλλάξουμε rear <-- rear - 1.
Από τη ζωή βγαλμένο και γλιτώνουμε τους μαθητές μας από μια επίπονη διαδικασία, εκτός αν η κουβέντα γίνεται αποκλειστικά για την δική μας επάρκεια οπότε ζητώ συγνώμη δεν θέλω να  θεωρηθώ εξυπνάκιας (άλλωστε είμαι πολύ γέρος γι' αυτό).
Παραθέτω τρείς λύσεις που έχω δώσει στα παιδιά μου και θα ήθελα feedback αν θεωρεί κάποιος ότι υπάρχει κάποια χοντράδα ή κάτι πραγματικά μου ξέφυγε και λόγω ηλικίας δεν το βλέπω. Προσπαθώ να είμαι όσο πιο κοντά στην εισαγωγή-εξαγωγή του βιβλίου σελ. 26 και φυσικά δεν υπάρχει ποτέ περίπτωση να ελέγξω front > rear προτιμώ να πάω σε μια γραμματεία να συμπληρώνω φύλλα excel, αυτό δυστυχώς είναι μπηχτή για τις απείρου κάλλους "ενδεικτικές" λύσεις που  τους το δώσαν και σε βιβλίο..
Υ.Γ. Για να αποφύγουμε τα 5 και 6 φωλιασμένα επίπεδα ελέγχων σε ουρές - στοίβες  είναι απαραίτητο να διδάσκονται  πρώτα τα  υποπρογράμματα, γιατί μετά από 2 -3 σελίδες πρόγραμμα έχουν χάσει όλα τα Τελος_αν και Τέλος_επανάληψης και πάντα ξεχνάνε να κλείσουν κάτι.(θυμάμαι στη σχολή μάς λέγανε μέχρι 3 επίπεδα να κατεβαίνουμε στο 4ο καιγόμαστε). Σίγουρα  θα ξανακάνω 2 ασκήσεις με χρήση διαδικασιών αργότερα για να σπάσει αυτό το "σεντόνι".
Αν σας κούρασα συγνώμη, θα ξαναμπώ στη τρύπα μου και θα σας αφήσω ήσυχους να συνεχίσετε να "ψάχνεστε", καλό είναι να έχεις όρεξη. Καλή δύναμη!!

Αφού δεν το διόρθωσε κανείς το ξαναστέλνω διορθωμένο και τέλος....

Μετακινήθηκε σε άλλο thread..

Αν κατάλαβα καλά στην 2η υλοποίηση κάνεις ολίσθηση κάθε φορά που κάνεις εξαγωγή, αυτό αυξάνει κατά πολύ την πολυπλοκότητα του κώδικα, να υποθέσω ότι το έκανες επειδή είναι κάπως πιο εύκολο για να το καταλάβουν οι μαθητές; ή μήπως το έκανες για να δείξεις στους μαθητές και αυτήν την περίπτωση; (μήπως και πέσει)

[tsioulak]

από τις τρεις υλοποιήσεις, του βιβλίου είναι νομίζω η χειρότερη,

προσωπικά δεν βλέπω κανένα πρόβλημα, με την κυκλική ουρά -είναι η πιο 'καθαρη'- και την απλή χρήση του τελεστή mod. Αν μη τι  άλλο να δείξουμε και σε τι χρησιμεύει...
Τώρα για ολίσθηση δεν το συζητάω καν
παραθέτω συνημμένα.
Αυτό που με προβλημάτισε είναι οι έλεγχοι για γεμάτη/άδεια δομή, ευθύνη του χρήστη; η της δομής;

Είναι η ιδέα μου ή στην πρώτη εισαγωγή δεν το βάζεις στην θέση 1 αλλά στην θέση 2;
Στην υλοποίηση της κυκλικής ουράς αναφέρομαι.

[mousipower]

Αν κατάλαβα καλά στην 2η υλοποίηση κάνεις ολίσθηση κάθε φορά που κάνεις εξαγωγή, αυτό αυξάνει κατά πολύ την πολυπλοκότητα του κώδικα, να υποθέσω ότι το έκανες επειδή είναι κάπως πιο εύκολο για να το καταλάβουν οι μαθητές; ή μήπως το έκανες για να δείξεις στους μαθητές και αυτήν την περίπτωση; (μήπως και πέσει)

Νομίζω είναι πιο κατανοητό και εύκολο (οι ίδιοι μου το είπαν, ευτυχώς δεν κάνουμε πολυπλοκότητα ή βελτιστοποίηση αλγόριθμου), αλλιώς η λύση του βιβλίου και αν ήταν δυσνόητη και πολύπλοκη!!