Απορια στις λιστες

Ξεκίνησε από computerscience, 31 Ιαν 2020, 01:51:33 ΜΜ

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

computerscience

Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

P.Tsiotakis

Για κάθε κόμβο της λίστας απαιτούνται 2 θέσεις μνήμης για την απλά και 3 θέσεις για την διπλά συνδεδεμένη λίστα, σε σχέση με τον πίνακα που απαιτείται 1.
Είναι περισσότερες οι θέσεις μνήμης.

Στους πίνακες το μειονέκτημα "ενεργοποιείται" όταν αναγκάζεται ο προγραμματιστής να δεσμεύσει πολλές περισσότερες θέσεις μνήμης για να είναι καλυμμένος.
Π.χ. στο θέμα εξετάσεων του 2010 θα έπρεπε να δεσμεύσει κανά εκατομμύριο θέσεις μνήμης γιατί τόσοι είναι οι μαθητές σε όλη την Ελλάδα που δυνητικά θα λάβουν μέρος στους μαθητικούς αγώνες.

petrosp13

Και οι πίνακες και οι λίστες δεσμεύουν μνήμη, αλλά σκέψου ότι ο πίνακας αποθηκεύει μόνο τα δεδομένα και η λίστα και τους δείκτες κάθε επόμενου κόμβου
Είτε στατικά, είτε δυναμικά, οι λίστες δεσμεύουν σχεδόν διπλάσια μνήμη από τον πίνακα
Κι αυτό για απλά συνδεδεμένη λίστα
Η διπλά συνδεδεμένη, απαιτεί σχεδόν τριπλάσια μνήμη
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

tdrivas

Παράθεση από: computerscience στις 31 Ιαν 2020, 01:51:33 ΜΜ
Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

Στις δυναμικές δομές πρέπει να δαπανήσεις μία ή περισσότερες θέσεις μνήμης για να γνωρίζει ο κάθε κόμβος ποια θέση μνήμης είναι το αδερφάκι του.

Στην αντίπερα όχθη, στον πίνακα a priori είναι γνωστό αυτό, καθώς οι κόμβοι του είναι σε συνεχόμενες θέσεις μνήμης.

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

π.χ. εξετάζω οχήματα που παιρνούν τα διόδια σε μία ημέρα.

Βάζω πίνακα 500,000 θέσεων για να είμαι σίγουρος => 500,000 θέσεις
Αν τελικά περάσουν 20,000 με απλά συνδεδεμένη λίστα θα ήθελα => 20,000 χ 2 = 40,000 θέσεις

Ελπίζω να βοηθήσαμε
Thanassis Drivas
BSc in Computer Science
MSc in Space Science Applications and Technologies
https://github.com/tdrivas

computerscience

Ναι ευχαριστω πολυ ολους

ΔΗΜΗΤΡΗΣ Χ

Το οτι αναφερεται ως μειονεκτημα των πινακων μεσα στο σχολικο βιβλιο το γεγονος οτι απαιτουν μνημη, δεν εχει να κανει σε συγκριση με τις λιστες αλλα σε συγκριση με τη μη χρησιμοποιηση τους οταν αυτο δεν απαιτειται. Για παραδειγμα διαβασε  1000 αριθμους και βγαλε μεσο ορο. Χωρις πινακα θες 4 θεσεις (λαμβανοντας υπ οψιν χονδρικα βεβαια καθε μεταβλητη ως μια θεση) ενω με πινακα θες 1003.
Εκει εστιαζεται νομιζω.
θα συμφωνησω συναδελφε οτι ειναι ενα απο τα πολλα διφορουμενα σημεια στο μαθημα και ειδικα με τη νεα υλη, και δυστυχως ειναι φυσιολογικο οταν υπαρχουν 4 βιβλια για ενα μαθημα.

ΔΗΜΗΤΡΗΣ Χ

Και βεβαια ισχυουν και ολα οσα γραφτηκαν για την "ασκοπη χρηση μεγαλων πινακων" και  απο τους 2 συναδελφους πριν, σε σχεση με τις λιστες με πολυ ευστοχα παραδειγματα.
Απλα κανω την προηγουμενη αναφορα για αυτο που λεει στο 9ο κεφαλαιο, γιατι νομιζω στο συγκεκριμενο σημειο ο συγγραφεας αναφερεται στη χρηση η οχι πινακα.

Λαμπράκης Μανώλης

Παράθεση από: tdrivas στις 31 Ιαν 2020, 04:50:12 ΜΜ
Στις δυναμικές δομές πρέπει να δαπανήσεις μία ή περισσότερες θέσεις μνήμης για να γνωρίζει ο κάθε κόμβος ποια θέση μνήμης είναι το αδερφάκι του.

Στην αντίπερα όχθη, στον πίνακα a priori είναι γνωστό αυτό, καθώς οι κόμβοι του είναι σε συνεχόμενες θέσεις μνήμης.

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

π.χ. εξετάζω οχήματα που παιρνούν τα διόδια σε μία ημέρα.

Βάζω πίνακα 500,000 θέσεων για να είμαι σίγουρος => 500,000 θέσεις
Αν τελικά περάσουν 20,000 με απλά συνδεδεμένη λίστα θα ήθελα => 20,000 χ 2 = 40,000 θέσεις

Ελπίζω να βοηθήσαμε

Καλημέρα σε όλους
Θανάση πολύ εύστοχα αυτά που αναφέρεις, όπως και οι υπόλοιποι συνάδελφοι ... να ρωτήσω, στο  σχήμα που παραθέτεις, θα μπορούσε κάποιος στις λίστες να βάλει 2 δεσμευμένες θέσεις για κάθε κόμβο, ώστε να φαίνεται κάπως πιο πρακτικά η επιπλέον επιβάρυνση στη μνήμη ?? θα μπορούσε κα πει κάποιος, "εγώ βλέπω 7 δεσμευμένες θέσεις σε πίνακα και 7 στη λίστα" .. αυτό θα "χαλούσε" κάτι στο σχήμα ??

akalest0s

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

Η αναπαράσταση μνήμης του Δρίβα είναι όμοια με αυτή που χρησιμοποιώ και εγώ, και νομίζω βοηθάει πολύ τα παιδιά να κατανοήσουν τι πρέπει να γράφουν στον κώδικα αντίστοιχα, για να δουλεύει σωστά ο αλγόριθμός τους. Είναι ένα σημείο που κάλλιστα θα μπορούσε να συμπεριληφθεί στο (νέο) βιβλίο μαθητή. Αν και εκ πρώτης όψεως, φαίνεται too much, και επικίνδυνα "κομπιουτερίστικο", στη πραγματικότητα, τέτοιες προσεγγίσεις είναι που δημιουργούν την απαραίτητη σύνδεση θεωρίας ("πότε πρέπει να χρησιμοποιούνται οι πίνακες"), με την πράξη. Σε κάθε κεφάλαιο που βλέπω ότι προσφέρεται, κάνω τέτοιες αναφορές με σχέδιο.
"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

pgrontas

Παράθεση από: akalest0s στις 01 Φεβ 2020, 11:28:36 ΠΜ
Η αναπαράσταση μνήμης του Δρίβα είναι όμοια με αυτή που χρησιμοποιώ και εγώ, και νομίζω βοηθάει πολύ τα παιδιά να κατανοήσουν τι πρέπει να γράφουν στον κώδικα αντίστοιχα, για να δουλεύει σωστά ο αλγόριθμός τους. Είναι ένα σημείο που κάλλιστα θα μπορούσε να συμπεριληφθεί στο (νέο) βιβλίο μαθητή. Αν και εκ πρώτης όψεως, φαίνεται too much, και επικίνδυνα "κομπιουτερίστικο", στη πραγματικότητα, τέτοιες προσεγγίσεις είναι που δημιουργούν την απαραίτητη σύνδεση θεωρίας ("πότε πρέπει να χρησιμοποιούνται οι πίνακες"), με την πράξη. Σε κάθε κεφάλαιο που βλέπω ότι προσφέρεται, κάνω τέτοιες αναφορές με σχέδιο.

Παρεμβαίνω λίγο στο θέμα για ένα άσχετο σχόλιο με αφορμή την αναπαράσταση μνήμης, όχι μόνο στο συγκεκριμένο θέμα αλλά και στο βιβλίο (σελ. 37 - Πληροφορική).
Πάντα θεωρούσα ότι μνήμη είναι καλύτερο να συμβολίζεται ως μονοδιάστατος πίνακας (αφού έχει μία διεύθυνση, όχι δύο). Αν δεν έχω άδικο, μήπως μπερδέψουμε τα παιδιά, με αυτόν τον τρόπο;

Φυσικά, το καλύτερο από όλα είναι να μην χρησιμοποιείται πινακας ή λίστα όταν δεν χρειάζεται (όπως το 2010).
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

akalest0s

Παράθεση από: pgrontas στις 01 Φεβ 2020, 11:57:16 ΠΜ
Παρεμβαίνω λίγο στο θέμα για ένα άσχετο σχόλιο με αφορμή την αναπαράσταση μνήμης, όχι μόνο στο συγκεκριμένο θέμα αλλά και στο βιβλίο (σελ. 37 - Πληροφορική).
Πάντα θεωρούσα ότι μνήμη είναι καλύτερο να συμβολίζεται ως μονοδιάστατος πίνακας (αφού έχει μία διεύθυνση, όχι δύο). Αν δεν έχω άδικο, μήπως μπερδέψουμε τα παιδιά, με αυτόν τον τρόπο;
Προσωπικά, χρησιμοποιώ και τις δύο περιπτώσεις, ανάλογα την πολυπλοκότητα του παραδείγματος, κάθε φορά. Δεν βλέπω στα παιδιά να υπάρχει πρόβλημα σύγχυσης. Τους εξηγώ ότι όλο αυτό είναι σχηματικό, και όχι σε αυστηρή αναλογία με την πραγματική κατάσταση στη μνήμη. Ειδικά στο "πλέγμα", χάνεις σε αυτό που είπες, όντως, αλλά κερδίζεις στο να δείξεις λίγο το χαώδες της μνήμης, κρατώντας οπτικά κοντά τα ζητούμενα κελιά. Και ένα πρακτικό, πιο ασήμαντο, είναι ότι, κάποιες φορές, ο διαθέσιμος χώρος στο χαρτί/πίνακα προσφέρεται καλύτερα για το ένα ή το άλλο.
Όλα αυτά δεν θα είχαν σημασία, αν τα παιδιά μπερδεύονταν. Αλλά για την ώρα, δεν έχω εντοπίσει πρόβλημα.

συγγνώμη για το offtopic
"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

droopy

Kαλησπέρα,

στη σελίδα 40 του Συμπληρωματικού Υλικού αναφέρει:

"Όπως φαίνεται και στην Εικόνα 1.3.5, οι απαιτούμενες ενέργειες για την εισαγωγή (παρεμβολή) του
νέου κόμβου είναι ο δείκτης του δεύτερου κόμβου να δείχνει τον νέο κόμβο και ο δείκτης του νέου
κόμβου να δείχνει τον τέταρτο κόμβο (δηλαδή, να πάρει την τιμή που είχε πριν την εισαγωγή ο δείκτης
του τρίτου κόμβου)."

Δεν θα έπρεπε να λέει του δεύτερου κόμβου;

Ευχαριστώ.


evry

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

Παράθεση από: droopy στις 02 Φεβ 2020, 12:05:06 ΠΜ
Kαλησπέρα,

στη σελίδα 40 του Συμπληρωματικού Υλικού αναφέρει:

"Όπως φαίνεται και στην Εικόνα 1.3.5, οι απαιτούμενες ενέργειες για την εισαγωγή (παρεμβολή) του
νέου κόμβου είναι ο δείκτης του δεύτερου κόμβου να δείχνει τον νέο κόμβο και ο δείκτης του νέου
κόμβου να δείχνει τον τέταρτο κόμβο (δηλαδή, να πάρει την τιμή που είχε πριν την εισαγωγή ο δείκτης
του τρίτου κόμβου)."

Δεν θα έπρεπε να λέει του δεύτερου κόμβου;

Ευχαριστώ.


What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

#13
Σχετικά με το αρχικό ερώτημα δε νομίζω ότι το βασικό πρόβλημα είναι η επιπλέον μνήμη που δεσμεύουν οι κόμβοι της λίστας (είναι και αυτό αλλά όχι το πρωτεύον).
Συγκεκριμένα λέει:
ΠαράθεσηΟι συνδεδεμένες λίστες έχουν πολύ μεγαλύτερη επιβάρυνση από τους πίνακες, αφού οι συνδεδεμένοι κόμβοι της λίστας είναι δυναμικά κατανεμημένοι (οι οποίοι είναι λιγότερο αποτελεσματικοί στη χρήση της μνήμης)

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

Αυτή είναι η δική μου ερμηνεία
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

droopy

Παράθεση από: evry στις 02 Φεβ 2020, 09:42:10 ΠΜ
Μάλλον εννοεί τον κόμβο που έγινε 3ος μετά την εισαγωγή του καινούργιου.
Νομίζω είναι η μόνη πιθανή εξήγηση.


Καλημέρα,

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

droopy

#15
Kαλησπέρα,

στην νέα έκδοση 2020 του Συμπληρωματικού Υλικού στη σελίδα 40 διορθώθηκε τελικά το λάθος και αναφέρει πλέον:

"Όπως φαίνεται και στην Εικόνα 1.3.5, οι απαιτούμενες ενέργειες για την εισαγωγή (παρεμβολή) του
νέου κόμβου είναι ο δείκτης του δεύτερου κόμβου να δείχνει τον νέο κόμβο και ο δείκτης του νέου
κόμβου να δείχνει τον τέταρτο κόμβο (δηλαδή, να πάρει την τιμή που είχε πριν την εισαγωγή ο δείκτης
του δεύτερου κόμβου)." (στην παλιά έκδοση έλεγε τρίτου κόμβου).

Με μια πρώτη ματιά είδα ότι διορθώθηκαν και τα παρακάτω που είχαν επισημανθεί από αρκετούς καθηγητές:

σελ 19 και 20 AN top < 250 στη θέση του AN top <= 250 
σελ 45 το μεσαίο παιδί της ΕΙΡΗΝΗΣ είναι η ΜΑΡΙΑ και όχι η ΕΙΡΗΝΗ
σελ 77 άλλαξε το κείμενο της 2ης κουκκίδας στην ανάλυση (γκρι πλαίσιο)
σελ 80 προστέθηκε η λέξη θετικός στην εντολή ΓΡΑΨΕ στη γραμμή 14 στη λύση του [3.5]

Στη σελίδα 123 στη γραμμή 21 του κώδικα σωστά προστέθηκε η Εντολή ΑΝ γιατί στην περίπτωση αρνητικής τιμής στα κυβικά δεν έπαιρνε αρχική τιμή η μεταβλητή οφειλή. Όμως έχει πάλι λάθος γιατί έπρεπε να λέει ΑΝ κυβικά>0 και όχι ΑΝ κυβικά < 0 όπως είναι στην τελευταία έκδοση.








Σάκης Δημόπουλος

2 βιντεομαθήματα για τις Λίστες:
Στο πρώτο αναπτύσσονται τα εξής:
Λίστες Ι  -  Απλά Συνδεδεμένη Λίστα
Άλλες Δομές Δεδομένων
Στατικές Δομές Δεδομένων
Δυναμικές Δομές Δεδομένων
Τι είναι μια απλά συνδεδεμένη Λίστα ;
Τι είναι ένας Δείκτης (pointer) ;
Προσπέλαση στους κόμβους μιας απλά συνδεδεμένης Λίστας
Εισαγωγή ενός νέου κόμβου  σε μία απλά συνδεδεμένη Λίστα
Διαγραφή  ενός  κόμβου  από μία απλά συνδεδεμένη Λίστα

https://www.youtube.com/watch?v=j4h7qSVl8TY&t=459s&ab_channel=DimopoulosInformaticsTutorials

Στο δεύτερο αναφέρονται τα εξής:

Λίστες ΙΙ   - Διπλά Συνδεδεμένη Λίστα
Εισαγωγή ενός νέου κόμβου  σε μία απλά συνδεδεμένη Λίστα
Διαγραφή  ενός  κόμβου  από μία απλά συνδεδεμένη Λίστα
Διαφορές Πίνακα - Λίστας
Βασικές Λειτουργίες των συνδεδεμένων Λιστών
Αξιοποίηση Λίστας για την υλοποίηση Στοίβας και Ουράς
Διαφορές Λίστας - Στοίβας και Ουράς

https://www.youtube.com/watch?v=xpXgqPEm0-0&t=10s&ab_channel=DimopoulosInformaticsTutorials