>> DAVID Malan: Εντάξει.
Είμαστε πίσω.
Έτσι, σε αυτό το τμήμα σχετικά με τον προγραμματισμό τι Σκέφτηκα ότι θα κάνουμε είναι ένας συνδυασμός πραγμάτων.
Ένα, κάνετε λίγη κάτι hands-on,
αν και χρησιμοποιώντας μια πιο παιχνιδιάρικη environment-- προγραμματισμού
ένα που είναι εκδηλωτικός του ακριβώς τα είδη των ιδεών
έχουμε μιλήσει για, αλλά λίγο πιο επίσημα.
Δύο, να δούμε μερικά από τα οι περισσότερες τεχνικές τρόπους
ότι ένας προγραμματιστής θα λύσει πραγματικά προβλήματα, όπως η αναζήτηση πρόβλημα
ότι εξετάσαμε πριν και Επίσης, μια πιο ριζικά
ενδιαφέρον πρόβλημα της διαλογής.
>> Εμείς μόλις ανέλαβε από το να πάει ότι το τηλεφωνικό ήταν ταξινομημένο,
αλλά αυτό από μόνο του είναι πραγματικά το είδος της μια δύσκολο πρόβλημα με πολλούς διαφορετικούς τρόπους
για την επίλυσή του.
Έτσι θα χρησιμοποιήσουμε αυτά ως μια κατηγορία προβλημάτων
εκπρόσωπος των πραγμάτων που θα μπορούσε να λυθεί σε γενικές γραμμές.
Και τότε θα μιλήσουμε σχετικά με κάποια λεπτομέρεια τι
καλούνται δεδομένα structures-- φανταχτερό τρόπους, όπως συνδεδεμένες λίστες
και οι πίνακες κατακερματισμού και δέντρα που ένας προγραμματιστής θα είναι στην πραγματικότητα
χρησιμοποιήσει και χρησιμοποιούν γενικά σε έναν πίνακα για να ζωγραφίσει
μια εικόνα του τι αυτός ή αυτή οραματίζεται για την εφαρμογή
κάποιο κομμάτι του λογισμικού.
>> Έτσι, ας κάνουμε τα hands-on πρώτο τμήμα.
Έτσι απλά λερώσετε τα χέρια σας με μια περιβάλλον που ονομάζεται scratch.mit.edu.
Αυτό είναι ένα εργαλείο που χρησιμοποιούμε σε προπτυχιακό τάξη μας.
Ακόμα κι αν αυτό είναι σχεδιασμένο για τις ηλικίες 12 και πάνω,
το χρησιμοποιούμε για την δημιουργία μέρος αυτής της αρκετά ένα κομμάτι
δεδομένου ότι είναι ένα ωραίο, διασκεδαστικό γραφικό τρόπο μάθησης
ένα μικρό κάτι για τον προγραμματισμό.
Έτσι, το κεφάλι σε αυτό το URL, όπου μπορείτε Πρέπει να δείτε μια σελίδα αρκετά όπως αυτό,
και να προχωρήσει και κάντε κλικ Γίνετε μέλος Scratch στην πάνω δεξιά
και να επιλέξετε ένα όνομα χρήστη και ένα κωδικό και τελικά να πάρει τον εαυτό σας
μια account-- scratch.mit.edu.
Νόμιζα ότι είχα χρησιμοποιήσει αυτό ως ένα ευκαιρία πρώτα να το αποδείξει αυτό.
Ένα ερώτημα που τέθηκε κατά τη διάρκεια του διαλείμματος για ποιο κωδικό μοιάζει πραγματικά.
Και μιλούσαμε κατά τη διάρκεια του διαλείμματος για το C,
σε particular-- ιδιαίτερα ένα χαμηλότερο επίπεδο σε μια παλαιότερη γλώσσα.
Και εγώ απλά έκανα μια γρήγορη Αναζήτηση στο Google για να βρείτε τον κωδικό C
για δυαδική αναζήτηση, τον αλγόριθμο που θα χρησιμοποιείται για την αναζήτηση το βιβλίο του τηλεφώνου νωρίτερα.
Αυτό το συγκεκριμένο παράδειγμα, φυσικά, δεν αναζητήσετε ένα τηλεφωνικό κατάλογο.
Ψάχνει μόνο ένα σωρό αριθμούς στη μνήμη του υπολογιστή.
Αλλά αν θέλετε να πάρετε μόνο μια οπτική αίσθηση του τι ένα πραγματικό προγραμματισμό
γλώσσα μοιάζει, φαίνεται ένα μικρό κάτι σαν αυτό.
Γι 'αυτό είναι περίπου 20-plus, 30 ή έτσι γραμμές κώδικα,
αλλά η συνομιλία μας Ήταν έχοντας πάνω από διάλειμμα
ήταν για το πώς αυτή η πραγματικότητα παίρνει μεταμορφωθεί σε μηδενικά και μονάδες
και αν δεν μπορείτε απλά να επανέλθει ότι επεξεργαστεί και να πάει από μηδενικά και μονάδες
πίσω στον κώδικα.
>> Δυστυχώς, η διαδικασία Είναι τόσο μετασχηματιστική
ότι είναι πολύ πιο εύκολο στα λόγια παρά στην πράξη.
Πήγα μπροστά και στην πραγματικότητα αποδείχθηκε ότι το πρόγραμμα, δυαδική αναζήτηση,
σε μηδενικά και μονάδες μέσω ενός πρόγραμμα που ονομάζεται ο compiler ότι εγώ,
τυχαίνει να έχουμε εδώ δικαίωμα στο Mac μου.
Και αν κοιτάξετε στην οθόνη Εδώ, με ιδιαίτερη έμφαση
σε αυτά τα μεσαία έξι κίονες μόνο, θα δείτε μόνο μηδενικά και μονάδες.
Και αυτά είναι τα μηδενικά και αυτοί που συνθέτουν ακριβώς αυτό το πρόγραμμα αναζήτησης.
>> Και έτσι κάθε κομμάτι από πέντε κομμάτια, κάθε byte από μηδενικά και αυτοί εδώ,
αντιπροσωπεύουν κάποια εντολή τυπικά μέσα από έναν υπολογιστή.
Και στην πραγματικότητα, αν έχετε ακούσει το σύνθημα μάρκετινγκ «Intel Inside» - δηλαδή,
Φυσικά, απλά σημαίνει ότι έχετε ένα Intel CPU ή τον εγκέφαλο στο εσωτερικό του υπολογιστή.
Και τι σημαίνει αυτό ότι είναι μια CPU είναι ότι έχετε ένα σύνολο εντολών,
να το πω έτσι.
>> Κάθε CPU στον κόσμο, πολλοί από τους έκανε από την Intel αυτές τις μέρες,
αντιλαμβάνεται ένα πεπερασμένο αριθμός οδηγιών.
Και αυτές οι οδηγίες είναι τόσο χαμηλό επίπεδο ως προσθέσει αυτά τα δύο αριθμούς μαζί,
πολλαπλασιάσουμε αυτά τα δύο αριθμούς μαζί, μετακινήσετε αυτό το κομμάτι των δεδομένων από εδώ
εδώ στη μνήμη, εκτός από αυτό πληροφορίες από εδώ εδώ στη μνήμη,
και έτσι forth-- τόσο πολύ, πολύ χαμηλού επιπέδου, σχεδόν ηλεκτρονικών στοιχείων.
Αλλά με αυτά τα μαθηματικές λειτουργίες σε συνδυασμό
με ό, τι συζητήσαμε νωρίτερα, η αναπαράσταση των δεδομένων
ως μηδενικά και μονάδες, μπορεί να χτίζετε τα πάντα
ότι ένας υπολογιστής μπορεί να κάνει σήμερα, αν Είναι κειμένου, γραφικών, μουσικής,
ή αλλιώς.
>> Έτσι, αυτό είναι πολύ εύκολο να φτάσετε χάνεται στα ζιζάνια του γρήγορα.
Και υπάρχει πολλή συντακτική προκλήσεις
σύμφωνα με την οποία αν κάνετε το πιο απλό, χαζό των typos κανένας από το πρόγραμμα
θα λειτουργήσει απολύτως.
Και έτσι αντί να χρησιμοποιεί ένα γλώσσα όπως η C το πρωί,
Σκέφτηκα ότι θα ήταν πιο διασκεδαστικό να κάνουν πραγματικά
κάτι πιο οπτική, η οποία ενώ έχουν σχεδιαστεί για τα παιδιά
είναι πραγματικά μια τέλεια εκδήλωση ενός πραγματικού προγραμματισμού
language-- συμβαίνει ακριβώς να χρησιμοποιούν εικόνες αντί για κείμενο
να εκπροσωπεί αυτές τις ιδέες.
>> Έτσι, μόλις έχετε πράγματι λογαριασμό στο scratch.mit.edu,
κάντε κλικ στο κουμπί Δημιουργία Στην επάνω αριστερή πλευρά της ιστοσελίδας.
Και θα πρέπει να δείτε ένα περιβάλλον όπως το ένα είμαι έτοιμος να δείτε στην οθόνη μου
εδώ.
Και θα περάσετε λίγο λίγο χρόνο παίζοντας εδώ.
Ας δούμε αν μπορούμε, δεν μπορούμε όλοι να λύσει μερικά προβλήματα μαζί με τον ακόλουθο τρόπο.
>> Έτσι, αυτό που θα δείτε μέσα σε αυτό environment-- και στην πραγματικότητα απλά αφήστε
με παύση.
Είναι κανείς δεν είναι εδώ;
Όχι εδώ?
ΕΝΤΆΞΕΙ.
Έτσι, επιτρέψτε μου να επισημάνω μερικά χαρακτηριστικά αυτού του περιβάλλοντος.
>> Έτσι, στο επάνω αριστερό μέρος της οθόνης, εμείς έχουν στάδιο Scratch, ώστε να μιλήσουν.
Scratch δεν είναι μόνο το όνομα αυτής της γλώσσας προγραμματισμού?
είναι επίσης το όνομα του γάτα που μπορείτε να δείτε από προεπιλογή εκεί στην πορτοκαλί.
Είναι σε ένα στάδιο, έτσι σαν περιέγραψα
η χελώνα νωρίτερα ότι βρίσκονται σε ένα ορθογώνιο λευκό περιβάλλον του σκάφους.
κόσμο αυτή η γάτα έχει περιοριστεί εξ ολοκλήρου σε αυτό το ορθογώνιο επάνω στην κορυφή εκεί.
>> Εν τω μεταξύ, στη δεξιά πλευρά εδώ, είναι
απλά μια περιοχή σενάρια, ένα κενή πλάκα αν θέλετε.
Αυτό είναι όπου θα πάμε να γράψω τα προγράμματά μας σε μια στιγμή.
Και τα δομικά στοιχεία ότι θα χρησιμοποιήσετε για να γράψω αυτό program-- το παζλ
κομμάτια, αν είστε will-- εκείνους ακριβώς εδώ στη μέση,
και από όπου και αν κατηγοριοποιούνται με τη λειτουργικότητα.
Έτσι, για παράδειγμα, Πάω να πάει μπροστά και επιδεικνύουν τουλάχιστον μία από αυτές.
Πάω να προχωρήσει και κάντε κλικ η κατηγορία ελέγχου επάνω στην κορυφή.
>> Αυτές είναι λοιπόν οι κατηγορίες επάνω στην κορυφή.
Πάω να κάντε κλικ στην κατηγορία Ελέγχου.
Αντίθετα, Πάω να κάνετε κλικ στο Εκδηλώσεις κατηγορία, η ίδια η πρώτη επάνω στην κορυφή.
Και αν θέλετε να ακολουθήσετε μαζί ακόμα όπως κάνουμε αυτό, είστε πολύ ευπρόσδεκτοι να.
Πάω να κάνετε κλικ και να σύρετε αυτό πρώτο, "όταν κάνετε κλικ πράσινη σημαία."
Και τότε εγώ είμαι πρόκειται να το ρίξει λίγο περίπου στην κορυφή κενό πλάκες μου.
>> Και τι είναι ωραίο για το Ξυστό είναι ότι αυτό το κομμάτι του παζλ, όταν
συμπλέκονται με άλλα παζλ κομμάτια, πρόκειται να κάνει κυριολεκτικά
ό, τι αυτά τα κομμάτια του παζλ πει να κάνουμε.
Έτσι, για παράδειγμα, Scratch είναι σωστό τώρα στη μέση του κόσμου του.
Πάω να πάει μπροστά και να επιλέξετε Τώρα, ας πούμε, η κατηγορία κίνησης,
αν θέλετε να κάνετε τα τρόπο-- κατηγορία κίνησης.
Και τώρα παρατηρήσετε έχω ένα ολόκληρο μάτσο κομμάτια του παζλ εδώ
ότι, και πάλι, το είδος του κάνει ό, τι λένε.
Και Πάω να πάει μπροστά και να μεταφέρετε και πτώση το μπλοκ κίνηση ακριβώς εδώ.
>> Και παρατηρήσετε ότι μόλις φτάσετε κοντά στο κάτω μέρος της "πράσινης σημαίας
κλικ "κουμπί, ανακοίνωση πώς εμφανίζεται μια λευκή γραμμή,
σαν να είναι σχεδόν μαγνητική, θέλει να πάει εκεί.
Απλά ας πάει, και θα snap μαζί και τα σχήματα θα ταιριάζουν.
Και τώρα μπορείτε ίσως σχεδόν μαντέψει όπου θα πάμε με αυτό.
>> Αν κοιτάξετε στο στάδιο Scratch εδώ και να κοιτάξουμε προς την κορυφή του,
θα δείτε ένα κόκκινο φως, ένα να σταματήσει σημάδι, και μια πράσινη σημαία.
Και Πάω να πάει μπροστά και να παρακολουθήσουν screen-- μου
για μια στιγμή, αν μπορούσε.
Πάω να κάνετε κλικ στο πράσινη σημαία τώρα,
και μετακόμισε ό, τι φαίνεται να είναι 10 βήματα ή 10 εικονοστοιχεία, 10 κουκκίδες, στην οθόνη.
>> Και έτσι δεν είναι ότι συναρπαστικό, αλλά επιτρέψτε μου να προτείνω
χωρίς καν να διδάσκει αυτό, απλά χρησιμοποιώντας το δικό σας intuition-- let
Θέλω να προτείνω να καταλάβω πώς να κάνει Scratch με τα πόδια δεξιά από το στάδιο.
Τον έχουν κάνει τον τρόπο για τη δεξιά πλευρά της η οθόνη, σε όλη τη διαδρομή προς τα δεξιά.
Επιτρέψτε μου να σας δώσω μια στιγμή ή έτσι για να παλέψει με αυτό.
Μπορεί να θέλετε να ρίξετε μια ματιά σε άλλες κατηγορίες μπλοκ.
Εντάξει.
Έτσι απλά για να ανακεφαλαιώσουμε, όταν έχουμε η πράσινη σημαία κλικ εδώ
και να κινηθεί 10 βήματα είναι η μόνο εντολή, κάθε φορά που
κάντε κλικ στην πράσινη σημαία, τι συμβαίνει;
Λοιπόν, αυτό τρέχει το πρόγραμμά μου.
Έτσι θα μπορούσα να κάνω αυτό ίσως 10 φορές με το χέρι,
αλλά αυτό αισθάνεται λίγο bit hackish, να το πω έτσι,
σύμφωνα με την οποία δεν είμαι πραγματικά επίλυση του προβλήματος.
Είμαι απλώς προσπαθούν ξανά και ξανά και ξανά και ξανά
μέχρι που το είδος της λάθος επιτευχθεί η οδηγία
ότι έθεσε ως στόχο να επιτευχθεί νωρίτερα.
>> Αλλά γνωρίζουμε από μας pseudocode νωρίτερα ότι υπάρχει
η έννοια αυτή στον προγραμματισμό του looping, κάνει κάτι ξανά και ξανά.
Και έτσι είδα ότι ένα μάτσο σας επιτευχθεί για κομμάτι ποιο παζλ;
Επαναλάβετε μέχρι.
Έτσι θα μπορούσαμε να κάνουμε κάτι όπως επαναλάβετε μέχρι.
Και τι έκανες επαναλάβετε μέχρι ακριβώς;
>> ΕΝΤΆΞΕΙ.
Και επιτρέψτε μου να πάει με αυτό που είναι κάπως πιο απλό για μια στιγμή.
Επιτρέψτε μου να προχωρήσει και να το κάνουμε αυτό.
Παρατηρήστε ότι, όπως μπορεί να έχετε ανακαλύφθηκε κάτω από τον έλεγχο,
υπάρχει αυτή η επανάληψη μπλοκ, το οποίο δεν μοιάζει να είναι τόσο μεγάλο.
Δεν υπάρχει πολύ χώρο στο μεταξύ αυτών των δύο κίτρινες γραμμές.
Αλλά, όπως κάποιοι από εσάς μπορεί να έχετε παρατηρήσει, αν drag and drop,
Παρατηρήστε πώς μεγαλώνει για να γεμίσει το σχήμα.
>> Και μπορείτε ακόμη και να χώνω περισσότερο.
Είναι απλώς θα συνεχίσει να αυξάνεται, αν μπορείτε να μεταφέρετε και να αιωρούνται πάνω από αυτό.
Και δεν ξέρω τι είναι καλύτερα εδώ, οπότε ας
μένα τουλάχιστον επαναλάβει πέντε φορές, για παράδειγμα, και στη συνέχεια να επιστρέψετε στο στάδιο
και κάντε κλικ στο πράσινο σημαία.
Και τώρα παρατηρήσετε ότι δεν είναι αρκετά εκεί.
>> Τώρα κάποιοι από εσάς που προτείνονται, όπως Victoria ακριβώς έκανε, επαναλάβετε 10 φορές.
Και αυτό το κάνει σε γενικές γραμμές να τον πάρει σε όλη τη διαδρομή,
αλλά δεν θα υπάρξει μια πιο ισχυρή τρόπο από ό, τι αυθαίρετα υπολογίζοντας
πόσες κινήσεις να κάνει;
Τι θα μπορούσε να είναι μια καλύτερη μπλοκ από επαναλάβετε 10 φορές να είναι;
>> Ναι, οπότε γιατί να μην κάνουμε κάτι για πάντα;
Και τώρα επιτρέψτε μου να μετακινήσετε αυτό το κομμάτι του παζλ εκεί μέσα και να απαλλαγούμε από αυτό.
Τώρα παρατηρήσετε δεν κατηγορία όπου Scratch εκκινήσεις, πηγαίνει προς την άκρη.
Και ευτυχώς MIT, που κάνει Ξυστό, απλά
εξασφαλίζει ότι ποτέ δεν εξαφανίζεται εντελώς.
Μπορείτε πάντα να αρπάξει την ουρά του.
>> Και μόνο διαισθητικά, γιατί αυτός να προχωρήσουμε;
Τι συμβαίνει εδώ;
Αυτός φαίνεται να έχουν σταματήσει, αλλά στη συνέχεια, αν έχω πάρει και σύρετε
κρατά θέλουν να πάνε εκεί.
Γιατί αυτό?
Πραγματικά, ένας υπολογιστής είναι κυριολεκτικά πρόκειται να κάνει ό, τι μπορείτε να πείτε για να το κάνει.
Έτσι, αν το είπε νωρίτερα να κάνει η ακόλουθα πράγμα για πάντα, κινούνται 10 βήματα,
πρόκειται να συνεχίσω και να πηγαίνει μέχρι να χτυπήσει το κόκκινο σήμα στοπ
και να σταματήσει το πρόγραμμα συνολικά.
>> Έτσι, ακόμη και αν δεν το έκανε να το κάνετε αυτό, πώς θα μπορούσα να
κάνει Scratch κινηθεί γρηγορότερα σε όλη την οθόνη;
Περισσότερα βήματα, έτσι δεν είναι;
Έτσι, αντί να κάνει 10 σε μια στιγμή, γιατί να μην το κάνουμε εμείς
να προχωρήσει και να αλλάξει το to-- τι θα propose-- 50;
Έτσι τώρα θα πάω να κάνετε κλικ στο πράσινο σημαία, και μάλιστα, πηγαίνει πολύ γρήγορα.
>> Και αυτό, φυσικά, είναι ακριβώς μια εκδήλωση του animation.
Τι είναι το animation;
Είναι απλά σας δείχνει τον άνθρωπο ένα σωρό εικόνες ακόμα πολύ,
πραγματικά, πραγματικά γρήγορα.
Και έτσι, αν είμαστε ακριβώς λέει αυτόν να κινηθεί περισσότερα βήματα,
είμαστε απλά έχοντας το αποτέλεσμα είναι να αλλαγής, όπου είναι επί της οθόνης
όλα τα πιο γρήγορα ανά μονάδα χρόνου.
>> Τώρα, η επόμενη πρόκληση που πρότεινα ήταν να τον αναπήδηση από την άκρη.
Και χωρίς να γνωρίζει ποιο παζλ κομμάτια exist-- γιατί είναι μια χαρά
αν δεν έχετε να το στάδιο της challenge-- τι
θέλετε να κάνετε διαισθητικά;
Πώς θα έχουμε τον αναπηδήσει πίσω και εμπρός, ανάμεσα στο αριστερό και το δεξί;
>> Ναι.
Έτσι, χρειαζόμαστε κάποιου είδους της κατάστασης, και
φαίνεται να έχουν υποθετικοί, έτσι ώστε να μιλούν, κάτω από την κατηγορία ελέγχου.
Ποια από αυτά τα τμήματα εμείς μάλλον θα θέλετε;
Ναι, ίσως "αν, τότε."
Έτσι, παρατηρούμε ότι ανάμεσα στα κίτρινα τετράγωνα έχουμε εδώ, υπάρχει αυτό το "αν"
ή αυτό το «εάν, αλλιώς" μπλοκ που θα μας επιτρέπουν να λάβει μια απόφαση για να γίνει αυτό
ή να το κάνουμε αυτό.
Και μπορείτε ακόμη και να τους φωλιά να κάνει πολλαπλές πράγματα.
Ή αν δεν έχετε πάει εδώ ακόμα, προχωρήστε στην κατηγορία Sensing
and-- ας δούμε αν είναι εδώ.
>> Λοιπόν, τι μπλοκ μπορεί να είναι χρήσιμη εδώ να ανιχνεύσει αν είναι από τη σκηνή;
Ναι, παρατηρήσετε ότι μερικά από αυτά τα μπλοκ μπορεί να παραμετροποιημένη, να το πω έτσι.
Μπορούν να είδος προσαρμοστεί, δεν σε αντίθεση με HTML χθες με χαρακτηριστικά,
όπου αυτά τα χαρακτηριστικά του είδους προσαρμόσετε τη συμπεριφορά μιας ετικέτας.
Ομοίως εδώ, μπορώ να αρπάξει αυτό το συγκινητικό μπλοκ και την αλλαγή και να θέσουμε το ερώτημα,
Σας αγγίζουν το ποντίκι δείκτη, όπως το δρομέα
ή μπορείτε να αγγίξετε την άκρη;
>> Έτσι, επιτρέψτε μου να πάω και να το κάνουμε αυτό.
Πάω για σμίκρυνση για μια στιγμή.
Επιτρέψτε μου να αρπάξει αυτό το κομμάτι του παζλ Εδώ, αυτό το παζλ κομμάτι αυτό,
και Πάω να συνονθύλευμα τους επάνω για μια στιγμή.
Πάω να μετακινήσετε αυτό, αλλάξετε αυτό σε συγκινητικό άκρη,
και θα πάω στην κίνηση το κάνουμε αυτό.
Έτσι, εδώ είναι μερικά συστατικά.
Νομίζω ότι έχω όλα όσα θέλω.
>> Κάποιος θα ήθελα να προτείνω το πώς θα μπορούν να συνδεθούν αυτά ίσως πάνω προς τα κάτω
προκειμένου να επιλυθεί το πρόβλημα της Scratch κίνηση δεξιά προς τα αριστερά προς τα δεξιά για να
αριστερά προς τα δεξιά προς τα αριστερά, το καθένα χρόνο ακριβώς αναπηδούν από τον τοίχο;
Τι θέλω να κάνω;
Ποια μπλοκ θα πρέπει να συνδεθεί με το "Όταν πράσινη σημαία κλικ πρώτα";
>> ΟΚ, οπότε ας αρχίσουμε με το "για πάντα".
Τι συμβαίνει στο εσωτερικό το επόμενο βήμα;
Κάποιος άλλος.
ΟΚ, μετακινηθείτε βήματα.
Εντάξει.
Τότε τι?
Έτσι, τότε η περίπτωση.
Και παρατηρήσετε, ακόμα κι αν φαίνεται στριμώχνεται μαζί σφιχτά,
θα αυξηθεί απλά για να γεμίσει.
Θα πηδήσει ακριβώς εκεί που θέλω.
>> Και τι μπορώ να τοποθετήσω μεταξύ το εάν και τότε;
Πιθανώς "αν αγγίξετε άκρη."
Και ειδοποίηση, και πάλι, αυτό είναι πάρα πολύ μεγάλο για αυτό, αλλά θα αυξηθεί για να γεμίσει.
Και στη συνέχεια ενεργοποιήστε 15 μοίρες;
Πόσοι βαθμοί?
Ναι, έτσι 180 θα περιστρέψει Θέλω όλος ο τρόπος γύρω.
Έτσι, ας δούμε αν έχω αυτό το δικαίωμα.
Επιτρέψτε μου σμίκρυνση.
>> Επιτρέψτε μου να σύρετε Scratch επάνω.
Έτσι, αυτός είναι λίγο διαστρεβλωμένη τώρα, αλλά αυτό είναι εντάξει.
Πώς μπορώ να τον επαναφέρετε εύκολα;
Πάω να εξαπατήσει λίγο.
Έτσι είμαι προσθέτοντας άλλο μπλοκ, ακριβώς για να είναι σαφής.
Θέλω να επισημάνω 90 μοίρες προς τα δεξιά, από προεπιλογή,
έτσι είμαι απλώς πρόκειται να του πω να το κάνουμε αυτό μέσω προγραμματισμού.
Και πάμε.
Εμείς φαίνεται να το έχουν κάνει.
Είναι λίγο περίεργο, γιατί αυτός είναι το περπάτημα ανάποδα.
Ας το ονομάσουμε ότι ένα bug.
Αυτό είναι ένα λάθος.
Ένα bug είναι ένα λάθος σε ένα πρόγραμμα, ένα λογικό λάθος που εγώ, ο άνθρωπος, έκανε.
Γιατί είναι αυτός που θα ανάποδα;
Μήπως MIT βίδα πάνω ή προς τα έκανα;
>> Ναι, θέλω να πω, δεν είναι του MIT σφάλμα. Μου έδωσαν ένα κομμάτι του παζλ
που λέει μετατρέψει κάποιο αριθμό των βαθμών.
Και μετά από πρόταση της Βικτώριας, Είμαι στροφή 180 μοιρών,
η οποία είναι η σωστή διαίσθηση.
Αλλά η στροφή 180 μοιρών στην κυριολεξία σημαίνει στροφή 180 μοιρών,
και αυτό δεν είναι πραγματικά ό, τι θέλω, προφανώς.
Επειδή τουλάχιστον αυτός είναι σε Αυτό δισδιάστατο κόσμο,
έτσι καμπής πραγματικά συμβαίνει να τον αναστρέψετε ανάποδα.
>> Μάλλον θέλετε να χρησιμοποιήσετε ό, τι μπλοκ Αντ 'αυτού, με βάση αυτά που βλέπετε εδώ;
Πώς μπορούμε να το διορθώσω αυτό;
Ναι, έτσι θα μπορούσαμε να επισημάνω προς την αντίθετη κατεύθυνση.
Και στην πραγματικότητα, ακόμη και αυτό είναι δεν πρόκειται να είναι αρκετή,
γιατί μπορούμε μόνο σκληρή κώδικα να δείχνει προς τα αριστερά ή προς τα δεξιά.
>> Ξέρεις τι θα μπορούσαμε να κάνουμε;
Φαίνεται σαν να έχουμε ένα μπλοκ ευκολία εδώ.
Αν μου μεγέθυνση, δείτε κάτι που μας αρέσει εδώ;
Ώστε να μοιάζει με το MIT έχει μια αφαίρεση χτίστηκε εδώ.
Αυτό το μπλοκ φαίνεται να είναι ισοδύναμες στην οποία άλλα μπλοκ, πληθυντικό;
>> Αυτό και μόνο το μπλοκ φαίνεται να είναι ισοδύναμες σε όλο αυτό το τρίο των μπλοκ
ότι έχουμε εδώ.
Έτσι αποδεικνύεται μπορώ να απλοποιήσει μου πρόγραμμα με το να απαλλαγούμε από όλα αυτά
και απλά βάλτε αυτό εδώ.
Και τώρα είναι ακόμα λίγο λάθη, και αυτό είναι μια χαρά για τώρα.
Θα το αφήσουμε να είναι.
Αλλά το πρόγραμμά μου είναι ακόμα απλούστερη, και αυτό, επίσης,
θα είναι αντιπροσωπευτικό από ένα γκολ σε programming--
είναι να κάνει ιδανικά κωδικό σας απλή, συμπαγής όσο είναι δυνατόν,
ενώ εξακολουθούν να είναι όσο αναγνώσιμη δυνατό.
Δεν θέλετε να το κάνετε τόσο συνοπτική ότι είναι δύσκολο να κατανοηθεί.
>> Αλλά παρατηρήσετε έχω αντικαθίστανται τρία τετράγωνα με ένα,
και αυτό είναι αναμφισβήτητα ένα καλό πράγμα.
Έχω αντλείται μακριά την έννοια να ελέγχεται εάν είστε
στην άκρη με μόλις ένα τετράγωνο.
Τώρα μπορούμε να διασκεδάσουν με αυτό, στην πραγματικότητα.
Αυτό δεν προσθέτουν τόσο πολύ πνευματική αξία, αλλά παιχνιδιάρικο αξία.
Πάω να πάει μπροστά και πιάσε αυτόν τον ήχο εδώ.
Έτσι, επιτρέψτε μου να πάει μπροστά, και επιτρέψτε μου να να σταματήσει το πρόγραμμα για μια στιγμή.
Πάω να καταγράψει τα ακόλουθα, επιτρέποντας την πρόσβαση στο μικρόφωνό μου.
>> Ορίστε.
Ωχ.
Ας δοκιμάσουμε αυτό και πάλι.
Ορίστε.
Εντάξει, καταγράφεται το λάθος πράγμα.
Ορίστε.
Ωχ.
Εντάξει.
Τώρα πρέπει να απαλλαγούμε από αυτό.
Εντάξει.
>> Έτσι, τώρα έχω ένα καταγραφή απλά "ωχ".
Έτσι τώρα είμαι πρόκειται να πάει μπροστά και να καλέσει αυτό το «ωχ».
Πάω να πάει πίσω σε σενάρια μου, και τώρα
προειδοποίηση υπάρχει αυτό το μπλοκ που ονομάζεται αναπαραγωγή ήχου "νιαούρισμα" ή αναπαραγωγή ήχου "ωχ".
Πάω να σύρετε αυτό, και όπου πρέπει να βάλω αυτό για κωμικό αποτέλεσμα;
Ναι, έτσι τώρα είναι το είδος της λάθη, γιατί τώρα αυτό block--
παρατηρήστε πώς αυτό το «αν στην άκρη, αναπήδηση "είναι το είδος της αυτόνομα.
Γι 'αυτό και πρέπει να το διορθώσω αυτό.
Επιτρέψτε μου να προχωρήσει και να το κάνουμε αυτό.
Επιτρέψτε μου να απαλλαγούμε από αυτό και να πάει πίσω στο αρχικό μας, πιο σκόπιμη
λειτουργικότητα.
Έτσι, "αν αγγίξετε άκρη, τότε« Θέλω να μετατρέψει, όπως προτείνεται Victoria,
180 μοίρες.
Και θέλω να παίξετε ο ήχος "ωχ" εκεί;
>> Ναι, παρατηρήσετε ότι είναι έξω ότι κίτρινο μπλοκ.
Έτσι, αυτό, επίσης, θα είναι ένα bug, αλλά το έχω παρατηρήσει.
Έτσι, Πάω να το σύρετε μέχρι εδώ, και προειδοποίηση τώρα είναι μέσα στο «αν».
Έτσι, το "αν" είναι αυτό το είδος σαν βραχίονας μοιάζει κηλίδα
ότι πρόκειται μόνο για κάνει ό, τι είναι μέσα από αυτό.
Έτσι τώρα, αν έχω σμίκρυνση σε ο κίνδυνος annoying--
>> COMPUTER: Ωχ, ωχ, ωχ.
>> DAVID Malan: Και θα πήγαινε για πάντα.
Τώρα απλά να επιταχύνει τα πράγματα Εδώ, επιτρέψτε μου να πάει μπροστά και να ανοίξει,
ας say-- επιτρέψτε μου να πάω σε κάποια της δικής μου πράγματα από την τάξη.
Και επιτρέψτε μου να ανοίξει, ας πούμε, αυτό το ένα που γίνεται από έναν από τη διδασκαλία τους συνανθρώπους μας
λίγα χρόνια πριν.
Έτσι, κάποιοι από εσάς μπορεί να υπενθυμίσει αυτό το παιχνίδι από το χτες,
και είναι πραγματικά αξιοσημείωτη.
Ακόμα κι αν έχουμε κάνει το απλούστερη των προγραμμάτων τώρα,
ας εξετάσουμε τι αυτό πραγματικά μοιάζει.
Επιτρέψτε μου να χτυπήσει το παιχνίδι.
>> Έτσι, σε αυτό το παιχνίδι, έχουμε ένα βάτραχος, και χρησιμοποιώντας το βέλος keys--
παίρνει μεγαλύτερα βήματα από ό, τι remember-- Έχω τον έλεγχο αυτού του βατράχου.
Και ο στόχος είναι να μεταδώσουμε την πολυάσχολη δρόμο χωρίς να τρέχει στα αυτοκίνητα.
Και ας see-- αν πάω μέχρι εδώ, πρέπει να περιμένετε για ένα ημερολόγιο για να μετακινηθείτε από.
Αυτό αισθάνεται σαν ένα bug.
Αυτό είναι το είδος του σφάλματος.
Εντάξει.
Είμαι σε αυτό εδώ, εκεί, και στη συνέχεια να σας κρατήσει
πρόκειται μέχρι να πάρετε όλα οι βάτραχοι στα μαξιλάρια κρίνων.
Τώρα αυτό μπορεί να μοιάζει όλο και πιο πολύπλοκες,
αλλά ας προσπαθήσουμε να σπάσει αυτό κάτω διανοητικά
και προφορικά σε όγκους που το απαρτίζουν.
Έτσι, υπάρχει πιθανώς ένα παζλ κομμάτι που δεν έχουμε δει ακόμα
αλλά αυτό είναι απάντηση σε πληκτρολογήσεις, για πράγματα που χτύπησε στο πληκτρολόγιο.
>> Έτσι, υπάρχει πιθανώς κάποιο είδος μπλοκ που λέει, όταν οι βασικές ισούται επάνω,
στη συνέχεια να κάνουμε κάτι με Scratch-- ίσως κινηθεί 10 βήματα με αυτόν τον τρόπο.
Αν κάτω πλήκτρο, μετακινήστε 10 βήματα Με αυτό τον τρόπο, ή αριστερό πλήκτρο, μετακινήστε 10 βήματα
Με αυτό τον τρόπο, 10 βήματα που.
Έχω μετατραπεί σαφώς τη γάτα σε ένα βάτραχο.
Έτσι, αυτό είναι ακριβώς όπου η φορεσιά, όπως κλήσεις Scratch it-- μας
μόλις εισαχθεί μια εικόνα του βατράχου.
>> Αλλά τι άλλο συμβαίνει;
Ποιες άλλες γραμμές κώδικα, τι άλλα κομμάτια του παζλ
έκανε Blake, τη διδασκαλία τους συναδέλφους μας, χρησιμοποιήσει σε αυτό το πρόγραμμα, προφανώς;
Τι κάνει τα πάντα move-- τι προγραμματισμού κατασκευάσει;
>> Κίνηση, σίγουρος, έτσι ώστε η μετακινήσετε μπλοκ, αυτό είναι σίγουρο.
Και τι είναι αυτό μπλοκ κίνηση εσωτερικό του, πιθανότατα;
Ναι, ένα είδος βρόχου, ίσως ένα πάντα μπλοκ, ίσως μια επανάληψη block--
επαναλάβετε μέχρι μπλοκ.
Και αυτό είναι που κάνει τα αρχεία καταγραφής και τα μαξιλάρια κρίνων και όλα τα άλλα κίνηση
εμπρός και πίσω.
Είναι ακριβώς συμβαίνει ασταμάτητα.
>> Γιατί είναι μερικά από τα αυτοκίνητα κινείται γρηγορότερα από τους άλλους;
Τι είναι διαφορετικό για αυτά τα προγράμματα;
Ναι, ίσως κάποιοι από αυτούς λαμβάνουν περισσότερα βήματα ταυτόχρονα και κάποια από αυτά
λιγότερα βήματα με τη μία.
Και το οπτικό αποτέλεσμα είναι γρήγορη σε σχέση με αργή.
>> Τι νομίζεις ότι συνέβη;
Όταν πήρα το βάτραχο μου σε όλη τη διαδρομή απέναντι από το δρόμο και το ποτάμι
πάνω στο μαξιλάρι κρίνων, κάτι αξιοσημείωτο συνέβη.
Τι συνέβη μόλις το έκανα αυτό;
Σταμάτησε.
Αυτό βάτραχος σταμάτησε, και Πήρα μια δεύτερη βάτραχο.
Λοιπόν, τι κατασκευή θα πρέπει να είναι που χρησιμοποιούνται εκεί, ποια η λειτουργία;
>> Ναι, έτσι υπάρχει κάποιο είδος "Αν" ρυθμίσει εκεί, πάρα πολύ.
Και αποδεικνύεται out-- δεν είδαμε this-- αλλά υπάρχουν και άλλα τμήματα εκεί που
μπορώ να πω, αν είστε συγκινητικό Ένα άλλο πράγμα που εμφανίζονται στην οθόνη,
αν είστε σε επαφή με το μαξιλάρι κρίνων, "τότε".
Και, στη συνέχεια, ότι όταν εμείς να εμφανιστεί η δεύτερη βάτραχος.
Έτσι, ακόμη κι αν αυτό το παιχνίδι είναι σίγουρα πολύ με ημερομηνία, παρόλο που με την πρώτη ματιά
υπάρχει τόσο πολύ να πάει on-- και Μπλέικ δεν μαστίγιο αυτό επάνω σε δύο λεπτά,
κατά πάσα πιθανότητα πήρε τον αρκετών ώρες για να δημιουργηθεί αυτό το παιχνίδι
βασίζονται σε μνήμη ή βίντεο του της έκδοσης χτες για αυτό.
Αλλά όλα αυτά τα μικρά πράγματα συμβαίνει στην οθόνη σε απομόνωση
συνοψίζεται σε αυτές τις πολύ απλές constructs-- κινήσεις ή δηλώσεις
όπως έχουμε συζητήσει, βρόχους και συνθήκες, και ότι είναι γι 'αυτό.
Υπάρχουν μερικά άλλα φανταχτερά χαρακτηριστικά.
Μερικά από αυτά είναι καθαρά αισθητική ή ακουστική,
όπως τους ήχους που μόλις έπαιξε με.
Αλλά για το μεγαλύτερο μέρος, θα έχουν σε αυτή τη γλώσσα, Ξυστό,
το σύνολο της θεμελιώδους δομικά στοιχεία που θα
έχουν σε C, Java, JavaScript, PHP, Ruby, Python,
και οποιοδήποτε αριθμό άλλων γλωσσών.
Οποιεσδήποτε ερωτήσεις σχετικά με το μηδέν;
Εντάξει.
Γι 'αυτό και δεν θα βουτήξει σε βαθύτερα στο Scratch, αν είστε ευπρόσδεκτοι αυτό το Σαββατοκύριακο,
ειδικά αν έχετε παιδιά ή ανίψια και τέτοια,
για την εισαγωγή τους στο Scratch.
Είναι πραγματικά μια θαυμάσια παιχνιδιάρικο περιβάλλον με, ως συντάκτες του λένε,
πολύ ψηλά ταβάνια.
Ακόμα κι αν ξεκινήσαμε με πολύ χαμηλού επιπέδου λεπτομέρειες,
μπορείτε να το κάνετε πραγματικά αρκετά ένα κομμάτι με αυτό, και αυτό είναι ίσως
μια επίδειξη ακριβώς αυτό.
>> Αλλά ας τώρα τη μετάβαση σε κάποιο πιο εξελιγμένα προβλήματα, αν θέλετε,
γνωστή ως "αναζήτηση" και «Διαλογή» γενικότερα.
Είχαμε αυτό το τηλέφωνο βιβλίο earlier-- εδώ ένα άλλο μόνο για discussion--
ότι ήμασταν σε θέση να αναζητήσετε πιο αποτελεσματικά, διότι
ενός σημαντικού υπόθεση.
Και ακριβώς για να είναι σαφές, τι παραδοχή ήμουν καθιστώντας
κατά την αναζήτηση μέσω αυτού του τηλεφώνου βιβλίο;
Ότι ο Mike Smith ήταν σε ο τηλεφωνικός κατάλογος, αν και
θα είναι σε θέση να χειριστεί το σενάριο χωρίς αυτόν
εκεί εάν σταμάτησα ακριβώς πρόωρα.
Το βιβλίο είναι αλφαβητική.
Και αυτό είναι ένα πολύ γενναιόδωρο υπόθεση, γιατί αυτό
σημαίνει someone-- είμαι το είδος κοπής σε μια γωνία,
σαν να είμαι πιο γρήγορα, επειδή κάποιος άλλος έκανε πολλή και σκληρή δουλειά για μένα.
>> Τι γίνεται όμως όταν το τηλέφωνο το βιβλίο ήταν άνευ διαλογής;
Ίσως Verizon πήρε τεμπέλης, απλά έριξε ονόματα και οι αριθμοί του καθενός εκεί
ίσως με τη σειρά με την οποία εγγραφεί για την τηλεφωνική υπηρεσία.
Και πόσο χρόνο χρειάζεται για να με πάρει να βρείτε κάποιον σαν τον Mike Smith;
1.000 τηλέφωνό σελίδα book-- πόσα σελίδες έχω να δούμε μέσα;
>> Ολα τους.
Είσαι το είδος του από την τύχη.
Μπορείτε κυριολεκτικά πρέπει να εξετάσουμε κάθε σελίδα, αν ο τηλεφωνικός κατάλογος είναι απλά
τυχαία διαλογή.
Μπορείτε να πάρετε τυχεροί και να βρείτε Mike από την πρώτη κιόλας σελίδα, γιατί
ήταν ο πρώτος πελάτης να διατάξει την τηλεφωνική υπηρεσία.
Αλλά θα μπορούσε να ήταν η τελευταία, πάρα πολύ.
>> Έτσι τυχαία σειρά δεν είναι καλή.
Έτσι, ας υποθέσουμε ότι έχουμε να λύσουμε το τηλεφωνικό κατάλογο ή σε γενικά δεδομένα ταξινόμησης
ότι έχουμε ήδη δοθεί.
Πώς μπορούμε να το κάνουμε αυτό;
>> Λοιπόν, επιτρέψτε μου να δοκιμάσετε ένα απλό παράδειγμα εδώ.
Επιτρέψτε μου να προχωρήσει και να πετάξει ένα μερικούς αριθμούς στον πίνακα.
Ας υποθέσουμε ότι οι αριθμοί που έχουμε είναι, ας πούμε, τέσσερις, δύο, ένα, και τα τρία.
Και, Ben, ταξινομήσετε αυτούς τους αριθμούς για εμάς.
>> Εντάξει, καλά.
Πώς το έκανες αυτό?
Εντάξει.
Έτσι, ξεκινούν με το μικρότερο αξία και η υψηλότερη,
και αυτό είναι πραγματικά καλή διαίσθηση.
Και να συνειδητοποιήσουμε ότι είμαστε οι άνθρωποι είναι στην πραγματικότητα αρκετά
καλή στην επίλυση των προβλημάτων όπως αυτό, τουλάχιστον
όταν τα δεδομένα είναι σχετικά μικρή.
Από τη στιγμή που θα αρχίσετε να έχετε εκατοντάδες των αριθμών, χιλιάδες αριθμούς,
τα εκατομμύρια των αριθμών, Ben πιθανώς Δεν μπορούσε να το κάνει αρκετά τόσο γρήγορα,
υποθέτοντας ότι υπήρχαν κενά στους αριθμούς.
Αρκετά εύκολο να μετρούν μέχρι το ένα εκατομμύριο Αλλιώς, απλά χρονοβόρα.
>> Έτσι, ο αλγόριθμος ακούγεται όπως ο Ben χρησιμοποιείται μόλις τώρα
ήταν αναζήτηση για το μικρότερο αριθμό.
Έτσι ακόμα κι αν εμείς οι άνθρωποι μπορούν να λάβουν σε πολλές πληροφορίες οπτικά,
ένας υπολογιστής είναι στην πραγματικότητα λίγο πιο περιορισμένη.
Ο υπολογιστής μπορεί μόνο εξετάσουμε ένα byte σε μια στιγμή
ή ίσως τέσσερα bytes σε time-- αυτές τις μέρες ίσως 8 bytes σε time--
αλλά ένας πολύ μικρός αριθμός από bytes σε μια δεδομένη στιγμή.
>> Έτσι, δεδομένου ότι έχουμε πραγματικά τέσσερις ξεχωριστές τιμές here--
και μπορείτε να σκεφτείτε Ben ως έχουσα παρωπίδες αν ήταν ένας υπολογιστής όπως
ότι δεν μπορεί να δει τίποτα άλλο από έναν αριθμό σε ένα time--
έτσι γενικά θα αναλάβει, όπως και σε Αγγλικά, θα διαβάζονται από τα δεξιά προς τα αριστερά.
Έτσι, ο πρώτος αριθμός Ben πιθανότατα κοίταξε σε ήταν τέσσερα και στη συνέχεια πολύ γρήγορα
συνειδητοποίησα ότι είναι ένα αρκετά μεγάλο number-- επιτρέψτε μου να συνεχίσετε να ψάχνετε.
>> Υπάρχουν δύο.
Περίμενε ένα λεπτό.
Δύο είναι μικρότερο από τέσσερα.
Πάω να θυμόμαστε.
Δύο είναι τώρα το μικρότερο.
Τώρα ένα-- που είναι ακόμα καλύτερη.
Αυτό είναι ακόμη μικρότερο.
Πάω να ξεχάσουμε δύο και απλά να θυμάστε ένα τώρα.
>> Και θα μπορούσε να σταματήσει να ψάχνει;
Καλά, αυτός θα μπορούσε να βασίζεται σε αυτές τις πληροφορίες,
αλλά είχε καλύτερη αναζήτηση το υπόλοιπο της λίστας.
Γιατί ό, τι και αν το μηδέν ήταν στη λίστα;
Τι θα συμβεί αν αρνητικό ήταν στη λίστα;
Ξέρει μόνο ότι η απάντησή του είναι σωστή, αν αυτός είναι εξαντλητικά
ελεγχθεί όλη τη λίστα.
Έτσι, θα εξετάσουμε το υπόλοιπο αυτού.
Τρία-- ότι ήταν χάσιμο χρόνου.
Πήρε άτυχος, αλλά ήμουν ακόμα σωστό να το πράξουν.
Και έτσι τώρα προφανώς επιλέγεται το μικρότερο αριθμό
και μόλις το θέσει στην αρχή της λίστας, όπως θα το κάνω εδώ.
Τώρα τι έκανες επόμενη, ακόμη και αν εσείς δεν το σκέφτομαι σχεδόν
σε αυτό το βαθμό;
Επαναλάβετε τη διαδικασία, έτσι κάποιο είδος βρόχου.
Υπάρχει μια γνωστή ιδέα.
Έτσι, εδώ είναι τέσσερις.
Αυτό είναι σήμερα το μικρότερο.
Αυτός είναι ένας υποψήφιος.
Όχι πια.
Τώρα που έχω δει δύο.
Αυτό είναι το επόμενο μικρότερο στοιχείο.
Τρία-- ότι δεν είναι μικρότερο, οπότε τώρα Ben μπορεί να κόβω το δύο.
>> Και τώρα μπορούμε να επαναλάβετε τη διαδικασία, και Φυσικά τριών παίρνει τράβηξε έξω την επόμενη.
Επαναλάβετε τη διαδικασία.
Τέσσερις παίρνει τράβηξε έξω.
Και τώρα είμαστε από τους αριθμούς, έτσι ώστε ο κατάλογος αυτός πρέπει να ταξινομηθούν.
>> Και πράγματι, αυτό είναι μια επίσημη αλγόριθμο.
Ένας επιστήμονας υπολογιστών θα καλέσετε αυτό το «είδος επιλογής,"
Η ιδέα είναι είδος μια λίστα iteratively-- και πάλι
και ξανά και ξανά, επιλέγοντας ο μικρότερος αριθμός.
Και τι είναι ωραίο γι 'αυτό είναι είναι ακριβώς έτσι καταριέται διαισθητική.
Είναι τόσο απλό.
Και μπορείτε να επαναλάβετε την ίδια λειτουργία ξανά και ξανά.
Είναι απλό.
>> Σε αυτή την περίπτωση ήταν γρήγορο, αλλά πόσο χρόνο χρειάζεται στην πραγματικότητα να λάβει;
Ας το κάνουμε να φαίνεται και αισθάνονται λίγο πιο κουραστικό.
Έτσι, ένα, δύο, τρία, τέσσερα, πέντε έξι, επτά, οκτώ, εννέα, 10, 11, 12, 13, 14,
15, 16-- αυθαίρετο αριθμό.
Απλά ήθελα περισσότερο αυτό χρόνο από ό, τι ακριβώς τους τέσσερις.
Έτσι, αν έχω ένα ολόκληρο δέσμη των αριθμών που now--
Δεν πειράζει ακόμη και τι are-- ας
σκεφτείτε τι είναι αυτό αλγόριθμος είναι πολύ παρόμοια.
>> Ας υποθέσουμε ότι υπάρχουν αριθμοί εκεί.
Και πάλι, δεν έχει σημασία τι είναι, αλλά είναι τυχαία.
Είμαι εφαρμόζοντας τον αλγόριθμο του Ben.
Θα πρέπει να επιλέξετε το μικρότερο αριθμό.
Τι κάνω?
Και Πάω να σωματικά το κάνει αυτή τη φορά για να ενεργήσει έξω.
Ψάχνουν, ψάχνουν, ψάχνουν, ψάχνουν, ψάχνουν.
Μόνο από τη στιγμή που έχω να το τέλος της λίστας μπορεί να
Αντιλαμβάνομαι το μικρότερο αριθμός ήταν δυο αυτή τη φορά.
Κάποιος δεν είναι στη λίστα.
Έτσι έβαλα κάτω δύο.
>> Τι μπορώ να κάνω το επόμενο βήμα;
Ψάχνουν, ψάχνουν, ψάχνουν, ψάχνουν.
Τώρα βρήκα τον αριθμό επτά, επειδή υπάρχει κενά σε αυτές τις numbers--
αλλά απλώς αυθαίρετη.
Εντάξει.
Έτσι τώρα μπορώ να βάλω κάτω επτά.
Κοιτάζοντας ψάχνουν, ψάχνουν.
>> Τώρα υποθέτω, της Φυσικά, ότι ο Ben δεν
έχουν επιπλέον μνήμη RAM, επιπλέον μνήμη, επειδή, φυσικά,
Ψάχνω στον ίδιο αριθμό.
Σίγουρα θα μπορούσα να είχα θυμήθηκε όλων αυτών των αριθμών,
και αυτό είναι απολύτως αληθές.
Αλλά αν ο Μπεν θυμάται όλα των αριθμών έχει δει,
δεν έχει κάνει πραγματικά θεμελιώδη πρόοδο
επειδή έχει ήδη η δυνατότητα να αναζητήσετε
μέσα από τους αριθμούς στον πίνακα.
Ενθυμούμενος όλα τα αριθμοί δεν βοηθά,
γιατί μπορεί ακόμα και έναν υπολογιστή μόνο να δούμε, έχουμε πει, έναν αριθμό
σε μια στιγμή.
Έτσι, δεν υπάρχει είδος cheat εκεί που μπορείτε να αξιοποιήσετε.
>> Έτσι, στην πραγματικότητα, όπως εγώ να συνεχιστεί η αναζήτηση του καταλόγου,
Έχω κυριολεκτικά πρέπει να συνεχίζουν να εργάζονται εμπρός και πίσω μέσα από αυτό, το μάδημα έξω
το επόμενο μικρότερο αριθμό.
Και όπως μπορείτε είδος μπορεί να συμπεράνει από ανόητες κινήσεις μου,
αυτό παίρνει απλά πολύ κουραστική πολύ γρήγορα,
και μου φαίνεται να πηγαίνει πίσω και εμπρός, εμπρός και πίσω αρκετά.
Τώρα για να είμαστε δίκαιοι, δεν έχω να πάω τόσο, καλά, ας see-- για να είμαστε δίκαιοι,
Δεν έχω να περπατήσει αρκετά όπως πολλά βήματα κάθε φορά.
Διότι, φυσικά, όπως επιλέξετε αριθμούς από τη λίστα,
το υπόλοιπο κατάλογος γίνεται όλο και μικρότερη.
>> Και έτσι ας σκεφτούμε πόσα βήματα Είμαι πραγματικά
traipsing μέσα από κάθε φορά.
Στην πρώτη κατάσταση είχαμε 16 αριθμούς,
και έτσι maximally-- ας μόνο κάνετε αυτό για μια discussion--
Έπρεπε να δούμε μέσα από 16 αριθμούς για να βρει το μικρότερο.
Αλλά από τη στιγμή που ξεριζώθηκαν ο μικρότερος αριθμός, πώς
μακρύ ήταν το υπόλοιπο λίστα, φυσικά;
Μόλις 15.
Έτσι, πόσοι αριθμοί έκαναν Ben ή έχω να κοιτάξετε μέσα από την δεύτερη φορά γύρω;
15, ακριβώς για να πάει και να βρει το μικρότερο.
Αλλά τώρα, φυσικά, ο κατάλογος είναι, πάρα πολύ, μικρότερα από ό, τι ήταν πριν.
Έτσι, πόσα βήματα έκανα πρέπει να λάβει την επόμενη φορά;
14 και στη συνέχεια 13 και στη συνέχεια 12, συν τελεία, τελεία, τελεία, μέχρι να είμαι αριστερά με ένα μόνο.
Έτσι τώρα ένας επιστήμονας υπολογιστών θα ρωτήσω, καλά, τι κάνει ότι όλοι ίσοι;
Ισούται πραγματικά κάποια συγκεκριμένη αριθμός που θα μπορούσαμε σίγουρα
κάνουν αριθμητικά, αλλά θέλουμε να μιλήσουμε σχετικά με την αποτελεσματικότητα των αλγορίθμων
λίγο πιο formulaically, ανεξάρτητα από το πόσο καιρό η λίστα είναι.
>> Και έτσι ξέρετε τι;
Αυτό είναι 16, αλλά όπως είπα και πριν, ας καλέσει το μέγεθος του προβλήματος
n, όπου το η είναι κάποιος αριθμός.
Ίσως είναι 16, ίσως είναι τρία, ίσως είναι ένα εκατομμύριο.
Δεν γνωρίζω.
Δεν με νοιάζει.
Αυτό που θέλω πραγματικά είναι ένας τύπος που μπορώ
χρησιμοποιήσετε για να συγκρίνετε αυτόν τον αλγόριθμο έναντι άλλων αλγορίθμων
ότι κάποιος μπορεί να ισχυριστεί είναι καλύτερα ή χειρότερα.
>> Έτσι αποδεικνύεται, και μόνο εγώ το γνωρίζουν αυτό από το σχολείο βαθμού,
ότι αυτό λειτουργεί πραγματικά έξω στο ίδιο πράγμα όπως n πάνω από n συν ένα πάνω από δύο.
Και αυτό συμβαίνει να είναι ίση, της Φυσικά, n στο τετράγωνο συν ν πάνω από δύο.
Έτσι, αν ήθελα μια φόρμουλα για πόσα βήματα
συμμετείχαν στην εξέταση όλων αυτών των αριθμών ξανά και ξανά
και ξανά και ξανά, θα έλεγα αυτό είναι n στο τετράγωνο συν ν πάνω από δύο.
Αλλά ξέρετε τι;
Αυτό ακριβώς φαίνεται βρώμικο.
Απλά θέλω πραγματικά ένα γενική αίσθηση των πραγμάτων.
Και ίσως να θυμάστε από γυμνάσιο ότι υπάρχει
είναι η έννοια της υψηλότερης όρος τάξης.
Ποια από αυτούς τους όρους, η n τετράγωνο, το Ν, ή το μισό,
έχει το μεγαλύτερο αντίκτυπο την πάροδο του χρόνου;
Το μεγαλύτερο n παίρνει, η οποία αυτών των θεμάτων το πιο;
>> Με άλλα λόγια, αν συνδέω σε ένα εκατομμύριο, n τετράγωνο
πρόκειται να είναι πιο πιθανό ο κυρίαρχος παράγοντας,
ένα εκατομμύριο γιατί οι καιροί από μόνη της είναι πολύ μεγαλύτερο
από συν ένα επιπλέον εκατομμύριο.
Έτσι, ξέρετε τι;
Αυτό είναι μια τέτοια καταριέται μεγάλο αριθμός αν τακτοποιήσει έναν αριθμό.
Αυτό δεν πειράζει πραγματικά.
Εμείς απλά θα σταυρό που έξω και να ξεχάσουμε αυτό.
Και έτσι ένας επιστήμονας υπολογιστών θα έλεγα ότι η αποτελεσματικότητα αυτού του αλγορίθμου
είναι της τάξης του n squared-- Εννοώ πραγματικά μια προσέγγιση.
Είναι το είδος των περίπου n στο τετράγωνο.
Την πάροδο του χρόνου, το μεγαλύτερο και μεγαλύτερα n παίρνει, αυτό
είναι μια καλή εκτίμηση για το ποια είναι η απόδοση ή έλλειψη αποτελεσματικότητας
αυτού του αλγορίθμου είναι στην πραγματικότητα.
Και εγώ αντλούν αυτό, φυσικά, από πραγματικά να κάνει τα μαθηματικά.
Αλλά τώρα είμαι απλά κουνώντας τα χέρια μου, γιατί απλά
θέλουν μια γενική αίσθηση αυτού του αλγορίθμου.
>> Έτσι, χρησιμοποιώντας την ίδια λογική, εν τω μεταξύ, Ας εξετάσουμε ένα άλλο αλγόριθμο
έχουμε ήδη εξετάσει at-- γραμμική αναζήτηση.
Όταν έψαχνα για το τηλέφωνο book--
Δεν είναι η διαλογή, αναζήτηση μέσω του τηλεφώνου book--
θα έλεγε ότι ήταν 1000 βήματα, ή 500 βήματα.
Αλλά ας γενικεύσουμε αυτό.
Αν υπάρχει n σελίδες ο τηλεφωνικός κατάλογος, τι είναι
ο χρόνος εκτέλεσης ή της αποτελεσματικότητα της γραμμικής αναζήτησης;
Είναι της τάξης των πόσα βήματα για να βρείτε
Mike Smith με τη βοήθεια γραμμικής αναζήτησης, η πρώτο αλγόριθμο, ή ακόμη και η δεύτερη;
>> Στη χειρότερη περίπτωση, ο Mike βρίσκεται στο τέλος του βιβλίου.
Έτσι, αν το βιβλίο τηλέφωνο έχει 1.000 σελίδες, είπαμε την τελευταία φορά, στη χειρότερη περίπτωση,
μπορεί να πάρει περίπου πόσο πολλές σελίδες για να βρείτε Mike;
Όπως και 1.000.
Είναι ένα άνω φράγμα.
Είναι μια χειρότερη δυνατή κατάσταση.
Αλλά και πάλι, είμαστε κινείται μακριά από αριθμούς όπως 1.000 τώρα.
Είναι ακριβώς n.
>> Έτσι, αυτό είναι το λογικό συμπέρασμα;
Η εύρεση Mike σε ένα τηλέφωνο βιβλίο που έχει n σελίδες
θα μπορούσε να λάβει, σε πολύ χειρότερη περίπτωση, πόσα βήματα της τάξης του n;
Και πράγματι ένας υπολογιστής επιστήμονας θα έλεγε
ότι ο χρόνος τρέχει, ή η απόδοση ή την αποτελεσματικότητα
ή αναποτελεσματικότητα, ενός αλγορίθμου όπως μια γραμμική έρευνα είναι της τάξης του n.
Και μπορούμε να εφαρμόσουμε την ίδια λογική διέλευση κάτι
όπως έκανα ακριβώς στο δεύτερο αλγόριθμο που είχαμε με τον τηλεφωνικό κατάλογο,
όπου πήγαμε δύο σελίδες σε έναν χρόνο.
>> Έτσι 1,000 σελίδα τηλεφωνικός κατάλογος θα μπορούσε να μας πάρει 500 στροφές σελίδα, συν ένα
αν έχουμε διπλασιάσει πίσω λίγο.
Έτσι, αν ένας τηλεφωνικός κατάλογος έχει n σελίδες, αλλά κάνουμε δύο σελίδες σε έναν χρόνο,
αυτό είναι σχεδόν ό, τι;
Ν πάνω από δύο, έτσι ώστε να είναι σαν ν πάνω από δύο.
Αλλά έκανα το αίτημα ενός πριν από λίγο ότι n πάνω two--
αυτό είναι το είδος της το ίδιο ακριβώς n.
Είναι απλά ένα σταθερό συντελεστή, επιστήμονες υπολογιστών θα έλεγα.
Ας επικεντρωθεί μόνο σε οι μεταβλητές, really--
οι μεγαλύτερες μεταβλητές στην εξίσωση.
>> Έτσι γραμμική αναζήτηση, αν γίνει ένα σελίδα τη φορά ή δύο σελίδες σε έναν χρόνο,
είναι είδος ουσιαστικά το ίδιο.
Είναι ακόμα της τάξεως των n.
Αλλά εγώ ισχυρίστηκε με την εικόνα μου νωρίτερα ότι η τρίτη αλγόριθμος δεν ήταν
γραμμικός.
Δεν ήταν μια ευθεία γραμμή.
Ήταν ότι καμπύλη γραμμή, και ο τύπο αλγεβρικό εκεί ήταν αυτό;
Σύνδεση του n-- έτσι log βάση δύο από n.
Και δεν έχουμε να πάει σε πάρα πολλές λεπτομέρειες σχετικά με λογαρίθμους σήμερα,
αλλά οι περισσότεροι επιστήμονες της πληροφορικής δεν θα ακόμη και να σας πω ποια είναι η βάση είναι.
Επειδή είναι όλα απλά σταθερούς παράγοντες, να το πω έτσι,
μόνο μικρές αριθμητικές διαφορές.
Και έτσι αυτό θα είναι ένα πολύ κοινό τρόπος για ιδιαίτερα επίσημη υπολογιστή
επιστήμονες σε έναν πίνακα ή προγραμματιστές σε ένα λευκό του σκάφους
στην πραγματικότητα το επιχείρημα το οποίο αλγόριθμος που θα χρησιμοποιήσετε
ή ποια είναι η απόδοση του αλγορίθμου τους είναι.
>> Και αυτό δεν είναι κατ 'ανάγκη κάτι θα συζητήσουμε σε κάθε μεγάλη λεπτομέρεια,
αλλά ένας καλός προγραμματιστής είναι κάποιος ο οποίος έχει μια σταθερή, επίσημη φόντο.
Είναι σε θέση να μιλήσει με σας σε αυτό το είδος του τρόπου
και πραγματικά να κάνει ποιοτικά επιχειρήματα
γιατί ένα αλγόριθμο ή ένα κομμάτι του λογισμικού
είναι ανώτερη κατά κάποιο τρόπο σε μια άλλη.
Επειδή θα μπορούσατε σίγουρα απλά τρέξτε το πρόγραμμα ενός ατόμου
και μετρήστε τον αριθμό των δευτερολέπτων που χρειάζεται για να ταξινομήσετε κάποιους αριθμούς,
και μπορείτε να εκτελέσετε κάποια πρόγραμμα άλλου ατόμου
και μετρήστε τον αριθμό των δευτερολέπτων που χρειάζεται.
Αλλά αυτό είναι ένα γενικότερο τρόπο ότι μπορείτε να χρησιμοποιήσετε για να αναλύσει αλγορίθμων,
αν θέλετε, μόνο για χαρτί ή απλά προφορικά.
Χωρίς καν να τρέχει, χωρίς να ακόμη προσπαθούν εισόδους του δείγματος,
μπορείτε απλά να λόγο μέσα από αυτό.
Και έτσι με την πρόσληψη ενός προγραμματιστή ή αν που έχει το άτομό του είδους υποστηρίζουν για να σας
γιατί αλγόριθμο τους, το μυστικό τους σάλτσα για την αναζήτηση δισεκατομμύρια
των ιστοσελίδων για σας Η εταιρεία είναι καλύτερη, αυτά
είναι τα είδη των επιχειρημάτων που θα πρέπει ιδανικά να είναι σε θέση να κάνει.
Ή τουλάχιστον αυτά είναι τα είδη των πραγμάτων
ότι θα καταλήξει στη συζήτηση, σε τουλάχιστον σε μια πολύ τυπική συζήτηση.
Εντάξει.
Έτσι Μπεν πρότεινε κάτι ονομάζεται το είδος επιλογής.
Αλλά Πάω να προτείνω ότι υπάρχει άλλους τρόπους για να γίνει αυτό, πάρα πολύ.
Αυτό που δεν μου άρεσε πραγματικά σχετικά με τον αλγόριθμο του Ben
είναι ότι διατηρούνται τα πόδια, ή αφού με τα πόδια, και πίσω
και μπροστά και πίσω και εμπρός και πίσω.
Τι θα συμβεί αν αντί γι 'αυτό ήταν να κάνω κάτι σαν αυτούς τους αριθμούς εδώ
και εγώ έπρεπε να ασχολείται μόνο με το καθένα αριθμό με τη σειρά του, όπως είμαι δώσει;
>> Με άλλα λόγια, είναι εδώ λίστα μου αριθμών.
Τέσσερις, ένα, τρία, δύο.
Και Πάω να κάνω το εξής.
Πάω να εισάγετε τους αριθμούς όπου ανήκουν μάλλον
από την επιλογή τους, ένα κάθε φορά.
Με άλλα λόγια, εδώ είναι το νούμερο τέσσερα.
>> Εδώ είναι αρχική λίστα μου.
Και Πάω να διατηρήσουν ουσιαστικά μια νέα λίστα εδώ.
Έτσι, αυτό είναι το παλιό λίστα.
Αυτή είναι η νέα λίστα.
Βλέπω τον αριθμό τέσσερα πρώτα.
νέα λίστα μου είναι αρχικά κενή, έτσι είναι κοινότοπα συμβαίνει
ότι τέσσερις είναι τώρα ανάμικτες λίστα.
Είμαι απλά παίρνετε τον αριθμό Είμαι δοθεί, και είμαι το θέτει σε νέα λίστα μου.
>> Ταξινομείται αυτή η νέα λίστα;
Ναι.
Είναι ηλίθιο επειδή υπάρχει μόνο ένα στοιχείο, αλλά είναι απολύτως ταξινομημένο.
Δεν υπάρχει τίποτα εκτός τόπου.
Είναι πιο ενδιαφέρον, ο αλγόριθμος αυτός, όταν προχωρήσουμε στο επόμενο βήμα.
>> Τώρα έχω ένα.
Έτσι ένα, φυσικά, ανήκει κατά τη αρχή ή στο τέλος αυτής της νέας λίστας;
Η αρχη.
Έτσι έχω να κάνω κάποια δουλειά τώρα.
Έχω ήδη λάβει κάποια ελευθερίες με δείκτη μου
από απλά αντλώντας τα πράγματα όπου εγώ τους θέλω,
αλλά αυτό δεν είναι πραγματικά ακριβής σε έναν υπολογιστή.
Ένας υπολογιστής, όπως γνωρίζουμε, έχει RAM, ή μνήμη τυχαίας προσπέλασης,
και αυτό είναι ένα byte και ένα άλλο byte και ένα άλλο byte.
Και αν έχετε ένα gigabyte του RAM, έχετε ένα δισεκατομμύριο bytes,
αλλά είναι φυσικά σε μία θέση.
Μπορείτε όχι μόνο να κινηθούν τα πράγματα γύρω από τραβώντας το στην πλακέτα
όπου θέλεις.
Έτσι, εάν η νέα λίστα μου έχει τέσσερις θέσεις στη μνήμη,
Δυστυχώς, οι τέσσερις είναι ήδη σε λάθος μέρος.
>> Έτσι για να εισάγετε τον αριθμό ένα Δεν μπορώ απλά να επιστήσω εδώ.
Αυτή η θέση μνήμης δεν υπάρχει.
Αυτό θα ήταν εξαπάτηση, και έχω εξαπάτηση με εικόνες για λίγα λεπτά
εδώ.
Έτσι, πραγματικά, αν θέλετε να βάλετε ένα εδώ, Έχω να αντιγράψετε προσωρινά τα τέσσερα
και στη συνέχεια, τοποθετήστε το ένα εκεί.
>> Αυτό είναι εντάξει, αυτό είναι σωστό, αυτό είναι τεχνικώς εφικτό,
αλλά συνειδητοποιούν ότι η επιπλέον εργασία.
Δεν είχα απλά βάλτε τον αριθμό στη θέση του.
Θα έπρεπε πρώτα να μετακινήσετε ένα αριθμός, τότε θα τεθεί σε εφαρμογή,
γι 'αυτό το είδος της διπλασιάστηκε το ποσό της εργασίας μου.
Έτσι, να το έχουμε κατά νου.
>> Αλλά είμαι τώρα γίνει με αυτό το στοιχείο.
Τώρα θέλω να αρπάξει τον αριθμό τρία.
Όταν, βέβαια, δεν ανήκει;
Ανάμεσα.
Δεν μπορώ να εξαπατήσει πια και απλά να βάλει εκεί,
επειδή, και πάλι, αυτή τη μνήμη Είναι σε φυσικές τοποθεσίες.
Γι 'αυτό και πρέπει να αντιγράψετε τα τέσσερα και να θέσει τα τρία εδώ.
Δεν είναι μεγάλη υπόθεση.
Είναι απλά ένα επιπλέον βήμα again-- αισθάνεται πολύ φθηνή.
>> Αλλά τώρα μπορώ να προχωρήσουμε στο δύο.
Οι δύο, φυσικά, ανήκει εδώ.
Τώρα θα αρχίσετε να βλέπετε πώς η εργασία μπορεί να συσσωρεύονται.
Τώρα τι πρέπει να κάνω;
Ναι, έχω να μετακινήσετε το τέσσερα, Θα πρέπει στη συνέχεια να αντιγράψετε το τρία,
και τώρα μπορώ να τοποθετήσετε τα δύο.
Και τα αλιεύματα με αυτό αλγόριθμο, αρκετά ενδιαφέρον,
είναι ότι ας υποθέσουμε ότι έχουμε μια πιο ακραία περίπτωση που είναι ας πούμε οκτώ, επτά,
έξι, πέντε, τέσσερα, τρία, δύο, ένα.
Αυτό είναι, σε πολλές περιπτώσεις, το χειρότερο σενάριο,
γιατί το καταριέται το πράγμα είναι κυριολεκτικά προς τα πίσω.
>> Δεν έχει πραγματικά επηρεάσει τον αλγόριθμο του Ben,
γιατί στην επιλογή του Ben είδος που πρόκειται να κρατήσει
πηγαινοέρχονται μέσα στη λίστα.
Και επειδή ήταν πάντα ψάχνει όλη τη απομένει λίστα,
δεν έχει σημασία όπου τα στοιχεία είναι.
Αλλά σε αυτή την περίπτωση εισαγωγής μου approach-- ας προσπαθήσουμε αυτό.
>> Έτσι, ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά, οκτώ.
Ένα δύο τρία τέσσερα, πέντε, έξι, επτά, οκτώ.
Πάω να πάρει το οκτώ, και πού μπορώ να το πω;
Λοιπόν, στην αρχή της λίστας μου, επειδή αυτή η νέα λίστα είναι ταξινομημένο.
Και εγώ το σταυρό έξω.
>> Πού μπορώ να θέσει το επτά;
Να παρει η ευχη.
Πρέπει να πάμε εκεί, έτσι Έχω να κάνω κάποια αντιγραφή.
Και τώρα τα επτά πηγαίνει εδώ.
Τώρα μπορώ να προχωρήσουμε στο έξι.
Τώρα είναι ακόμη περισσότερη δουλειά.
>> Οκτώ πρέπει να πάτε εδώ.
Επτά πρέπει να πάτε εδώ.
Τώρα τα έξι μπορεί να πάει εδώ.
Τώρα πιάσε το πέντε.
Τώρα το οκτώ έχει να πάει Εδώ, επτά πρέπει να πάτε εδώ,
έξι πρέπει να πάει εδώ, και τώρα το πέντε και επαναλάβετε.
Και είμαι λίγο πολύ μετακινώντας το συνεχώς.
>> Έτσι, στο τέλος, αυτό algorithm-- εμείς θα αποκαλούν εισαγωγή sort-- πραγματικότητα
έχει πολλή δουλειά, πάρα πολύ.
Είναι απλά διαφορετικό το είδος της εργασίας από ό, τι του Ben.
το έργο του Ben μου είχε πηγαίνει εμπρός και πίσω όλη την ώρα,
επιλέγοντας το αμέσως μικρότερο στοιχείο ξανά και ξανά.
Έτσι, ήταν αυτό το πολύ οπτική είδος της εργασίας.
>> Αυτό το άλλο αλγόριθμο, η οποία εξακολουθεί να είναι correct-- θα πάρει τη δουλειά done--
αλλάζει μόνο το ποσό της εργασίας.
Μοιάζει αρχικά είστε εξοικονόμησης ενέργειας, επειδή είστε ακριβώς
ασχολούνται με κάθε στοιχείο μπροστά, χωρίς να σηκωθούν όλα
ο τρόπος μέσα από τον κατάλογο, όπως ο Ben ήταν.
Αλλά το πρόβλημα είναι, ειδικά σε αυτούς τους τρελό περιπτώσεις όπου είναι όλα προς τα πίσω,
είστε ακριβώς το είδος της αναβάλλοντας τη σκληρή δουλειά
μέχρι να έχετε για να διορθώσετε τα λάθη σας.
>> Και έτσι, αν μπορείτε να φανταστείτε αυτό οκτώ και επτά και έξι και πέντε
και αργότερα τεσσάρων και τριών και δύο κινείται το δρόμο τους μέσα από τη λίστα,
έχουμε μόλις αλλάξει η το είδος της εργασίας που κάνουμε.
Αντί να γίνει αυτό κατά τη αρχίζοντας της επανάληψης μου,
Είμαι απλά το κάνουν κατά τη τέλος κάθε επανάληψης.
Έτσι αποδεικνύεται ότι αυτόν τον αλγόριθμο, πάρα πολύ, γενικά ονομάζεται εισαγωγή είδους,
Είναι επίσης της τάξης των n στο τετράγωνο.
Είναι πραγματικά δεν είναι καλύτερη, δεν είναι καλύτερη σε όλα.
>> Ωστόσο, υπάρχει μια τρίτη προσέγγιση Θα ήθελα να μας ενθαρρύνουν να εξετάσει,
το οποίο είναι αυτό.
Έτσι, ας υποθέσουμε λίστα μου, για την απλότητα πάλι, είναι τέσσερα, ένα, τρία,
two-- μόλις τέσσερις αριθμούς.
Ben είχε καλή διαίσθηση, καλή ανθρώπινη διαίσθηση
πριν, με την οποία θα καθοριστεί το σύνολο λίστα eventually-- είδος εισαγωγής.
Θα μας έπεισε μαζί.
Αλλά ας εξετάσουμε το απλούστερος τρόπος για να διορθώσετε αυτή τη λίστα.
>> Αυτή η λίστα δεν είναι ταξινομημένο.
Γιατί;
Στην αγγλική γλώσσα, να εξηγήσει γιατί δεν είναι πραγματικά διευθετηθεί.
Τι δεν σημαίνει να διευθετηθεί;
>> Φοιτητής: Δεν είναι διαδοχική.
>> DAVID Malan: Δεν διαδοχική.
Δώσε μου ένα παράδειγμα.
>> Φοιτητής: Βάλτε τους σε σειρά.
>> DAVID Malan: OK.
Δώστε μου ένα πιο συγκεκριμένο παράδειγμα.
>> Φοιτητής: αύξουσα σειρά.
DAVID Malan: Δεν αύξουσα σειρά.
Να είναι πιο ακριβείς.
Δεν ξέρω τι εννοείτε με αύξουσα σειρά.
Τι τρέχει?
>> ΜΑΘΗΤΗ: Το μικρότερο από το αριθμών δεν είναι στην πρώτη θέση.
>> DAVID Malan: Μικρότερο αριθμό του όχι στον πρώτο χώρο.
Γίνε πιο συγκεκριμένος.
Αρχίζω να πιάσει.
Μετράμε, αλλά τι είναι εκτός λειτουργίας εδώ;
>> Φοιτητής: αριθμητική ακολουθία.
DAVID Malan: αριθμητική ακολουθία.
το είδος του καθενός της τήρησης το here-- πολύ υψηλό επίπεδο.
Απλά κυριολεκτικά να μου πει τι είναι λάθος σαν ένα πέντε-year-old δύναμη.
>> Φοιτητής: συν ένα.
>> DAVID Malan: Τι είναι αυτό;
>> Φοιτητής: συν ένα.
>> DAVID Malan: Τι εννοείς συν ένα;
Δώσε μου ένα διαφορετικό πέντε ετών.
Τι είναι λάθος, μαμά;
Τι κάνει λάθος, ο μπαμπάς;
Τι εννοείς αυτό δεν είναι ταξινομημένο;
>> Φοιτητής: Δεν είναι το σωστό μέρος.
>> DAVID Malan: Τι είναι όχι στο σωστό μέρος;
>> ΦΟΙΤΗΤΗ: Four.
DAVID Malan: Εντάξει, καλά.
Έτσι, τέσσερις δεν είναι εκεί που πρέπει να είναι.
Ειδικότερα, είναι αυτό το δικαίωμα;
Τέσσερις και ένα, το πρώτο δύο αριθμούς βλέπω.
Είναι αυτό σωστό?
Όχι, είναι εκτός λειτουργίας, έτσι δεν είναι;
Στην πραγματικότητα, σκεφτείτε τώρα για έναν υπολογιστή, πάρα πολύ.
Μπορεί μόνο να δούμε ίσως ένα, ίσως δύο πράγματα once--
και στην πραγματικότητα μόνο ένα πράγμα σε μια στιγμή, αλλά μπορεί τουλάχιστον
δούμε ένα πράγμα, στη συνέχεια, το επόμενο πράγμα ακριβώς δίπλα σε αυτό.
>> Έτσι είναι αυτά για;
Φυσικά και όχι.
Έτσι, ξέρετε τι;
Γιατί δεν παίρνουμε το μωρό βήματα για τον καθορισμό αυτού του προβλήματος
αντί να κάνει αυτά τα φανταχτερά αλγόριθμοι όπως ο Ben, όπου
αυτός είναι το είδος αυτό για τον καθορισμό από την looping μέσα στη λίστα
αντί να κάνει ό, τι έκανα, όπου Θέλω μόνο είδος που ορίζεται ως πάμε;
Ας κυριολεκτικά καταρρεύσει η έννοια της order-- αριθμητική σειρά,
ονομάσουμε ό, τι want-- σε αυτές τις κατά ζεύγη συγκρίσεις.
>> Τέσσερις και ένα.
Είναι αυτό η σωστή σειρά;
Ας το διορθώσουμε.
Ένα και τέσσερα, και στη συνέχεια θα αντιγράψει ακριβώς αυτό.
Εντάξει, καλά.
Έχω σταθερό από ένα έως τέσσερα.
Τρία και δύο;
Όχι.
Ας τα λόγια μου ταιριάζουν τα δάχτυλά μου.
Τέσσερις και τρεις;
>> Δεν είναι σε σειρά, έτσι Πάω να κάνει ένα, τρία, τέσσερα, δύο.
Εντάξει, καλά.
Τώρα τεσσάρων και δύο;
Πρέπει να το διορθώσετε αυτό, πάρα πολύ.
Έτσι ένα, τρία, δύο, τέσσερα.
Έτσι είναι ταξινομημένο;
Όχι, αλλά είναι πιο κοντά να διευθετηθεί;
>> Είναι, γιατί αυτή καθορίζεται λάθος, είμαστε σταθερά αυτό το λάθος,
και σταθερό αυτό το λάθος.
Γι 'αυτό και σταθερό τρία λάθη αναμφισβήτητα.
Ακόμα πραγματικά δεν φαίνονται ταξινομημένα αλλά είναι αντικειμενικά πιο κοντά να διευθετηθεί
γιατί έχουμε σταθερό ορισμένα από αυτά τα λάθη.
>> Τώρα τι πρέπει να κάνω το επόμενο βήμα;
Ι το είδος φτάσει στο τέλος της λίστας.
Μου φάνηκε να έχουν σταθερές όλα τα λάθη, αλλά όχι.
Επειδή σε αυτή την περίπτωση, ορισμένοι αριθμοί θα μπορούσε να διοχετεύεται μέχρι πιο κοντά
σε άλλες αριθμών που εξακολουθούν να είναι εκτός λειτουργίας.
Έτσι, ας το κάνουμε και πάλι, και εγώ θα απλά να το κάνει στη θέση του αυτή τη φορά.
Ενός και τριών;
Είναι εντάξει.
Τρία και δύο;
Φυσικά όχι, οπότε ας το αλλάξουμε αυτό.
Έτσι δύο, τρία.
Τρία και τέσσερα;
Και τώρα ας είναι ιδιαίτερα σχολαστικός εδώ.
Είναι ταξινομημένο;
Εσείς οι άνθρωποι ξέρουν ότι είναι ταξινομημένο.
>> Θα πρέπει να προσπαθήσετε ξανά.
Έτσι Ολίβια προτείνει προσπαθώ ξανά.
Γιατί;
Επειδή ένας υπολογιστής δεν έχει η πολυτέλεια των ανθρώπινων ματιών μας
μόλις ανακλώμενη back-- Εντάξει, είμαι γίνει.
Πώς καθορίσει ο υπολογιστής ότι ο κατάλογος είναι τώρα ταξινομημένο;
Μηχανικά.
>> Θα πρέπει να περάσουν από για μια ακόμη φορά, και μόνο αν
δεν κάνουν / να βρούμε τα λάθη μπορώ στη συνέχεια να συνάψει με τον υπολογιστή, yep,
είμαστε καλοί να πάτε.
Έτσι, ένα και δύο, δύο και τρία, τρία και τέσσερα.
Τώρα μπορώ να πω οριστικά αυτό είναι διαλογή, επειδή έκανα καμία αλλαγή.
Τώρα θα ήταν ένα σφάλμα και μόνο ανόητο αν, ο υπολογιστής,
ζήτησε από τις ίδιες ερωτήσεις ξανά περιμένουμε διαφορετικές απαντήσεις.
δεν πρέπει να συμβεί.
>> Και έτσι τώρα η λίστα είναι ταξινομημένο.
Δυστυχώς, χρόνος λειτουργίας της Ο αλγόριθμος αυτός είναι επίσης Ν τετράγωνο.
Γιατί;
Επειδή έχετε n αριθμούς, και το χειρότερη περίπτωση θα πρέπει να κινηθούν οι αριθμοί n
n φορές γιατί πρέπει να συνεχίσουμε πίσω για να ελέγξει και ενδεχομένως να καθορίσει
αυτοί οι αριθμοί.
Και μπορούμε να κάνουμε μια πιο τυπική ανάλυση, πάρα πολύ.
>> Έτσι, όλα αυτά είναι για να πούμε ότι έχουμε λάβει τρεις διαφορετικές προσεγγίσεις, μία
από αυτούς αμέσως διαισθητική από το ρόπαλο από τον Ben
με προτεινόμενη εισαγωγή μου Ταξινόμηση σε αυτό
όπου μπορείτε είδους παραβλέπουμε το δάσος για τα δέντρα αρχικά.
Στη συνέχεια, όμως, αν κάνουμε ένα βήμα πίσω, voila, έχουμε σταθερή την έννοια διαλογής.
Έτσι, αυτό είναι, τολμώ να πω, ένα χαμηλότερο επίπεδο ίσως
από ό, τι μερικά από τα άλλα αλγορίθμους, αλλά ας
να δούμε αν δεν μπορούμε να απεικονίσει αυτά μέσω αυτού.
>> Έτσι, αυτό είναι μερικά ωραία λογισμικό ότι κάποιος
έγραψε χρησιμοποιώντας πολύχρωμα μπαρ που είναι πρόκειται να κάνετε τα εξής για εμάς.
Κάθε μία από αυτές τις ράβδους αντιπροσωπεύει έναν αριθμό.
Ψηλότερος το μπαρ, το μεγαλύτερο ο αριθμός, τόσο μικρότερη είναι η ράβδος,
όσο μικρότερος είναι ο αριθμός.
Έτσι, στην ιδανική περίπτωση που θέλετε ένα ωραίο πυραμίδα όπου ξεκινά μικρό και παίρνει μεγάλες,
και ότι θα σήμαινε ότι αυτές οι μπάρες ταξινομημένο.
Έτσι, Πάω να πάει μπροστά και να επιλέξετε, για παράδειγμα, ο αλγόριθμος του Ben
first-- είδος επιλογής.
>> Και παρατηρήστε τι κάνει.
Ο τρόπος με τον οποίο έχετε επιλέξει να απεικονίσει αυτόν τον αλγόριθμο
είναι ότι, ακριβώς όπως ήμουν περπατώντας μέσα από λίστα μου,
Αυτό το πρόγραμμα είναι το περπάτημα μέσω λίστα των αριθμών,
τονίζοντας σε ροζ χρώμα κάθε αριθμός που είναι κοιτάζοντας.
Και τι πρόκειται να συμβεί τώρα;
>> Ο μικρότερος αριθμός ότι Ι ή Ben βρεθεί ξαφνικά
παίρνει κινήθηκε προς την αρχή της λίστας.
Και παρατηρήστε έκαναν έξωση ο αριθμός που ήταν εκεί,
και ότι είναι απολύτως εντάξει.
Δεν είχα μπει σε αυτό το επίπεδο λεπτομέρειας.
Αλλά πρέπει να τεθεί ότι ο αριθμός κάπου,
γι 'αυτό ακριβώς κινήθηκε προς το ανοικτό σημείο που δημιουργήθηκε.
Έτσι, Πάω να επιταχυνθεί αυτή η up, γιατί διαφορετικά
γίνεται πολύ κουραστικό γρήγορα.
Animation speed-- εκεί πάμε.
Έτσι τώρα ίδια αρχή Ήμουν εφαρμογή, αλλά θα
μπορεί να αρχίσει να αισθάνονται τον αλγόριθμο, που αν θα είναι, ή να δείτε λίγο πιο ξεκάθαρα.
Και αυτός ο αλγόριθμος έχει ως αποτέλεσμα την επιλέγοντας το επόμενο μικρότερο στοιχείο,
έτσι θα πάμε να αρχίσουν να δείτε ράμπα μέχρι στα αριστερά.
Και σε κάθε επανάληψη, όπως πρότεινε, το κάνει λίγο λιγότερη εργασία.
Δεν πρέπει να πάει σε όλη τη διαδρομή πίσω στο αριστερό άκρο της λίστας,
γιατί ήδη ξέρει αυτά είναι ταξινομημένο.
Γι 'αυτό το είδος του αισθάνεται σαν να είναι επιτάχυνση, αν και κάθε βήμα είναι
λαμβάνοντας το ίδιο χρονικό διάστημα.
Υπάρχει μόνο λιγότερα βήματα που απομένουν.
Και τώρα μπορείτε είδος μπορεί να αισθάνεται ο αλγόριθμο καθαρισμό στο τέλος της,
και μάλιστα τώρα είναι ταξινομημένο.
>> Έτσι, το είδος εισαγωγής είναι όλα γίνονται.
Θα πρέπει να επαν-τυχαίο τον πίνακα.
Και παρατηρήσετε μπορώ μόνο κρατήσει την τυχαία αυτό,
και θα πάρετε μια προσέγγιση της η ίδια προσέγγιση, το είδος εισαγωγής.
Επιτρέψτε μου να επιβραδύνει εδώ.
Ας ξεκινήσουμε ότι πάνω.
Στάση.
>> Ας παραλείψτε τέσσερις.
Εκεί πάμε.
Τυχαίο σειρά τους.
Και εδώ έχουμε go-- είδος εισαγωγής.
Παιχνίδι.
Παρατηρήστε ότι αυτό είναι που ασχολούνται με κάθε στοιχείο συναντά αμέσως,
αλλά αν ανήκει σε η λανθασμένη ανακοίνωση χώρα
όλες τις εργασίες που έχει να συμβεί.
Πρέπει να συνεχίσουμε τη μετατόπιση περισσότερα και περισσότερα στοιχεία για να κάνει χώρο
για τη μία θέλουμε να τεθεί σε εφαρμογή.
>> Έτσι, είμαστε εστιάζοντας στην αριστερό άκρο του μόνο τη λίστα.
Ανακοίνωση δεν έχουμε καν κοίταξε at-- μας Δεν έχουν αναδείξει σε ροζ τίποτα
δεξιά.
Είμαστε ακριβώς που ασχολούνται με τα προβλήματα όπως πάμε,
αλλά είμαστε δημιουργώντας πολλά εργάζονται για τον εαυτό μας ακόμα.
Και έτσι αν θέλουμε να επιταχύνει τη διαδικασία τώρα να πάνε στην ολοκλήρωση,
έχει μια διαφορετική αίσθηση σε αυτό όντως.
Είναι απλά με επίκεντρο το αριστερό άκρο, αλλά κάνει λίγο περισσότερη δουλειά ως needed--
είδους εξομάλυνση πράγματα πάνω, για τον καθορισμό πράγματα,
αλλά ασχολούνται τελικά με κάθε στοιχείο, ένα κάθε φορά
μέχρι να φτάσουμε στο το-- καλά, Όλοι γνωρίζουμε πώς αυτό πρόκειται να τελειώσει,
γι 'αυτό είναι λίγο απογοητευτικό ίσως.
>> Αλλά ο κατάλογος στον end-- spoiler-- πρόκειται να διευθετηθεί.
Έτσι, ας ρίξουμε μια ματιά σε ένα τελευταίο.
Δεν μπορούμε απλά να παραλείψετε τώρα.
Είμαστε σχεδόν εκεί.
Δύο για να πάει, το ένα για να πάει.
Και voila.
Έξοχος.
>> Έτσι τώρα ας κάνουμε μια τελευταία, εκ νέου την τυχαία κατανομή με ταξινόμηση φυσαλίδας.
Και παρατηρήσετε εδώ, ειδικά αν μπορώ να επιβραδύνει προς τα κάτω, αυτό τηρεί ορμώντας μέσα.
Αλλά παρατηρήσετε ότι κάνει ακριβώς ζεύγη comparisons-- είδος τοπικές λύσεις.
Αλλά μόλις φτάσουμε το τέλος του καταλόγου σε ροζ χρώμα,
τι θα πρέπει να συμβεί ξανά;
Ναι, πρόκειται να πρέπει να ξεκινήσετε από την αρχή, γιατί μόνο
σταθερό ζεύγη λάθη.
Και αυτό θα μπορούσε να αποκαλύψει ακόμα άλλους.
Και έτσι αν έχετε να επιταχύνει τη διαδικασία, θα δείτε ότι, όσο υποδηλώνει το όνομα,
το μικρότερο elements-- ή μάλλον, τα μεγαλύτερα elements-- ξεκινώντας
να φούσκα μέχρι την κορυφή, αν θέλετε.
Και τα μικρότερα στοιχεία είναι αρχίζουν να φούσκα κάτω προς τα αριστερά.
Και πράγματι, αυτό είναι το είδος της το οπτικό αποτέλεσμα, καθώς και.
Και έτσι αυτό θα καταλήξει φινίρισμα σε ένα πολύ παρόμοιο τρόπο, πάρα πολύ.
>> Δεν έχουμε να σταθώ σε αυτό το συγκεκριμένο.
Επιτρέψτε μου να ανοίξει αυτό τώρα, πάρα πολύ.
Υπάρχουν μερικά άλλα αλγορίθμων ταξινόμησης στον κόσμο, μερικά εκ των οποίων
Εδώ συλλαμβάνονται.
Και ειδικά για τους μαθητές που δεν είναι απαραίτητα οπτική ή μαθηματικών,
όπως κάναμε πριν, μπορούμε Επίσης, το κάνετε αυτό audially
αν έχουμε συνδέσει έναν ήχο με αυτό.
Και μόνο για διασκέδαση, εδώ είναι μια Λίγα διαφορετικών αλγορίθμων,
και ένας από αυτούς, ιδίως είστε Θα παρατηρήσετε ονομάζεται «συγχώνευση του είδους."
>> Είναι πραγματικά μια ριζικά καλύτερο αλγόριθμο,
τέτοια ώστε ταξινόμηση με συγχώνευση, ένας από τους αυτά που είστε έτοιμος να δείτε,
Δεν είναι σειρά των n τετράγωνο.
Είναι της τάξης του n φορές log της n, η οποία είναι στην πραγματικότητα μικρότερο και έτσι
ταχύτερα από ό, τι τα άλλα τρία.
Και υπάρχει ένα ζευγάρι άλλα ανόητα αυτά που θα δούμε.
>> Έτσι, εδώ πηγαίνουμε με κάποιο ήχο.
Αυτό είναι το είδος της εισαγωγής, οπότε και πάλι είναι ακριβώς ασχολούνται με τα στοιχεία
όπως έρχονται.
Αυτό είναι το είδος φούσκα, έτσι είναι θεωρώντας τα ζευγάρια σε έναν χρόνο.
Και πάλι, τα μεγαλύτερα στοιχεία Οι εμφύσηση μέχρι την κορυφή.
>> Έπειτα επάνω είδος επιλογής.
Αυτό είναι ο αλγόριθμος του Ben, όπου και πάλι αυτός είναι επιλογή επαναληπτικά
το επόμενο μικρότερο στοιχείο.
Και πάλι, τώρα μπορείτε πραγματικά να ακούω ότι αυτό είναι την επιτάχυνση, αλλά μόνο στο βαθμό
όπως κάνει και λιγότερο εργάζονται σε κάθε επανάληψη.
Αυτή είναι η πιο γρήγορη μία, ταξινόμηση με συγχώνευση, η οποία είναι η διαλογή συστάδες των αριθμών
μαζί και στη συνέχεια ο συνδυασμός τους.
Έτσι look-- το αριστερό μισό έχει ήδη διευθετηθεί.
>> Τώρα είναι η διαλογή το δεξί μισό, και Τώρα πρόκειται να τα συνδυάσετε σε ένα.
Αυτό είναι κάτι που ονομάζεται "Gnome είδος."
Και μπορείτε να το είδος δούμε ότι πρόκειται εμπρός και πίσω,
καθορισμό έργο λίγο εδώ και εκεί πριν προχωρήσει σε νέα εργασία.
Και αυτό είναι όλο.
Υπάρχει ένα άλλο είδος, το οποίο είναι πραγματικά μόνο για ακαδημαϊκούς σκοπούς,
που ονομάζεται «ηλίθιο είδος," η οποία λαμβάνει τα δεδομένα σας, ταξινομεί τυχαία,
και στη συνέχεια ελέγχει αν είναι ταξινομημένο.
Και αν δεν είναι, εκ νέου ταξινομεί το τυχαία, ελέγχει αν είναι ταξινομημένο,
και αν δεν επαναλαμβάνεται.
Και στη θεωρία, πιθανολογικά αυτό θα ολοκληρωθεί,
αλλά μετά από αρκετά ένα κομμάτι του χρόνου.
Δεν είναι το πιο αποδοτικών αλγορίθμων.
Έτσι, οποιεσδήποτε ερωτήσεις σχετικά με εκείνους Ειδικότερα οι αλγόριθμοι ή τίποτα
που σχετίζονται εκεί, πάρα πολύ;
>> Λοιπόν, ας τώρα πειράζουν πέρα ​​ό, τι όλα αυτές οι γραμμές είναι ότι έχω την κατάρτιση
και τι είμαι υποθέτοντας τον υπολογιστή μπορεί να κάνει κάτω από την κουκούλα.
Θα έλεγα ότι όλα αυτά τα νούμερα Κρατάω drawing-- που χρειάζονται για να
αποθηκευμένα κάπου στη μνήμη.
Θα απαλλαγούμε από αυτόν τον τύπο σήμερα, πάρα πολύ.
>> Έτσι, ένα κομμάτι της μνήμης σε ένα computer-- έτσι RAM DIMM είναι
αυτό που έψαχναν για χθες, διπλή inline μνήμη module-- μοιάζει με αυτό.
Και κάθε ένα από αυτά τα μικρά μαύρα τσιπ είναι κάποια αριθμός των bytes, τυπικά.
Και τότε οι χρυσές καρφίτσες είναι σαν το καλώδια που συνδέουν τον υπολογιστή,
και το πράσινο πλακέτα πυριτίου είναι μόνο αυτό που κρατά τα πάντα μαζί.
Λοιπόν, τι σημαίνει αυτό πραγματικά;
Αν ήμουν είδος επιστήσει την ίδια εικόνα, ας υποθέσουμε για απλότητα
ότι αυτή η DIMM, διπλή inline μονάδα μνήμης,
είναι ένα gigabyte μνήμης RAM, ένα gigabyte μνήμη, η οποία είναι πόσα bytes;
Ένα gigabyte είναι πόσα bytes;
Περισσότερο από αυτό.
1124 είναι κιλό, 1000.
Mega είναι εκατομμύρια.
Giga είναι ένα δισεκατομμύριο.
>> Είμαι ξαπλωμένη;
Μπορούμε να διαβάσει ακόμα την ετικέτα;
Αυτό είναι στην πραγματικότητα 128 gigabytes, οπότε είναι περισσότερο.
Αλλά θα προσποιηθώ αυτό Είναι απλά ένα gigabyte.
Έτσι, αυτό σημαίνει ότι υπάρχει ένα δισεκατομμύριο bytes της μνήμης στη διάθεσή μου
ή 8 δισεκατομμύρια bits, αλλά θα πάμε να μιλήσει από την άποψη των bytes τώρα,
προχωρώντας μπροστά.
>> Έτσι τι αυτό σημαίνει ότι είναι αυτό είναι ένα byte, αυτό είναι ένα άλλο byte,
αυτό είναι ένα άλλο byte, και αν πραγματικά ήθελε
να είναι συγκεκριμένες θα έπρεπε να συντάξει ένα δισεκατομμύριο μικρές πλατείες.
Αλλά τι σημαίνει αυτό;
Λοιπόν, επιτρέψτε μου να μεγεθύνετε σε αυτή την εικόνα.
Αν έχω κάτι που φαίνεται όπως αυτό τώρα, αυτό είναι τέσσερα bytes.
>> Και έτσι θα μπορούσα να βάλω τέσσερις αριθμούς εδώ.
Ένα δύο τρία τέσσερα.
Ή θα μπορούσα να βάλω τέσσερα γράμματα ή σύμβολα.
"Γεια σου!" θα μπορούσε να πάει εκεί, επειδή καθένα από τα γράμματα,
συζητήσαμε νωρίτερα, θα μπορούσαν να εκπροσωπούνται
με οκτώ bits ή ASCII ή ένα byte.
Έτσι με άλλα λόγια, μπορείς βάλει 8000000000 πράγματα στο εσωτερικό
αυτού ένα ραβδί της μνήμης.
Τώρα τι σημαίνει αυτό για να βάλει τα πράγματα πίσω στην πλάτη με πλάτη στη μνήμη σαν αυτό;
Αυτό είναι ό, τι έναν προγραμματιστή θα αποκαλούσα μια «σειρά».
Σε ένα πρόγραμμα υπολογιστή, που δεν νομίζω σχετικά με το υποκείμενο υλικό, per se.
Απλά σκεφτείτε τον εαυτό σας ως έχουν πρόσβαση σε ένα σύνολο δισεκατομμύριο bytes,
και μπορείτε να ό, τι θέλετε με αυτό.
Αλλά για λόγους ευκολίας είναι γενικά χρήσιμη
για να κρατήσει σωστά τη μνήμη σας δίπλα στο άλλο όπως αυτό.
Έτσι, αν κάνετε ζουμ σε this-- επειδή είμαστε σίγουρα δεν πρόκειται
να συντάξει ένα δισεκατομμύριο λίγο τετράγωνα-- ας υποθέσουμε ότι αυτή η πλακέτα αντιπροσωπεύει
ότι το ραβδί μνήμης τώρα.
Και εγώ θα επιστήσω ακριβώς όσο μου δείκτης καταλήγει δίνοντας μου εδώ.
Έτσι τώρα έχουμε ένα ραβδί της μνήμης στην πλακέτα
ότι έχεις ένα, δύο, τρία, τέσσερα, πέντε, έξι, ένα, δύο, τρία, τέσσερα, πέντε, έξι,
seven-- έτσι 42 bytes της μνήμη επί του συνολικού οθόνη.
Ευχαριστώ.
Ναι, έκανε την αριθμητική μου σωστά.
Έτσι 42 bytes της μνήμης εδώ.
Λοιπόν, τι σημαίνει αυτό πραγματικά σημαίνει;
Λοιπόν, ένας προγραμματιστής ηλεκτρονικών υπολογιστών θα ήταν στην πραγματικότητα σε γενικές γραμμές
σκέφτομαι αυτή τη μνήμη ως addressable.
Με άλλα λόγια, κάθε μία από αυτές θέσεις στη μνήμη, στο υλικό,
έχει μια μοναδική διεύθυνση.
>> Δεν είναι τόσο περίπλοκο όπως ένα Brattle Πλατεία, Cambridge, Mass., 02138.
Αντ 'αυτού, είναι απλά ένας αριθμός.
Αυτός είναι ο αριθμός byte μηδέν, αυτό είναι ένα, αυτό είναι δύο, αυτό είναι τρεις,
και αυτό είναι 41.
Περίμενε ένα λεπτό.
Νόμιζα ότι είπα 42 πριν από λίγο.
Άρχισα καταμέτρηση στο μηδέν, έτσι ώστε να είναι πραγματικά σωστή.
Τώρα δεν έχουμε να επιστήσει την πραγματικότητα ως πλέγμα, και αν το σχεδιάσετε ως πλέγμα
Νομίζω ότι τα πράγματα στην πραγματικότητα να πάρει λίγο παραπλανητικό.
Τι προγραμματιστής θα ήταν, στο δικό του μυαλό,
γενικά σκεφτείτε αυτό μνήμη είναι ακριβώς όπως μια ταινία,
σαν ένα κομμάτι κολλητική ταινία που πηγαίνει ακριβώς και για πάντα
ή μέχρι να εξαντληθεί η μνήμη.
Έτσι, μια πιο συνηθισμένος τρόπος για να αντλήσει και απλά σκεφτείτε τη μνήμη
θα ήταν ότι αυτό είναι το byte μηδέν, ένα, δύο, τρία, και στη συνέχεια, τελεία, τελεία, τελεία.
Και έχετε 42 όπως bytes Συνολικά, ακόμη και αν φυσικά αυτό μπορεί στην πραγματικότητα
είναι κάτι περισσότερο σαν αυτό.
>> Έτσι, αν τώρα σκεφτείτε σας μνήμη όπως αυτό, ακριβώς όπως μια ταινία,
Αυτό είναι ό, τι ένας προγραμματιστής και πάλι θα έθετε μια σειρά από μνήμης.
Και όταν θέλετε να αποθηκεύσετε πραγματικά κάτι στη μνήμη ενός υπολογιστή,
μπορείτε γενικά να κάνουμε τα πράγματα κατάστημα back-to-back to back-to-back.
Έτσι έχουμε μιλήσει σχετικά με τους αριθμούς.
Και όταν θέλησα να λύσει τα προβλήματα όπως τέσσερα, ένα, τρία, δύο,
ακόμα κι αν ήμουν μόλις κατάρτιση Μόνον οι αριθμοί τέσσερα, ένα, τρία,
δύο στο διοικητικό συμβούλιο, ο υπολογιστής θα πραγματικά αυτή τη ρύθμιση στη μνήμη.
>> Και τι θα ήταν δίπλα στο δύο στη μνήμη του υπολογιστή;
Λοιπόν, δεν υπάρχει καμία απάντηση σε αυτό.
Εμείς πραγματικά δεν ξέρω.
Και εφόσον η υπολογιστή δεν το χρειάζεται,
δεν πρέπει να με νοιάζει τι είναι το επόμενο με τους αριθμούς που κάνει τη φροντίδα για.
Και όταν είπα νωρίτερα ότι έναν υπολογιστή να δείτε μόνο σε μια διεύθυνση σε μια στιγμή,
αυτό είναι το είδος της γιατί.
>> Δεν σε αντίθεση με ρεκόρ player και μια κεφαλή ανάγνωσης
μόνο να είναι σε θέση να δούμε ένα ορισμένο αυλάκι σε μια φυσική παλιό σχολείο-ρεκόρ
σε μια στιγμή, ομοίως Μπορεί ένας υπολογιστής χάρη
σε CPU και της Intel σύνολο εντολών,
μεταξύ των οποίων η διδασκαλία διαβάζεται από τη μνήμη
ή να το αποθηκεύσετε σε memory-- ένα υπολογιστής μπορεί να κοιτάμε μόνο
σε μια τοποθεσία με ένα time-- μερικές φορές ένα συνδυασμό αυτών,
αλλά πραγματικά μόνο ένα χώρο κάθε φορά.
Έτσι, όταν κάναμε αυτές οι διάφορες αλγόριθμοι,
Δεν είμαι απλά γράφοντας σε ένα vacuum-- τέσσερα, ένα, τρία, δύο.
Αυτοί οι αριθμοί στην πραγματικότητα ανήκουν κάπου φυσική μνήμη.
Έτσι, υπάρχουν μικροσκοπικά τρανζίστορ ή κάποιο είδος
των ηλεκτρονικών ειδών κάτω από το κουκούλα αποθήκευση αυτών των αξιών.
>> Και συνολικά, πόσα bits είναι που συμμετέχουν αυτή τη στιγμή, ακριβώς για να είναι σαφές;
Έτσι, αυτό είναι τέσσερα bytes, ή τώρα είναι η συνολική 32 bits.
Έτσι, στην πραγματικότητα υπάρχουν 32 μηδενικά και αυτά που συνθέτουν αυτά τα τέσσερα πράγματα.
Υπάρχει ακόμη περισσότερο εδώ, αλλά και πάλι δεν με νοιάζει γι 'αυτό.
>> Έτσι τώρα, ας ζητήσει από άλλο ερώτηση χρησιμοποιώντας τη μνήμη,
επειδή ότι στο τέλος της ημέρας είναι στο διακύμανσης.
Δεν έχει σημασία τι θα μπορούσαμε να κάνουμε με ο υπολογιστής, στο τέλος της ημέρας
το υλικό εξακολουθεί να είναι η ίδιο κάτω από την κουκούλα.
Πώς θα αποθηκεύσετε μια λέξη εδώ;
Λοιπόν, μια λέξη σε έναν υπολογιστή, όπως "Γεια σου!" θα αποθηκεύονται ακριβώς όπως αυτό.
Και αν θέλετε ένα μεγαλύτερο λέξη, μπορείτε απλά
αντικαταστήσετε ότι και να πω κάτι όπως "γεια" και το κατάστημα που εδώ.
>> Και έτσι εδώ, πάρα πολύ, αυτό contiguousness είναι στην πραγματικότητα ένα πλεονέκτημα,
γιατί ένας υπολογιστής μπορεί απλά διαβάζεται από δεξιά προς τα αριστερά.
Αλλά εδώ είναι μια ερώτηση.
Στο πλαίσιο αυτής της λέξης, h-e-l-L-o, θαυμαστικό,
πώς θα μπορούσε ο υπολογιστής ξέρει όπου ο λέξη αρχίζει και πού τελειώνει η λέξη;
Στο πλαίσιο των αριθμών, πώς ο υπολογιστής
ξέρω πόσο καιρό η ακολουθία του αριθμοί είναι ή όπου αρχίζει;
Λοιπόν, αποδεικνύεται out-- και εμείς δεν θα πάει πάρα πολύ
σε αυτό το επίπεδο detail-- υπολογιστές κινηθούν τα πράγματα γύρω στη μνήμη
κυριολεκτικά μέσω των διευθύνσεων αυτών.
Έτσι, σε έναν υπολογιστή, αν είστε γράφοντας κώδικα για να αποθηκεύσετε τα πράγματα
όπως λέξεις, τι είστε πραγματικά κάνουν είναι να πληκτρολογείτε
εκφράσεις που θυμάμαι όταν σε μνήμη του υπολογιστή αυτά τα λόγια είναι.
Έτσι, επιτρέψτε μου να κάνω μια πολύ, πολύ απλό παράδειγμα.
>> Πάω να πάει μπροστά και να ανοίξει ένα απλό πρόγραμμα κειμένου,
και Πάω να δημιουργήσουν ένα αρχείο που ονομάζεται hello.c.
Οι περισσότερες από αυτές τις πληροφορίες που Δεν θα μπω σε με μεγάλη λεπτομέρεια,
αλλά Πάω να γράψω ένα προγράμματος σε εκείνη την ίδια γλώσσα,
C. Αυτό είναι πολύ πιο εκφοβιστικό, Θα έλεγα, από το μηδέν,
αλλά είναι πολύ παρόμοιο με το πνεύμα.
Στην πραγματικότητα, αυτά τα σγουρά braces-- μπορείτε να το είδος της
σκεφτείτε τι έκανα ακριβώς όπως αυτό.
>> Ας κάνουμε αυτό, στην πραγματικότητα.
Όταν κάνετε κλικ πράσινη σημαία, κάνετε τα εξής.
Θέλω να εκτυπώσετε "γεια".
Έτσι, αυτό είναι τώρα ψευδοκώδικα.
Είμαι το είδος της θολώνοντας τις γραμμές.
Στην C, αυτή η γλώσσα που μιλώ περίπου, αυτή η γραμμή εκτύπωσης γεια
στην πραγματικότητα γίνεται "printf» με μερικές παρενθέσεις και μία άνω τελεία.
>> Αλλά είναι η ίδια ακριβώς ιδέα.
Και αυτό είναι πολύ φιλικό προς το χρήστη "Όταν πατηθεί πράσινη σημαία" γίνεται
η πιο απόκρυφες "int main άκυρη."
Και αυτό πραγματικά δεν έχει καμία χαρτογράφηση, έτσι είμαι απλώς πρόκειται να αγνοήσει αυτό.
Αλλά τα άγκιστρα είναι σαν το καμπύλα κομμάτια του παζλ σαν αυτό.
>> Έτσι, μπορείτε να το είδος υποθέτω.
Ακόμα κι αν δεν έχετε προγραμματιστεί πριν, τι κάνει αυτό το πρόγραμμα ίσως να κάνω;
Πιθανώς εκτυπώνει γεια με ένα θαυμαστικό.
>> Έτσι, ας προσπαθήσουμε αυτό.
Πάω να το αποθηκεύσετε.
Και αυτό είναι, και πάλι, ένα πολύ παλιό σχολικό περιβάλλον.
Δεν μπορώ να πατήσω, δεν μπορώ να σύρετε.
Έχω να πληκτρολογήσετε εντολές.
Γι 'αυτό θέλω να τρέξει το πρόγραμμά μου, έτσι Θα ήθελα να το κάνετε αυτό, όπως hello.c.
Αυτό είναι το αρχείο έτρεξα.
Αλλά περιμένετε, είμαι λείπει ένα βήμα.
Τι έκανε λέμε είναι απαραίτητη βήμα για μια γλώσσα όπως η C;
Έχω μόνο γραπτή πηγή κώδικα, αλλά τι πρέπει να κάνω;
Ναι, χρειάζομαι ένα compiler.
Έτσι, στο Mac μου εδώ, έχω ένα πρόγραμμα που ονομάζεται GCC, GNU C compiler,
η οποία μου επιτρέπει να κάνω this-- στροφή πηγαίο κώδικα μου σε, θα το ονομάσουμε,
κώδικα μηχανής.
>> Και μπορώ να δω ότι, πάλι, ως εξής, αυτοί
είναι τα μηδενικά και μονάδες που μόλις δημιουργήθηκε από τον πηγαίο κώδικα μου,
όλα τα μηδενικά και μονάδες.
Και αν θέλω να τρέξει μου program-- συμβαίνει
να ονομάζεται a.out για ιστορικές reasons-- "γεια".
Μπορώ να το εκτελέσετε ξανά.
Γεια γεια γεια.
Και φαίνεται να λειτουργεί.
>> Αλλά αυτό σημαίνει ότι κάπου στο μου μνήμη του υπολογιστή είναι οι λέξεις
h-e-l-L-o, θαυμαστικό.
Και αποδεικνύεται, ακριβώς όπως ένα μέρος, ό, τι ένας υπολογιστής θα συνήθως
το κάνουμε έτσι ώστε να ξέρει πού τα πράγματα αρχίζουν και end-- είναι
πρόκειται να θέσει ένα ειδικό σύμβολο εδώ.
Και η σύμβαση είναι να τεθεί η αριθμός μηδέν στο τέλος μιας λέξης
έτσι ώστε να γνωρίζετε πού στην πραγματικότητα τελειώνει, έτσι ώστε να
δεν τηρούν την εκτύπωση όλο και περισσότερα χαρακτήρες από ό, τι πραγματικά σκοπεύετε.
>> Αλλά το πακέτο εδώ, ακόμα και αν και αυτό είναι αρκετά απόκρυφα,
είναι ότι είναι, τελικά, σχετικά απλή.
Μπορείτε δόθηκε ένα είδος ταινίας, ένα κενό χώρο στον οποίο μπορείτε να γράψετε γράμματα.
Εσείς απλά πρέπει να έχουν ειδικό σύμβολο, όπως αυθαίρετα
ο αριθμός μηδέν, να θέσει στο τέλος του τα λόγια σας, έτσι ώστε ο υπολογιστής ξέρει,
OH, εγώ πρέπει να σταματήσει την εκτύπωση μετά Βλέπω το θαυμαστικό.
Επειδή το επόμενο πράγμα εκεί είναι μια τιμή ASCII του μηδενός,
ή η μηδενική χαρακτήρα, όπως κάποιος θα το ονομάσουμε.
Αλλά υπάρχει το είδος του προβλήματος εδώ, και ας επανέλθει
σε αριθμούς για μια στιγμή.
Ας υποθέσουμε ότι κάνω, στην πραγματικότητα, έχουν μια σειρά από αριθμούς,
και ας υποθέσουμε ότι το πρόγραμμα γράφω είναι
όπως ένα βιβλίο βαθμό για έναν δάσκαλο και μια τάξη δασκάλους.
Και αυτό το πρόγραμμα το άτομό του επιτρέπει για να πληκτρολογήσετε στις βαθμολογίες των μαθητών τους
στο κουίζ.
Και ας υποθέσουμε ότι ο μαθητής παίρνει 100 στην πρώτη κουίζ τους, ίσως
σαν 80 στην επόμενη, τότε ένα 75, τότε 90 στον τέταρτο κουίζ.
>> Έτσι, σε αυτό το σημείο στην ιστορία, η συστοιχία είναι του μεγέθους τέσσερα.
Δεν υπάρχει απολύτως περισσότερη μνήμη στο υπολογιστή, αλλά η συστοιχία, να το πω έτσι,
έχει μέγεθος τέσσερα.
Ας υποθέσουμε τώρα ότι ο δάσκαλος θέλει να ορίσετε ένα πέμπτο κουίζ στην τάξη.
Λοιπόν, ένα από τα πράγματα που ή αυτή που θα πρέπει να κάνετε
είναι τώρα αποθηκεύουν πρόσθετη αξία εδώ.
Αλλά αν η σειρά έχει ο δάσκαλος δημιουργήθηκε σε αυτό το πρόγραμμα είναι μεγέθους για,
ένα από το πρόβλημα με μία συστοιχία είναι ότι μπορείτε όχι μόνο να συνεχίσουμε να προσθέτουμε στη μνήμη.
Γιατί ό, τι και αν ένα άλλο μέρος του το πρόγραμμα έχει τη λέξη "Γεια σου" εκεί;
>> Με άλλα λόγια, η μνήμη μου μπορεί να είναι χρησιμοποιηθεί για οτιδήποτε σε ένα πρόγραμμα.
Και αν εκ των προτέρων έχω πληκτρολογήσει, hey, Θέλω να εισόδου τέσσερις βαθμολογίες κουίζ,
θα μπορούσε να πάει εδώ και εδώ.
Και αν ξαφνικά αλλάξει το μυαλό σας αργότερα και να πω θέλω ένα πέμπτο κουίζ
σκορ, μπορείτε όχι μόνο να βάζουμε οπουδήποτε θέλετε,
γιατί ό, τι και αν αυτό μνήμη που χρησιμοποιείται
για κάτι else-- κάποιο άλλο πρόγραμμα ή κάποιο άλλο χαρακτηριστικό του προγράμματος
ότι τρέχετε;
Έτσι θα πρέπει να σκεφτείτε εκ των προτέρων πώς θέλετε να αποθηκεύσετε τα δεδομένα σας,
γιατί τώρα έχετε βαμμένα τον εαυτό σας σε ένα ψηφιακό γωνία.
>> Έτσι, ένας δάσκαλος θα μπορούσε, αντί λένε όταν γράφετε ένα πρόγραμμα
για την αποθήκευση του ή της βαθμούς, ξέρετε τι;
Πάω να ζητήσει, όταν γράφετε το πρόγραμμά μου,
ότι θέλω μηδέν, ένα, δύο, τρία, τέσσερα, πέντε, έξι, οκτώ βαθμούς συνολικά.
Έτσι, ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά, οκτώ.
Ο δάσκαλος μπορεί μόλις πάνω από διαθέσει μνήμη κατά τη σύνταξη του προγράμματος του ή της
και να πω, ξέρετε τι;
Είμαι ποτέ δεν πρόκειται να εκχωρήσει περισσότερα από οκτώ κουίζ σε ένα εξάμηνο.
Αυτό είναι απλά τρελό.
Ποτέ δεν θα διαθέσει αυτό.
Έτσι ώστε με αυτόν τον τρόπο αυτός ή αυτή έχει το ευελιξία να σκοράρει κατάστημα σπουδαστών,
όπως 75, 90, και ίσως ένα επιπλέον όπου ο μαθητής πήρε επιπλέον πίστωσης, 105.
>> Αλλά αν ο δάσκαλος δεν χρησιμοποιεί αυτές τις τρεις θέσεις,
υπάρχει ένα έξυπνο πακέτο εδώ.
Αυτός ή αυτή είναι απλώς σπατάλη χώρου.
Έτσι με άλλα λόγια, υπάρχει αυτό το κοινή δίλημμα στον προγραμματισμό
όπου μπορείτε είτε να διαθέσουν ακριβώς όπως το μέγεθος της μνήμης, όπως θέλετε,
η άνω πλευρά του οποίου είναι ότι είστε σούπερ efficient-- δεν είσαι σπάταλη
σε all-- αλλά το μειονέκτημα της οποίας είναι ό, τι εάν αλλάξετε το μυαλό σας, όταν
χρησιμοποιώντας το πρόγραμμα που θέλετε να αποθηκεύσετε περισσότερα δεδομένα από ό, τι προβλεπόταν αρχικά.
>> Έτσι ίσως η λύση είναι, τότε, γράψει τα προγράμματα σας με τέτοιο τρόπο
ότι χρησιμοποιούν περισσότερη μνήμη ό, τι πραγματικά χρειάζονται.
Αυτός ο τρόπος εσείς δεν πρόκειται για να τρέξει σε αυτό το πρόβλημα,
αλλά είστε είναι σπάταλη.
Και η περισσότερη μνήμη πρόγραμμά σας χρησιμοποιεί, όπως συζητήσαμε χθες, το λιγότερο
μνήμη που είναι διαθέσιμη για άλλα προγράμματα,
τόσο πιο γρήγορα ο υπολογιστής σας μπορεί να επιβραδύνει προς τα κάτω, λόγω της εικονικής μνήμης.
Και έτσι η ιδανική λύση θα μπορούσε να είναι αυτό;
>> Υπό-κατανομή φαίνεται κακό.
Πάνω-την κατανομή φαίνεται κακό.
Λοιπόν, τι θα μπορούσε να είναι η καλύτερη λύση;
Ανακατανομής.
Να είναι πιο δυναμική.
Μην πιέζετε τον εαυτό σας να επιλέξετε ένα εκ των προτέρων, στην αρχή, ό, τι θέλετε.
Και σίγουρα δεν υπερ-κατανομή, μήπως είναι σπάταλη.
>> Και έτσι για να επιτευχθεί ο στόχος αυτός, εμείς πρέπει να ρίξει αυτή τη δομή δεδομένων,
να το πω έτσι, μακριά.
Και έτσι ό, τι ένας προγραμματιστής θα χρησιμοποιούν συνήθως
είναι κάτι που δεν είναι ένα που ονομάζεται array αλλά μια συνδεδεμένη λίστα.
Με άλλα λόγια, αυτός ή αυτή θα αρχίζουν να σκέφτονται τη μνήμη τους
ως είδος ενός σχήματος ώστε να να σχεδιάσετε με τον ακόλουθο τρόπο.
Αν θέλω να αποθηκεύσετε έναν αριθμό στη ένα program-- έτσι είναι Σεπτέμβριος,
Έχω δώσει στους μαθητές μου ένα κουίζ? θέλω για να αποθηκεύσετε το πρώτο κουίζ των μαθητών,
και πήραν 100 και στο εξής it-- είμαι πρόκειται να ζητήσει από τον υπολογιστή μου,
μέσω του προγράμματος έχω γραπτή, για ένα κομμάτι της μνήμης.
Και Πάω να αποθηκεύσετε το αριθμό 100 σε αυτό, και αυτό είναι όλο.
>> Στη συνέχεια, λίγες εβδομάδες αργότερα όταν παίρνω το δεύτερο κουίζ μου,
και ήρθε η ώρα για να πληκτρολογήσετε σε αυτό το 90%, Πάω
να ζητήσει από τον υπολογιστή, hey, ηλεκτρονικών υπολογιστών, μπορώ να έχω ένα άλλο κομμάτι της μνήμης;
Είναι πρόκειται να μου δώσει αυτό άδειο κομμάτι της μνήμης.
Πάω να θέσει σε αριθμό 90, αλλά στο πρόγραμμα μου με κάποιο τρόπο ή other--
και δεν θα ανησυχείτε για η σύνταξη για this-- χρειάζομαι
με κάποιο τρόπο να συνδέετε αυτά τα πράγματα μαζί.
Και εγώ θα τους αλυσίδα μαζί με αυτό που μοιάζει με ένα βέλος εδώ.
>> Το τρίτο κουίζ που έρχεται, Πάω να πω, hey, ηλεκτρονικών υπολογιστών,
να μου δώσει ένα άλλο κομμάτι της μνήμης.
Και Πάω να βάλει κάτω ό, τι ήταν, όπως 75,
και έχω να την αλυσίδα αυτή μαζί τώρα με κάποιο τρόπο.
Τέταρτη κουίζ έρχεται, και ίσως ότι είναι προς το τέλος του εξαμήνου.
Και από αυτό το πρόγραμμα μου σημείο θα μπορούσε να είναι με τη χρήση της μνήμης
σε όλη τη χώρα, σε όλο σωματικά.
Και έτσι απλά για πλάκα, είμαι πρόκειται να συντάξει αυτό το εμπρός
quiz-- ξεχάσω ό, τι ήταν? εγώ ότι ίσως ένα 80 ή something--
τρόπο εδώ.
>> Αλλά αυτό είναι εντάξει, επειδή εικονογραφικά Πάω να επιστήσει αυτή τη γραμμή.
Με άλλα λόγια, στην πραγματικότητα, στο υλικό του υπολογιστή σας,
το πρώτο αποτέλεσμα θα μπορούσε καταλήγουν εδώ γιατί είναι
ακριβώς στην αρχή του εξαμήνου.
Η επόμενη θα μπορούσε κανείς να καταλήγουν εδώ επειδή ένα κομμάτι του χρόνου έχει περάσει
και το πρόγραμμα συνεχίζει να τρέχει.
Η επόμενη βαθμολογία, η οποία ήταν ένα 75, θα μπορούσε να είναι εδώ.
Και η τελευταία σκορ θα μπορούσε να είναι ένας 80, που είναι εδώ.
>> Έτσι, στην πραγματικότητα, σωματικά, αυτό θα μπορούσε να είναι τι μνήμη του υπολογιστή σας μοιάζει.
Αλλά αυτό δεν είναι ένα χρήσιμο ψυχική παράδειγμα για έναν προγραμματιστή υπολογιστών.
Γιατί πρέπει να σας νοιάζει, όπου η Heck τα δεδομένα σας είναι να καταλήξουμε;
Απλά θέλετε να αποθηκεύσετε τα δεδομένα.
>> Αυτό είναι κάτι σαν τη συζήτησή μας νωρίτερα από την κατάρτιση του κύβου.
Γιατί σε νοιάζει εσένα τι η γωνία είναι του κύβου
και πώς θα πρέπει να στραφούν για να βγάλουμε;
Μπορείτε απλά θέλουν έναν κύβο.
Ομοίως εδώ, απλά θέλουν να βιβλίου βαθμού.
Απλά θέλετε να σκεφτείτε αυτό ως μια λίστα των αριθμών.
Ποιος νοιάζεται πώς είναι υλοποιηθεί σε hardware;
>> Έτσι τώρα η αφαίρεση Είναι αυτή η εικόνα εδώ.
Αυτή είναι μια λίστα που συνδέεται, όπως ένας προγραμματιστής θα το ονομάσουμε,
εφόσον έχετε ένα κατάλογος, προφανώς των αριθμών.
Αλλά αυτό είναι που συνδέονται εικονογραφικά μέσω αυτών των βελών,
και όλα αυτά τα βέλη are-- κάτω από η κουκούλα, αν είστε περίεργοι,
Υπενθυμίζουμε ότι το φυσικό υλικό μας έχει διευθύνσεις μηδέν, ένα, δύο, τρία, τέσσερα.
Όλα αυτά τα βέλη είναι είναι σαν ένα χάρτη ή οδηγίες, που αν 90 is-- τώρα
Πήρα να μετρήσει.
>> Μηδέν, ένα, δύο, τρία, τέσσερα, πέντε, έξι, επτά.
Μοιάζει με το 90 είναι σε Αριθμός διεύθυνση μνήμης επτά.
Όλα αυτά τα βέλη είναι είναι σαν ένα μικρό κομμάτι χαρτί
ότι είναι να δίνει οδηγίες για το πρόγραμμα που λέει ακολουθούν αυτόν τον χάρτη
για να φτάσουμε στην θέση επτά.
Και εκεί θα βρείτε το δεύτερο βαθμολογία κουίζ μαθητή.
Εν τω μεταξύ, η 75-- αν συνεχιστεί αυτό, αυτό είναι επτά, οκτώ, εννέα, 10, 11, 12,
13, 14, 15.
>> Αυτό το άλλο βέλος αντιπροσωπεύει μόλις το ένας χάρτης στη θέση μνήμης 15.
Αλλά και πάλι, ο προγραμματιστής κάνει γενικά Δεν νοιάζονται για αυτό το επίπεδο λεπτομέρειας.
Και στις περισσότερες κάθε προγραμματισμό γλώσσας σήμερα, ο προγραμματιστής
Δεν θα γνωρίζουν καν από πού στη μνήμη οι αριθμοί αυτοί στην πραγματικότητα είναι.
Όλα τα αυτός ή αυτή έχει να νοιάζονται για είναι ότι είναι κατά κάποιο τρόπο συνδέονται μεταξύ τους
σε μια δομή δεδομένων όπως αυτό.
>> Αλλά τελικά δεν να πάρει πάρα πολύ τεχνική.
Αλλά ακριβώς επειδή μπορούμε ίσως την πολυτέλεια να κάνουμε αυτήν τη συζήτηση εδώ,
ας υποθέσουμε ότι έχουμε επανεξετάσουμε Αυτό το θέμα εδώ μιας συστοιχίας.
Ας δούμε αν λυπούμαστε πρόκειται εδώ.
Αυτό είναι 100, 90, 75, και 80.
>> Επιτρέψτε μου να κάνω για λίγο αυτόν τον ισχυρισμό.
Αυτή είναι μια συστοιχία, και πάλι, ο εξέχον χαρακτηριστικό μιας συστοιχίας
είναι ότι όλα τα δεδομένα σας είναι πίσω για να πλάτη με πλάτη στο memory-- κυριολεκτικά
ένα byte ή ίσως τέσσερα bytes, μερικά σταθερό αριθμό των bytes μακριά.
Σε μια συνδεδεμένη λίστα, η οποία θα μπορούσε να αντλήσει όπως αυτό, κάτω από την κουκούλα που
ξέρει πού ότι τα πράγματα είναι;
Δεν χρειάζεται καν να ρέει σαν αυτό.
Μερικά από τα στοιχεία θα μπορούσαν να είναι πίσω προς τα αριστερά μέχρι εκεί.
Δεν ξέρω καν.
>> Και έτσι με μια σειρά, έχετε ένα χαρακτηριστικό γνωστό ως τυχαίας προσπέλασης.
Και τι σημαίνει τυχαίας προσπέλασης είναι ότι ο υπολογιστής μπορεί να πηδήξει αμέσως
σε οποιαδήποτε θέση σε μια σειρά.
Γιατί;
Επειδή ο υπολογιστής ξέρει ότι η πρώτη θέση είναι
μηδέν, ένα, δύο και τρία.
>> Και έτσι, αν θέλετε να πάτε από Αυτό το στοιχείο στο επόμενο στοιχείο,
μπορείτε κυριολεκτικά, στο το μυαλό του υπολογιστή, απλά προσθέστε ένα.
Αν θέλετε να πάτε στο τρίτο στοιχείο, απλά προσθέστε ένα-- επόμενο στοιχείο, απλά
προσθέσετε μία.
Ωστόσο, σε αυτή την έκδοση της ιστορίας, ας υποθέσουμε
ο υπολογιστής αυτή τη στιγμή ψάχνει στο ή ασχολούνται με τον αριθμό 100.
Πώς μπορείτε να φτάσετε στο επόμενο βαθμό στο βιβλίο βαθμό;
>> Θα πρέπει να λάβει επτά στάδια, η οποία είναι αυθαίρετη.
Για να φτάσετε στο επόμενο, θα πρέπει να να λάβει άλλα οκτώ βήματα για να φτάσετε στο 15.
Με άλλα λόγια, δεν είναι ένα σταθερό διάκενο μεταξύ των αριθμών,
και γι 'αυτό ακριβώς χρειάζεται η υπολογιστή περισσότερο χρόνο είναι το σημείο.
Ο υπολογιστής πρέπει να ψάξει μέσω της μνήμης, προκειμένου
για να βρείτε αυτό που ψάχνετε.
>> Έτσι, ενώ μια σειρά τείνει να είναι μια structure-- γρήγορα τα δεδομένα, γιατί
μπορεί κυριολεκτικά να κάνει απλή αριθμητική και να πάρετε όπου θέλετε με την προσθήκη ενός,
για instance-- μια συνδεδεμένη λίστα, θα θυσιάσει αυτό το χαρακτηριστικό.
Δεν μπορείς απλά να πάει από την πρώτη για τη δεύτερη στην τρίτη στην τέταρτη θέση.
Θα πρέπει να ακολουθήσετε το χάρτη.
Θα πρέπει να λάβει περισσότερα μέτρα για να πάρει σε αυτές τις αξίες, οι οποίες
φαίνεται να είναι η προσθήκη ενός κόστους.
Έτσι είμαστε πληρώνουν ένα τίμημα, αλλά αυτό που ήταν το χαρακτηριστικό ότι Dan αναζητούσε εδώ;
Τι κάνει μια συνδεδεμένη λίστα προφανώς θα μας επιτρέψουν να κάνουμε,
το οποίο ήταν η προέλευση της Αυτή η συγκεκριμένη ιστορία;
>> Ακριβώς.
Μια δυναμική μέγεθος σε αυτό.
Μπορούμε να προσθέσουμε σε αυτή τη λίστα.
Μπορούμε να συρρικνωθεί ακόμη τη λίστα, έτσι ότι είμαστε μόνο χρησιμοποιώντας ως πολύ μνήμη
όπως έχουμε πραγματικά θέλουν και έτσι είμαστε ποτέ υπερβολική κατανομή.
>> Τώρα, ακριβώς για να είναι πραγματικά nit-επιλεκτικοί, υπάρχει ένα κρυφό κόστος.
Έτσι δεν θα πρέπει απλά επιτρέψτε μου να πείσω σας ότι αυτό είναι ένα σημαντικό δίλημμα.
Υπάρχει ένα άλλο κρυφό κόστος εδώ.
Το όφελος, να είναι σαφής, είναι ότι έχουμε δυναμισμό.
Αν θέλω ένα άλλο στοιχείο, μπορώ μόνο συντάξει και να το βάλετε έναν αριθμό εκεί.
Και τότε μπορώ να το συνδέσετε με μια εικόνα εδώ,
ενώ εδώ, και πάλι, αν έχω ζωγράφισε τον εαυτό μου σε μια γωνία,
αν κάτι άλλο είναι ήδη χρησιμοποιώντας η μνήμη εδώ, είμαι από την τύχη.
Έχω ζωγράφισε τον εαυτό μου στη γωνία.
>> Αλλά τι είναι το κρυφό το κόστος σε αυτή την εικόνα;
Δεν είναι μόνο το ποσό του χρόνου που χρειάζεται
για να πάει από εδώ εδώ, η οποία είναι επτά βήματα, στη συνέχεια,
οκτώ βήματα, που είναι περισσότερα από ένα.
Τι είναι άλλο κρυφό κόστος;
Όχι μόνο χρόνο.
Πρόσθετες πληροφορίες αναγκαίο για την επίτευξη αυτή την εικόνα.
>> Ναι, αυτό χάρτη, αυτά τα μικρά κομμάτια χαρτί, όπως έχω κρατήσει τους περιγράφει ως.
Αυτά arrows-- αυτά δεν είναι δωρεάν.
Μια computer-- ξέρετε ό, τι ένας υπολογιστής έχει.
Έχει μηδενικά και μονάδες.
Αν θέλετε να αντιπροσωπεύουν ένα βέλος ή ένα χάρτης ή ένας αριθμός, θα πρέπει να έχετε κάποια μνήμη.
Έτσι, από την άλλη τιμή που πληρώσουν για μια συνδεδεμένη λίστα,
ένα κοινό επιστήμη των υπολογιστών των πόρων, είναι επίσης χώρο.
>> Και πράγματι έτσι, τόσο συχνά, μεταξύ των tradeoffs
στο σχεδιασμό της μηχανικής λογισμικού συστημάτων είναι ο χρόνος και space--
είναι δύο από τα συστατικά σας, δύο από τα πιο δαπανηρά συστατικά σας.
Αυτό μου κοστίζει περισσότερο χρόνο γιατί έχω να ακολουθήσουν αυτό το χάρτη,
αλλά είναι επίσης κοστίζει μένα περισσότερο χώρο γιατί έχω να κρατήσει αυτό το χάρτη γύρω.
Έτσι, η ελπίδα, όπως έχουμε το είδος της συζήτησαν πάνω χθες και σήμερα,
είναι ότι τα οφέλη θα υπερκαλύπτουν το κόστος.
>> Αλλά δεν υπάρχει καμία προφανής λύση εδώ.
Ίσως είναι better-- a la γρήγορη και βρώμικη,
όπως Kareem προτεινόμενη earlier-- να ρίξει τη μνήμη στο πρόβλημα.
Απλά αγοράζουν περισσότερη μνήμη, σκέφτονται λιγότερο σκληρά για την επίλυση του προβλήματος,
και να το λύσει με έναν ευκολότερο τρόπο.
Και πράγματι νωρίτερα, όταν μιλήσαμε για ανταλλαγές,
δεν ήταν κόπηκε με ο υπολογιστής και το χρόνο.
Ήταν η ώρα του έργου, η οποία είναι ένα ακόμη πόρο.
>> Έτσι και πάλι, είναι αυτό πράξη εξισορρόπησης προσπαθείτε να αποφασίσετε ποια από αυτά τα πράγματα
είστε πρόθυμοι να περάσετε;
Ποιο είναι το λιγότερο ακριβό;
Η οποία αποδίδει τα καλύτερα αποτελέσματα;
Ναι;
>> Πράγματι.
Σε αυτή την περίπτωση, αν είστε που αντιπροσωπεύουν αριθμούς στο maps--
αυτές ονομάζονται σε πολλές γλώσσες «Δείκτες» ή «διευθύνσεις» -
είναι διπλάσιο από το χώρο.
Αυτό δεν χρειάζεται να είναι τόσο κακή όσο διπλά αν τώρα είμαστε ακριβώς την αποθήκευση αριθμών.
Ας υποθέσουμε ότι είχαμε την αποθήκευση φακέλους των ασθενών σε hospital--
έτσι ώστε ονόματα του Pierson, αριθμούς τηλεφώνου, αριθμούς κοινωνικής ασφάλισης, ο γιατρός
ιστορία.
Αυτό το πλαίσιο θα μπορούσε να είναι πολύ, πολύ μεγαλύτερη, οπότε
ένα μικροσκοπικό μικρό δείκτη, η διεύθυνση της η επόμενη element-- δεν είναι μια μεγάλη υπόθεση.
Είναι ένα τέτοιο περιθώριο το κόστος αυτό δεν έχει σημασία.
Αλλά σε αυτή την περίπτωση, ναι, είναι ο διπλασιασμός.
Καλή ερώτηση.
>> Ας μιλήσουμε για το χρόνο μια λίγο πιο συγκεκριμένα.
Τι είναι ο χρόνος εκτέλεσης από την αναζήτηση αυτή τη λίστα;
Ας υποθέσουμε Ήθελα να αναζητήσετε μέσω όλων των τάξεων των μαθητών,
και υπάρχει n βαθμούς σε αυτή τη δομή δεδομένων.
Εδώ, επίσης, μπορούμε να δανειστούμε το λεξιλόγιο του νωρίτερα.
Αυτή είναι μια γραμμική δομή δεδομένων.
>> Big O Ν είναι ό, τι απαιτείται για να στο τέλος αυτής της δομής δεδομένων,
whereas-- και δεν έχουμε δει Αυτό before-- μια σειρά που δίνει
αυτό που ονομάζεται σταθερά χρόνου, πράγμα που σημαίνει ένα βήμα ή δύο βήματα ή 10 steps--
Δεν πειράζει.
Είναι ένα σταθερό αριθμό.
Δεν έχει τίποτε να κάνει με την το μέγεθος της συστοιχίας.
Και ο λόγος γι 'αυτό, πάλι, είναι τυχαίας προσπέλασης.
Ο υπολογιστής μπορεί απλά αμέσως μεταβείτε σε άλλη θέση,
επειδή είναι όλοι το ίδιο απόσταση από οτιδήποτε άλλο.
Δεν υπάρχει καμία σκέψη που εμπλέκονται.
Εντάξει.
Έτσι, αν μπορώ, επιτρέψτε μου να προσπαθήσω να ζωγραφίσει δύο τελικές εικόνες.
Ένα πολύ κοινό ένα γνωστό ως πίνακα κατακερματισμού.
Έτσι για να παρακινήσει τη συζήτηση αυτή, επιτρέψτε μου να σκεφτεί για το πώς να το κάνουμε αυτό.
>> Πώς, λοιπόν, γι 'αυτό;
Ας υποθέσουμε ότι το πρόβλημα θέλουμε να λύσουμε τώρα
εφαρμόζει σε dictionary-- έτσι, ένα σωρό των αγγλικών λέξεων
ή οτιδήποτε.
Και ο στόχος είναι να είναι σε θέση να απαντήσει ερωτήσεις της μορφής είναι αυτή η λέξη;
Έτσι θέλετε να εφαρμόσουν ένα ορθογράφο, απλά
σαν μια φυσική λεξικό ότι μπορείτε να δείτε τα πράγματα μέσα.
Ας υποθέσουμε ότι επρόκειτο να το κάνουμε αυτό με μια σειρά.
Θα μπορούσα να το κάνουμε αυτό.
>> Και ας υποθέσουμε ότι οι λέξεις είναι μήλο και μπανάνα και πεπόνι.
Και δεν μπορώ να σκεφτώ φρούτα που ξεκινούν με d, έτσι είμαστε απλά
πρόκειται να έχει τρία φρούτα.
Έτσι, αυτό είναι μια σειρά, και είμαστε αποθήκευση όλων αυτών των λέξεων
σε αυτό το λεξικό ως πίνακας.
Το ερώτημα, λοιπόν, είναι πώς αλλιώς θα μπορούσε να αποθηκεύσει αυτές τις πληροφορίες;
>> Λοιπόν, είμαι το είδος της εξαπάτησης εδώ, επειδή καθένα από αυτά τα γράμματα της λέξης
Είναι πραγματικά ένα άτομο byte.
Έτσι, αν πραγματικά ήθελε να είναι nit-επιλεκτικοί, θα ήθελα πραγματικά
να διαιρώντας αυτό επάνω σε πολλά μικρότερα κομμάτια της μνήμης,
και θα μπορούσαμε να κάνουμε ακριβώς αυτό.
Αλλά θα πάμε να τρέχει σε το ίδιο πρόβλημα όπως και πριν.
Τι θα συμβεί αν, όπως Merriam Webster ή Οξφόρδης κάνει κάθε year-- προσθέτουν λέξεις
στην dictionary-- δεν το κάνουμε θέλουν απαραιτήτως να ζωγραφίσει τον εαυτό μας
σε μια γωνία με μια σειρά;
>> Έτσι, αντ 'αυτού, ίσως μια πιο έξυπνη προσέγγιση είναι να τεθεί το μήλο στο δικό κόμβο ή το κουτί της,
όπως θα λέγαμε, μπανάνα, και τότε εδώ έχουμε το πεπόνι.
Και εγχόρδων εμείς αυτά τα πράγματα μαζί.
Έτσι, αυτό είναι ο πίνακας, και αυτή είναι η συνδεδεμένη λίστα.
Εάν δεν μπορείτε να εντελώς δείτε, απλά λέει "σειρά", και αυτό λέει "λίστα".
>> Έτσι έχουμε την ίδια ακριβής ζητήματα όπως πριν,
σύμφωνα με την οποία έχουμε τώρα δυναμισμό στην συνδεδεμένη λίστα μας.
Αλλά έχουμε μια αρκετά αργή λεξικό.
Ας υποθέσουμε ότι θέλετε να αναζητήσετε μια λέξη.
Θα μπορούσε να μου πάρει μεγάλο O του n βήματα, γιατί η λέξη θα μπορούσε
είναι σε όλη τη διαδρομή στο τέλος της η λίστα, όπως και το πεπόνι.
Και αποδεικνύεται ότι στον προγραμματισμό, το είδος
το Άγιο Δισκοπότηρο των δεδομένων δομές, είναι κάτι
ότι δίνει σταθερή χρόνου, όπως μια σειρά
αλλά ότι εξακολουθεί να σας δίνει δυναμισμό.
>> Έτσι, μπορούμε να έχουμε το καλύτερο και των δύο κόσμων;
Και πράγματι, υπάρχει κάτι ονομάζεται ο πίνακας κατακερματισμού
που σας επιτρέπει να κάνετε ακριβώς ότι, έστω και κατά προσέγγιση.
Ένας πίνακας hash είναι ένα φανταχτερό δομή δεδομένων που θα
μπορεί να σκεφτεί ως συνδυασμός ενός array--
και πάω να το συντάξει όπως this-- και συνδεδεμένες λίστες
ότι εγώ θα επιστήσω σαν αυτό εδώ.
>> Και ο τρόπος που αυτό το πράγμα έργα είναι η εξής.
Εάν αυτό now-- hash table-- είναι η τρίτη δομή δεδομένων μου,
και θέλω να αποθηκεύσετε λέξεις σε αυτό, εγώ δεν κάνω
θέλετε να αποθηκεύσετε μόνο όλα τα λέξεις πλάτη με πλάτη με πλάτη με πλάτη.
Θέλω να αξιοποιήσουν κάποια κομμάτι των πληροφοριών
για τις λέξεις που θα σας αφήσει Θέλω να το πάρει, όπου είναι πιο γρήγορο.
>> Έτσι, δίνεται το μήλο λέξεις και μπανάνα και πεπόνι,
Έχω σκόπιμα επέλεξε αυτές τις λέξεις.
Γιατί;
Ποιο είναι το είδος της θεμελιωδώς διαφορετικά για τα τρία;
Ποιο είναι το προφανές;
Αρχίζουν με διαφορετικά γράμματα.
>> Έτσι, ξέρετε τι;
Αντί να βάλει όλα τα λόγια μου το ίδιο κουβά, να το πω έτσι,
όπως σε μια μεγάλη λίστα, γιατί να μην το κάνουμε Θα προσπαθήσουμε τουλάχιστον μια βελτιστοποίηση
και να κάνουν λίστες μου 1/26 εφ.
Ένα συναρπαστικό βελτιστοποίησης θα μπορούσε να είναι γιατί δεν το κάνουν
I-- κατά την εισαγωγή μιας λέξης σε αυτή τη δομή δεδομένων,
στη μνήμη του υπολογιστή, γιατί Δεν μπορώ να θέσει όλες τις λέξεις «ένα» εδώ,
όλες οι «β» λόγια εδώ, και όλα τα «c» λέξεις εδώ;
Έτσι, αυτό καταλήγει βάζοντας ένα μήλο Εδώ, μπανάνα εδώ, πεπόνι εδώ,
και ούτω καθεξής.
>> Και εάν έχω μια πρόσθετη λέξη like-- τι άλλο;
Μήλο, μπανάνα, αχλάδι.
Όποιος σκεφτεί ενός φρούτου που ξεκινά με α, β, ή γ;
Blueberry-- τέλεια.
Αυτό πρόκειται να τελειώσει εδώ.
Και έτσι φαίνεται να έχουμε μια οριακά καλύτερη λύση,
γιατί τώρα αν θέλω για να αναζητήσετε το μήλο, θα
first-- δεν το κάνω μόνο κατάδυση στη δομή των δεδομένων μου.
Δεν βουτήξει στη μνήμη του υπολογιστή μου.
Θα εξετάσουμε πρώτα το πρώτο γράμμα.
>> Και αυτό είναι ό, τι έναν υπολογιστή επιστήμονας θα έλεγε.
Μπορείτε hash στη δομή των δεδομένων σας.
Μπορείτε να πάρετε τη συμβολή σας, η οποία με τη η υπόθεση αυτή είναι μια λέξη σαν μήλο.
Μπορείτε να το αναλύσουμε, κοιτάζοντας το πρώτο γράμμα σε αυτή την περίπτωση,
το hashing με αυτόν τον τρόπο.
Κατακερματισμός είναι ένας γενικός όρος σύμφωνα με την οποία πάρετε κάτι σαν είσοδο
και θα παράγει κάποια έξοδο.
Και η έξοδος από το ότι περίπτωση είναι η θέση
που θέλετε να αναζητήσετε, το πρώτο θέση, δεύτερη θέση, τρίτη.
Έτσι, η είσοδος είναι το μήλο, η έξοδος είναι πρώτη.
Η είσοδος είναι μπανάνα, η εξόδου θα πρέπει να είναι δεύτερη.
Η είσοδος είναι πεπόνι, η έξοδος θα πρέπει να είναι τρίτο.
Η είσοδος είναι βατόμουρου, η εξόδου θα πρέπει και πάλι να είναι δεύτερη.
Και αυτό είναι που σας βοηθά να πάρετε συντομεύσεις μέσα από τη μνήμη σας
προκειμένου να πάρει τα λόγια ή δεδομένα πιο αποτελεσματικά.
>> Τώρα αυτό μειώνει το χρόνο μας δυνητικά από όσο ένας στους 26,
γιατί αν υποθέσουμε ότι έχετε έχουν ως πολλά "Α" λέξεις όπως "z"
λέξεις λέξεις "q", η οποία Δεν είναι πραγματικά realistic--
θα πάμε να έχουν παραποιήσει ολόκληρη ορισμένες επιστολές του alphabet--
αλλά αυτό θα είναι μια σταδιακή προσέγγιση που δεν επιτρέπει
μπορείτε να πάρετε τα λόγια πολύ πιο γρήγορα.
Και στην πραγματικότητα, ένα εξελιγμένο προγράμματος, η Googles του κόσμου,
η Facebooks του world-- θα χρησιμοποιήσει έναν πίνακα κατακερματισμού
για πολλούς διαφορετικούς σκοπούς.
Αλλά δεν θα ήταν τόσο αφελής ώστε να εξετάσουμε μόνο το πρώτο γράμμα
το μήλο ή μπανάνα ή αχλάδι ή πεπόνι,
επειδή όπως μπορείτε να δείτε αυτά λίστες θα μπορούσε να πάρει ακόμα καιρό.
>> Και έτσι αυτό μπορεί να είναι ακόμα είδος της linear-- έτσι το είδος της αργή,
όπως και με το μεγάλο Ο Ν ότι συζητήσαμε νωρίτερα.
Έτσι, αυτό που πραγματικά καλό πίνακα κατακερματισμού θα do-- θα έχει μια πολύ μεγαλύτερη ποικιλία.
Και θα χρησιμοποιήσει ένα πολύ πιο εξελιγμένα συνάρτηση κατακερματισμού,
έτσι ώστε να μην εξετάσουμε μόνο το "α."
Ίσως φαίνεται στο "A-π-π-λ-ε» και κατά κάποιο τρόπο μετατρέπει αυτά τα πέντε γράμματα
στην τοποθεσία όπου μήλο θα πρέπει να αποθηκεύονται.
Εμείς απλά αφελώς χρησιμοποιώντας το γράμμα «a» μόνη της, γιατί είναι όμορφο και απλό.
>> Αλλά ένα πίνακα κατακερματισμού, σε το τέλος, μπορείτε να σκεφτείτε
του ως συνδυασμός ένας πίνακας, καθένα από τα οποία
έχει μια συνδεδεμένη λίστα που ιδανική θα πρέπει να είναι όσο το δυνατόν συντομότερη.
Και αυτό δεν είναι μια προφανής λύση.
Στην πραγματικότητα, ένα μεγάλο μέρος της μικρορύθμιση ότι συνεχίζεται κάτω από την κουκούλα, όταν
εφαρμογή αυτών των ειδών εξελιγμένες δομές δεδομένων
είναι ό, τι είναι το σωστό μήκος του πίνακα;
Ποια είναι η λειτουργία σωστό hash;
Πώς μπορείτε να αποθηκεύσετε τα πράγματα στη μνήμη;
>> Αλλά συνειδητοποιούν πόσο γρήγορα Αυτό το είδος της συζήτησης
κλιμακώθηκε, είτε μέχρι τώρα ότι αυτό είναι το είδος πάνω από το κεφάλι του σε αυτό το σημείο, το οποίο
είναι μια χαρά.
Αλλά αρχίσαμε, ανάκληση, με πραγματικά κάτι χαμηλού επιπέδου και των ηλεκτρονικών.
Και έτσι αυτό πάλι είναι αυτό το θέμα της αφαίρεσης,
όπου μόλις αρχίσετε να πάρει για χορηγείται, εντάξει, έχω it-- πήρα υπάρχει
φυσική μνήμη, εντάξει, το πήρα, κάθε φυσική τοποθεσία έχει μια διεύθυνση,
Εντάξει, το πήρα, μπορώ να εκπροσωπώ αυτές οι διευθύνσεις ως arrows--
μπορείτε να ξεκινήσετε πολύ γρήγορα για να έχουν πιο εξελιγμένα συζητήσεις που
στο τέλος φαίνεται να μας επιτρέπουν για την επίλυση προβλημάτων όπως η αναζήτηση
και διαλογή πιο αποτελεσματικά.
Και να είστε βέβαιοι, too-- επειδή πιστεύω ότι αυτό
είναι η βαθύτερη που έχουμε πάει σε μερικά από αυτά τα θέματα CS proper-- έχουμε
γίνει σε μια μέρα και ένα μισό στο αυτό το σημείο αυτό μπορείτε να συνήθως κάνει πάνω
η πορεία οκτώ εβδομάδες σε ένα εξάμηνο.
>> Οποιεσδήποτε ερωτήσεις σχετικά με αυτά;
Όχι?
Εντάξει.
Λοιπόν, γιατί δεν σταματάμε εκεί, ξεκινήσετε το γεύμα λίγα λεπτά νωρίτερα,
επαναλάβει σε μόλις περίπου μία ώρα;
Και εγώ θα σταθώ για ένα κομμάτι με τις ερωτήσεις.
Στη συνέχεια, Πάω να πρέπει να πάει να λάβει ένα ζευγάρι κλήσεις αν αυτό είναι εντάξει.
Θα ενεργοποιήσετε κάποια μουσική, εν τω μεταξύ, αλλά το μεσημεριανό γεύμα θα πρέπει να είναι γύρω από τη γωνία.