Αποστολέας Θέμα: Απορια στις λιστες  (Αναγνώστηκε 1397 φορές)

computerscience

  • Οπαδός
  • **
  • Μηνύματα: 10
Απορια στις λιστες
« στις: 31 Ιαν 2020, 01:51:33 μμ »
Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3305
  • agent romanoff you miss me?
    • P.Tsiotakis
Απ: Απορια στις λιστες
« Απάντηση #1 στις: 31 Ιαν 2020, 02:38:18 μμ »
Για κάθε κόμβο της λίστας απαιτούνται 2 θέσεις μνήμης για την απλά και 3 θέσεις για την διπλά συνδεδεμένη λίστα, σε σχέση με τον πίνακα που απαιτείται 1.
Είναι περισσότερες οι θέσεις μνήμης.

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

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2313
Απ: Απορια στις λιστες
« Απάντηση #2 στις: 31 Ιαν 2020, 02:39:00 μμ »
Και οι πίνακες και οι λίστες δεσμεύουν μνήμη, αλλά σκέψου ότι ο πίνακας αποθηκεύει μόνο τα δεδομένα και η λίστα και τους δείκτες κάθε επόμενου κόμβου
Είτε στατικά, είτε δυναμικά, οι λίστες δεσμεύουν σχεδόν διπλάσια μνήμη από τον πίνακα
Κι αυτό για απλά συνδεδεμένη λίστα
Η διπλά συνδεδεμένη, απαιτεί σχεδόν τριπλάσια μνήμη
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

tdrivas

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 657
  • κάποτε έκαιγαν βιβλία,τώρα καίνε μυαλά...
Απ: Απορια στις λιστες
« Απάντηση #3 στις: 31 Ιαν 2020, 04:50:12 μμ »
Στα μειονεκτηματα των λιστων αναφερει οτι οι λιστες εχουν μεγαλυτερη επιβαρυνση απο τους πινακες αφου οι κομβοι ειναι δυναμικα κατανεμημενοι...κτλ
Δεν ειναι λιγο οξυμωρο μιας κ μειονεκτηματα των πινακων ειναι οτι δεσμευουν μνημη.. το οτι οι λιστες εχουν δυναμικο μεγεθος ειναι ενα απο τα πλεονεκτηματα τους..

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

Στην αντίπερα όχθη, στον πίνακα 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

computerscience

  • Οπαδός
  • **
  • Μηνύματα: 10
Απ: Απορια στις λιστες
« Απάντηση #4 στις: 01 Φεβ 2020, 12:16:53 πμ »
Ναι ευχαριστω πολυ ολους

ΔΗΜΗΤΡΗΣ Χ

  • Βετεράνος
  • ****
  • Μηνύματα: 69
Απ: Απορια στις λιστες
« Απάντηση #5 στις: 01 Φεβ 2020, 12:40:19 πμ »
Το οτι αναφερεται ως μειονεκτημα των πινακων μεσα στο σχολικο βιβλιο το γεγονος οτι απαιτουν μνημη, δεν εχει να κανει σε συγκριση με τις λιστες αλλα σε συγκριση με τη μη χρησιμοποιηση τους οταν αυτο δεν απαιτειται. Για παραδειγμα διαβασε  1000 αριθμους και βγαλε μεσο ορο. Χωρις πινακα θες 4 θεσεις (λαμβανοντας υπ οψιν χονδρικα βεβαια καθε μεταβλητη ως μια θεση) ενω με πινακα θες 1003.
Εκει εστιαζεται νομιζω.
 θα συμφωνησω συναδελφε οτι ειναι ενα απο τα πολλα διφορουμενα σημεια στο μαθημα και ειδικα με τη νεα υλη, και δυστυχως ειναι φυσιολογικο οταν υπαρχουν 4 βιβλια για ενα μαθημα.

ΔΗΜΗΤΡΗΣ Χ

  • Βετεράνος
  • ****
  • Μηνύματα: 69
Απ: Απορια στις λιστες
« Απάντηση #6 στις: 01 Φεβ 2020, 01:04:27 πμ »
Και βεβαια ισχυουν και ολα οσα γραφτηκαν για την "ασκοπη χρηση μεγαλων πινακων" και  απο τους 2 συναδελφους πριν, σε σχεση με τις λιστες με πολυ ευστοχα παραδειγματα.
Απλα κανω την προηγουμενη αναφορα για αυτο που λεει στο 9ο κεφαλαιο, γιατι νομιζω στο συγκεκριμενο σημειο ο συγγραφεας αναφερεται στη χρηση η οχι πινακα.

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 836
Απ: Απορια στις λιστες
« Απάντηση #7 στις: 01 Φεβ 2020, 07:35:29 πμ »
Στις δυναμικές δομές πρέπει να δαπανήσεις μία ή περισσότερες θέσεις μνήμης για να γνωρίζει ο κάθε κόμβος ποια θέση μνήμης είναι το αδερφάκι του.

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

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

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

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

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

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

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Απορια στις λιστες
« Απάντηση #8 στις: 01 Φεβ 2020, 11:28:36 πμ »
Ειδικά από τη στιγμή που η μνήμη φαίνεται με "συμβολικό" τρόπο, χωρίς λεπτομέρειες και απόλυτη ακρίβεια, δεν βλέπω το πρόβλημα. Θα μπορούσες. Όπως θα μπορούσε να κρατήσεις άλλο χρώμα για τις δεσμεύσεις δεικτών και δεδομένων. Έτσι θα φαινόταν ότι για την ίδια επιβάρυνση μνήμης, η λίστα θα έχει λιγότερες διαθέσιμες θέσεις για δεδομένα, από έναν πίνακα.

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

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1430
  • There are always possibilities...
Απ: Απορια στις λιστες
« Απάντηση #9 στις: 01 Φεβ 2020, 11:57:16 πμ »
Η αναπαράσταση μνήμης του Δρίβα είναι όμοια με αυτή που χρησιμοποιώ και εγώ, και νομίζω βοηθάει πολύ τα παιδιά να κατανοήσουν τι πρέπει να γράφουν στον κώδικα αντίστοιχα, για να δουλεύει σωστά ο αλγόριθμός τους. Είναι ένα σημείο που κάλλιστα θα μπορούσε να συμπεριληφθεί στο (νέο) βιβλίο μαθητή. Αν και εκ πρώτης όψεως, φαίνεται too much, και επικίνδυνα "κομπιουτερίστικο", στη πραγματικότητα, τέτοιες προσεγγίσεις είναι που δημιουργούν την απαραίτητη σύνδεση θεωρίας ("πότε πρέπει να χρησιμοποιούνται οι πίνακες"), με την πράξη. Σε κάθε κεφάλαιο που βλέπω ότι προσφέρεται, κάνω τέτοιες αναφορές με σχέδιο.

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

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

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 247
Απ: Απορια στις λιστες
« Απάντηση #10 στις: 01 Φεβ 2020, 01:03:48 μμ »
Παρεμβαίνω λίγο στο θέμα για ένα άσχετο σχόλιο με αφορμή την αναπαράσταση μνήμης, όχι μόνο στο συγκεκριμένο θέμα αλλά και στο βιβλίο (σελ. 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

  • Θαμώνας
  • ***
  • Μηνύματα: 45
  • you know what... i'm happy
Απορια στις λιστες
« Απάντηση #11 στις: 02 Φεβ 2020, 12:05:06 πμ »
Kαλησπέρα,

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

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

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

Ευχαριστώ.


evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3530
  • to Iterate is human to Recurse divine
Απ: Απορια στις λιστες
« Απάντηση #12 στις: 02 Φεβ 2020, 09:42:10 πμ »
Μάλλον εννοεί τον κόμβο που έγινε 3ος μετά την εισαγωγή του καινούργιου.
Νομίζω είναι η μόνη πιθανή εξήγηση.

Kαλησπέρα,

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

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

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

Ευχαριστώ.


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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3530
  • to Iterate is human to Recurse divine
Απ: Απορια στις λιστες
« Απάντηση #13 στις: 02 Φεβ 2020, 09:51:17 πμ »
Σχετικά με το αρχικό ερώτημα δε νομίζω ότι το βασικό πρόβλημα είναι η επιπλέον μνήμη που δεσμεύουν οι κόμβοι της λίστας (είναι και αυτό αλλά όχι το πρωτεύον).
Συγκεκριμένα λέει:
Παράθεση
Οι συνδεδεμένες λίστες έχουν πολύ μεγαλύτερη επιβάρυνση από τους πίνακες, αφού οι συνδεδεμένοι κόμβοι της λίστας είναι δυναμικά κατανεμημένοι (οι οποίοι είναι λιγότερο αποτελεσματικοί στη χρήση της μνήμης)

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

Αυτή είναι η δική μου ερμηνεία
« Τελευταία τροποποίηση: 02 Φεβ 2020, 11:29:36 πμ από evry »
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

droopy

  • Θαμώνας
  • ***
  • Μηνύματα: 45
  • you know what... i'm happy
Απ: Απορια στις λιστες
« Απάντηση #14 στις: 03 Φεβ 2020, 09:10:38 πμ »
Μάλλον εννοεί τον κόμβο που έγινε 3ος μετά την εισαγωγή του καινούργιου.
Νομίζω είναι η μόνη πιθανή εξήγηση.


Καλημέρα,

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