Άσκηση Java

[Kercyn]

Κακέ Μ2000 με μπερδεύεις με τις διαολογιάβες.

[M2000]

Η άσκηση ζητάει σταθερό χρόνο εισαγωγής αριθμού στην λίστα. Αυτό σημαίνει με απλά λόγια ότι δεν γίνεται ταξινόμηση, ούτε αναζήτηση θέσης στη λίστα. Μια είναι η κίνηση:

Αν ο αριθμός που μπαίνει είναι μεγαλύτερος από τον μεγάλο της λίστας (Στη θέση 0) τότε αυτός στην θέση 0 πάει στο τέλος άμεσα (Είναι πίνακας), και στη θέση του μπαίνει ο νέος. Αν όχι τότε πάει στο τέλος ο νέος. Έτσι δεν υπάρχει καμία αναζήτηση που να σχετίζεται με Ν στοιχεία στον πίνακα..

 

Γκέγκε;

 

 

(στο τέλος λέμε στο τελευταίο στοιχείο στον πίνακα όχι του πίνακα..., άρα έχουμε μια μεταβλητή που δείχνει παράλληλα και το μέγεθος του πίνακα σε στοιχεία - όχι το μέγεθος με τα κενά)

 

στο blog έβαλα και την Merge (η οποία εν τέλει για να είναι γρήγορη δεν χρησιμοποιεί το Poll() αλλά απευθείας διαβάζει και βγάζει από το τέλος τα αντικείμενα, στη Μ2000 έχω βάλει αντικείμενα στον πίνακα)

[Kercyn]

Δε με μπέρδεψε ένας ζητούμενος αλγόριθμος 3ου (ή 4ου ή whatever) εξαμήνου, αυτό που με μπέρδεψε είναι ότι θέλει να του φτιάξεις ένα priority queue που τελικά δεν είναι priority queue.

[M2000]

Ρε συ στο προγραμματισμό αν κάτι το βαφτίζει κάποιος Ελέφαντα και σου ζητάει να κάνει πέντε πράγματα...εσύ τι θα σκεφτείς; Να κάνεις αυτά τα πέντε πράγματα που είναι απλά και "διακριτά" ή ότι έχεις θέμα ότι ο Ελέφαντας δεν είναι έτσι;

Άντε να περάσεις μετά!

[Kercyn]

Κοίτα, η αλήθεια είναι ότι από το πρώτο εξάμηνο με ενδιέφερε πιο πολύ να μαθαίνω παρά "να περνάω", γι' αυτό ασχολιόμουν μ' αυτά που μ' ενδιέφεραν και όχι μ' αυτά που δε μ' ενδιέφεραν. Το θέμα είναι ότι αν σε μια τόσο ακριβής επιστήμη όπως ο προγραμματισμός ο άλλος σου ζητάει κάτι και εννοεί κάτι άλλο, τότε υπάρχει πρόβλημα. Ειδικά άμα είσαι νέος και δε μπορείς να καταλάβεις ότι ο άλλος δεν ξέρει τι σου ζητάει. Δε μιλάω γενικά κι αόριστα περί project requirements και specs και δεν ξέρω γω τι άλλο, μιλάω πολύ συγκεκριμένα για αυτό το θέμα. Ο καθηγητής ζητάει κάτι που βαφτίζει "priority queue" χωρίς αυτό να είναι priority queue.

[M2000]

Όχι βέβαια, είναι Priority Queue χρηστικά, δηλαδή έχει αυτό που ζητάει, δηλαδή να υπάρχει ένα στοιχείο σε προτεραιότητα έναντι άλλων, που συνυπάρχουν με αυτό. Κάθε γλώσσα και κάθε τεχνολογία γενικότερα, έχει τα δικά της λεκτικά...Αυτά δεν είναι υποχρεωτικό να συμπίπτουν με τα λεκτικά  της οποιαδήποτε άλλης.

Λοιπόν θα είναι ενδιαφέρον να κάνει ο καθένας εδώ την υλοποίηση στη γλώσσα της αρεσκείας του, και όπως το θέλει, αν έχει όρεξη. Εν τέλει ο φοιτητής ας βγάλει άκρη, από τη συζήτηση, και ας δουλέψει!

[Kercyn]

Κάτσε ρε συ, πώς είναι priority queue; Αν εγώ βάλω ένα στοιχείο που δεν είναι το μέγιστο, πού θα μπει; Στο τέλος; Πού; Και αν αρχίσω να κάνω pop πώς θα βγούνε με τη σωστή σειρά αν δεν είναι sorted;

[M2000]

Θα βγουν πάντα με βάσει την προτεραιότητα...δηλαδή αν βάλεις λέμε τα

10,5, 20, 8 θα πάρεις τα 20,10, 8,5.....αλλά ο πίνακας δεν χρειάζεται να ταξινομείται κάθε φορά που βάζεις ένα στοιχείο. Κάθε φορά όμως που βγάζεις γίνεται επιλογή του στοιχείου που θα κάτσει επόμενο Head. Αυτό είναι απλό πάμε στο τέλος και αρχίζουμε την αναζήτηση μεγαλύτερου, όπου το βρούμε το αλλάζουμε....και έτσι κάνουμε σαν ένα Bubble sort αλλά για ένα στοιχείο, και το τοποθετούμε στο Head

 

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

[Kercyn]

Μα δεν είπα ποτέ ότι θα ταξινομείται κάθε φορά που βάζεις ένα στοιχείο!

 

Επίσης, δε μου απαντάς στην ερώτηση που έκανα παραπάνω. Όταν βάζουμε ένα καινούριο στοιχείο, πού μπαίνει;

edit: never mind...

 

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

 

riiiiiiiight

[M2000]

Μπαίνει ή στη κορυφή (head) ή στο τέλος. Αν είχαμε συνδεδεμένη λίστα, τότε θα μας βοηθούσε να μην φέρναμε το τέλος στην αρχή όπως έχω κάνει στο δικό μου αλγόριθμο, αλλά απλά βρίσκουμε από το τέλος το μεγαλύτερο και το βγάζουμε από την λίστα και το "μοντάρουμε" στη κορυφή. Το κέρδος με την συνδ. λίστα είναι ότι έχουμε πράγματι FIFO σε κάθε προτεραιότητα. Το μειονέκτημα της μεθόδου που έφτιαξα είναι ότι σε ισόβαθμης προτεραιότητας αντικείμενα ενδέχεται να βγει στην κορυφή κάποιο που μπήκε τελευταίο, άρα να έχουμε LIFO (μόνο για τα ισόβαθμα) αν δεν μας νοιάζει δεν πειράζει!

[AlexHello]

Διορθώστε με αν κάνω λάθος αλλά ένα pq backed με heap, σου προσφέρει αυτά τα complexities:

 

Method           Complexity

top                  O(1)

push               O(logn) (Λόγω bubble up)

pop                 O(logn) (Λόγω bubble down)

 

Αν αποφευχθούν τα bubble-up και bubble-down, τότε το pq χάνει την ουσία του.

Άρα πως ζητείται η προσθήκη να γίνεται σε O(1) ?

[M2000]

Η προσθήκη όπως το ζητάει γίνεται χωρίς να ενδιαφέρει πόσα στοιχεία έχει η ουρά. :Αυτό σημαίνει το Ο(1)΄. Τι έχει; έχει δυο δείκτες, μια για την θέση 0 και μία για την θέση στον πίνακα που θα γραφτεί το επόμενο στοιχείο. Ή θα είναι αυτό που θα μπει στη λίστα, ή θα είναι το στοιχείο στη θέση 0, και στη θέση του θα μπει το νέο. Έτσι θα κάνει μια αύξηση κατά ένα του δείκτη που δείχνει το επόμενο ελεύθερο στοιχείο πίνακα, και ή μια ή δυο αντιγραφές.

Αν υποθέσουμε ότι έχουμε κυκλική λίστα, τότε έχουμε ή προσθήκη στο rear, ;h προσθήκη στο front, ανάλογα με την συνθήκη. Αλλά έτσι δεν καλύπτουμε την απαίτηση να είναι στο στοιχείο 0 του πίνακα το Head..ή κορυφή όπως θες πες το.

Νομίζω ότι αυτή η άσκηση τους προετοιμάζει για να πάνε σε πιο ουσιαστικό αλγόριθμο.

 

(έχουμε Push O(1) κατ΄απαίτηση)

[AlexHello]

Καταλαβαίνω τι λες Μ2000, αλλά στο παράδειγμά σου της κυκλικής λίστας (ξεχνάμε για λίγο το head πρέπει να ειναι στο στοιχείο 0), κάνωντας τις εξής προσθήκες:

 

=============================================

Προσθήκη 5 (κανένα στοιχείο αρα το 5 μπαίνει στο front):            

 

[5]

 

Προσθήκη 2 (το 2 < 5 αρα το 2 μπαίνει στο rear):

 

[5, 2]

 

Προσθήκη 3 (το 3 < 5 άρα το 3 μπαίνει στο rear):

 

[5, 2, 3]

=============================================

 

Παρατηρούμε οτί κάνοντας επακόλουθα pop, παίρνουμε πίσω τα στοιχεία 5 -> 2 -> 3 το οποίο προφανώς είναι

λάθος.

 

Συνεπώς δεν διατηρείται ο βασικός μηχανισμός της pq, αν δεν έχουμε επιπλέον βήματα όπως το bubble-up και το bubble-down για να αναδιαμορφωθεί το δέντρο.

[CrimsonSky_gr]

Καταλαβαίνω τι λες Μ2000, αλλά στο παράδειγμά σου της κυκλικής λίστας (ξεχνάμε για λίγο το head πρέπει να ειναι στο στοιχείο 0), κάνωντας τις εξής προσθήκες:

 

=============================================

Προσθήκη 5 (κανένα στοιχείο αρα το 5 μπαίνει στο front):            

 

[5]

 

Προσθήκη 2 (το 2 < 5 αρα το 2 μπαίνει στο rear):

 

[5, 2]

 

Προσθήκη 3 (το 3 < 5 άρα το 3 μπαίνει στο rear):

 

[5, 2, 3]

=============================================

 

Παρατηρούμε οτί κάνοντας επακόλουθα pop, παίρνουμε πίσω τα στοιχεία 5 -> 2 -> 3 το οποίο προφανώς είναι

λάθος.

 

Συνεπώς δεν διατηρείται ο βασικός μηχανισμός της pq, αν δεν έχουμε επιπλέον βήματα όπως το bubble-up και το bubble-down για να αναδιαμορφωθεί το δέντρο.

οχι γιατι στο extract θα φερεις το 3 στην πρωτη θεση..

[AlexHello]

οχι γιατι στο extract θα φερεις το 3 στην πρωτη θεση..

 

..Ναι αλλά με το tradeoff οτι πολλαπλασιάζεις τον χρόνο του extract οταν πραγματοποιείς επακόλουθα push εφόσον μπορεί σε περισσότερα απο ενα στοιχεία να πρέπει να κανεις impose το heap property