1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι αυτό είναι
CS50 Αυτό είναι το τέλος της εβδομάδας πέντε.

3
00:00:15,860 --> 00:00:19,220
Και υπενθυμίζουν ότι η τελευταία φορά που
άρχισε να ψάχνει στο εκτροφέα δεδομένων

4
00:00:19,220 --> 00:00:22,310
δομές που άρχισε να λύσει
προβλήματα, που άρχισαν να εισάγουν

5
00:00:22,310 --> 00:00:25,640
νέα προβλήματα, αλλά το κλειδί σε αυτό
Ήταν το είδος του περάσματος ότι εμείς

6
00:00:25,640 --> 00:00:27,940
άρχισε να κάνει από κόμβο σε κόμβο.

7
00:00:27,940 --> 00:00:30,085
Έτσι, αυτό βέβαια είναι
ένα μεμονωμένα συνδεδεμένη λίστα.

8
00:00:30,085 --> 00:00:31,960
Και από μόνες που συνδέονται,
Θέλω να πω ότι υπάρχει μόνο μία

9
00:00:31,960 --> 00:00:33,380
νήμα μεταξύ κάθε μία από αυτές κόμβων.

10
00:00:33,380 --> 00:00:35,890
Βγάζει μπορείτε να κάνετε εκτροφέα
πράγματα όπως διπλά συνδεδεμένες λίστες

11
00:00:35,890 --> 00:00:38,470
σύμφωνα με την οποία έχετε ένα βέλος
πηγαίνει προς τις δύο κατευθύνσεις, η οποία

12
00:00:38,470 --> 00:00:40,320
μπορεί να βοηθήσει με συγκεκριμένες αποδόσεις.

13
00:00:40,320 --> 00:00:42,000
Αλλά αυτό έλυσε το πρόβλημα;

14
00:00:42,000 --> 00:00:43,500
Τι πρόβλημα είχε αυτό το λύσει;

15
00:00:43,500 --> 00:00:46,620
Γιατί μας νοιάζει τη Δευτέρα;

16
00:00:46,620 --> 00:00:49,820
Γιατί, θεωρητικά, δεν φροντίζουμε τη Δευτέρα;

17
00:00:49,820 --> 00:00:50,630
Τι κάνει?

18
00:00:50,630 --> 00:00:51,950
>> Κοινό: Μπορούμε να αλλάξετε το μέγεθος δυναμικά.

19
00:00:51,950 --> 00:00:53,740
>> ΟΜΙΛΗΤΗΣ 1: Εντάξει, ώστε να μπορούμε να
δυναμικά αλλάξετε το μέγεθός του.

20
00:00:53,740 --> 00:00:54,710
Μπράβο τους δυο σας.

21
00:00:54,710 --> 00:00:57,560
Έτσι, μπορείτε να αλλάξετε το μέγεθος δυναμικά αυτή
δομή δεδομένων, ενώ μια σειρά,

22
00:00:57,560 --> 00:01:00,760
ανάκληση, θα πρέπει να γνωρίζουμε
εκ των προτέρων πόσο χώρο θέλετε

23
00:01:00,760 --> 00:01:03,870
και αν χρειάζεστε λίγο περισσότερο
χώρο, είστε το είδος του από την τύχη.

24
00:01:03,870 --> 00:01:05,560
Θα πρέπει να δημιουργήσετε μια εντελώς νέα σειρά.

25
00:01:05,560 --> 00:01:07,893
Θα πρέπει να μετακινήσετε όλα σας
δεδομένα από το ένα στο άλλο,

26
00:01:07,893 --> 00:01:10,600
τελικά ελευθερώσει την παλιά σειρά
αν μπορείτε, και στη συνέχεια να προχωρήσει.

27
00:01:10,600 --> 00:01:13,891
Ποια ακριβώς αισθάνεται πολύ δαπανηρή και πολύ
αναποτελεσματική, και πράγματι μπορεί να είναι.

28
00:01:13,891 --> 00:01:14,890
Αλλά αυτό δεν είναι όλα καλά.

29
00:01:14,890 --> 00:01:18,180
Έχουμε πληρώσει ένα τίμημα, τι ήταν ένα
από τις πιο προφανείς τις τιμές μας

30
00:01:18,180 --> 00:01:20,550
πληρώσουν χρησιμοποιώντας μια συνδεδεμένη λίστα;

31
00:01:20,550 --> 00:01:22,825
>> Κοινό: Πρέπει να χρησιμοποιήσουμε
διπλό χώρο για κάθε μία.

32
00:01:22,825 --> 00:01:25,200
ΟΜΙΛΗΤΗΣ 1: Ναι, γι 'αυτό χρειαζόμαστε
τουλάχιστον διπλάσιο χώρο.

33
00:01:25,200 --> 00:01:27,700
Στην πραγματικότητα, κατάλαβα αυτή η εικόνα του
έστω και λίγο παραπλανητικό,

34
00:01:27,700 --> 00:01:32,200
γιατί σε CS50 IDE σε πολλά σύγχρονα
υπολογιστές, ένας δείκτης ή μια διεύθυνση

35
00:01:32,200 --> 00:01:33,700
δεν είναι στην πραγματικότητα τέσσερεις bytes.

36
00:01:33,700 --> 00:01:36,090
Είναι πολύ συχνά αυτά
οκτώ ημέρες bytes, το οποίο

37
00:01:36,090 --> 00:01:38,530
σημαίνει το κάτω μέρος πιο
ορθογώνια υπάρχει στην πραγματικότητα

38
00:01:38,530 --> 00:01:40,900
είναι το είδος του δύο φορές
μεγάλο όσο αυτό που έχω σχεδιάσει,

39
00:01:40,900 --> 00:01:44,409
πράγμα που σημαίνει ότι είστε χρησιμοποιώντας τρεις φορές
πολύ χώρο καθώς μπορεί να έχουμε διαφορετικά.

40
00:01:44,409 --> 00:01:46,700
Τώρα, την ίδια στιγμή, είμαστε
εξακολουθεί να μιλάει bytes, έτσι δεν είναι;

41
00:01:46,700 --> 00:01:49,140
Εμείς δεν μιλάμε απαραίτητα
megabytes ή gigabytes,

42
00:01:49,140 --> 00:01:51,000
εκτός αν αυτές οι δομές δεδομένων πάρει μεγάλες.

43
00:01:51,000 --> 00:01:54,510
>> Και έτσι σήμερα μπορούμε να αρχίσουμε να εξετάζουμε
πώς μπορούμε να διερευνήσει δεδομένα

44
00:01:54,510 --> 00:01:57,310
πιο αποτελεσματικά εάν σε
Πράγματι τα δεδομένα μεγαλώνει.

45
00:01:57,310 --> 00:02:00,360
Αλλά ας προσπαθήσουμε να canonicalize
οι πρώτες πράξεις

46
00:02:00,360 --> 00:02:02,460
ότι μπορείτε να κάνετε σε αυτά
είδη δομών δεδομένων.

47
00:02:02,460 --> 00:02:04,790
Έτσι, κάτι σαν ένα συνδεδεμένο
Λίστα υποστηρίζει σε γενικές γραμμές

48
00:02:04,790 --> 00:02:07,514
λειτουργίες όπως διαγραφή,
εισάγετε, και αναζήτηση.

49
00:02:07,514 --> 00:02:08,639
Και τι εννοώ με αυτό;

50
00:02:08,639 --> 00:02:11,222
Αυτό ακριβώς σημαίνει ότι συνήθως,
αν οι άνθρωποι χρησιμοποιούν συνδεδεμένη λίστα,

51
00:02:11,222 --> 00:02:14,287
οι ίδιοι ή κάποιος άλλος έχει υλοποιηθεί
λειτουργίες όπως η διαγραφή, εισαγωγή,

52
00:02:14,287 --> 00:02:16,120
και αναζήτησης, ώστε να μπορείτε να
πραγματικά να κάνουμε κάτι

53
00:02:16,120 --> 00:02:18,030
χρήσιμο με τη δομή δεδομένων.

54
00:02:18,030 --> 00:02:20,760
Έτσι, ας ρίξουμε μια γρήγορη ματιά
το πώς θα μπορούσαμε να εφαρμόσουν

55
00:02:20,760 --> 00:02:24,530
μερικά κωδικό για μια συνδεδεμένη λίστα ως εξής.

56
00:02:24,530 --> 00:02:27,885
>> Έτσι, αυτό είναι μόνο ένα τμήμα κώδικα C,
ούτε καν ένα πλήρες πρόγραμμα

57
00:02:27,885 --> 00:02:29,260
ότι πραγματικά γρήγορα χτυπημένη.

58
00:02:29,260 --> 00:02:32,300
Δεν είναι σε απευθείας σύνδεση στην κατανομή
κώδικα, διότι δεν θα λειτουργεί πραγματικά.

59
00:02:32,300 --> 00:02:33,790
Αλλά έχω παρατηρήσει μόνο
με ένα σχόλιο, δήλωσε,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, υπάρχει κάτι
εκεί, dot dot dot, κάτι εκεί.

61
00:02:36,130 --> 00:02:38,410
Και ας δούμε
ποια είναι τα ζουμερά μέρη είναι.

62
00:02:38,410 --> 00:02:40,790
Έτσι, στη γραμμή των τριών,
Υπενθυμίζω ότι αυτό είναι τώρα

63
00:02:40,790 --> 00:02:45,960
προτείναμε την κήρυξη κόμβο τελευταία
ώρα, ένα από αυτά τα ορθογώνια αντικείμενα.

64
00:02:45,960 --> 00:02:48,790
Έχει μια int που θα καλέσουμε Ν,
αλλά θα μπορούσαμε να το ονομάσουμε κάτι,

65
00:02:48,790 --> 00:02:51,920
και, στη συνέχεια, ένα αστέρι struct node ονομάζεται επόμενη.

66
00:02:51,920 --> 00:02:55,520
Και ακριβώς για να είναι σαφές, ότι η δεύτερη
γραμμή, on line έξι, τι είναι αυτό;

67
00:02:55,520 --> 00:02:57,930
Τι είναι αυτό που κάνει για μας;

68
00:02:57,930 --> 00:03:01,044
Επειδή σίγουρα μοιάζει περισσότερο
κρυπτικό από το συνηθισμένο μεταβλητές μας.

69
00:03:01,044 --> 00:03:02,740
>> Κοινό: Κάνει το μετακινήσετε πάνω από ένα.

70
00:03:02,740 --> 00:03:04,650
>> ΟΜΙΛΗΤΗΣ 1: Κάνει το μετακινήσετε πάνω από ένα.

71
00:03:04,650 --> 00:03:08,580
Και για να είμαι πιο ακριβής,
θα αποθηκεύσει τη διεύθυνση

72
00:03:08,580 --> 00:03:11,582
του κόμβου που είναι γραφτό να γίνει
σημασιολογικά δίπλα του, σωστά;

73
00:03:11,582 --> 00:03:13,540
Έτσι, δεν πρόκειται να
κατ 'ανάγκην κάτι κινείται.

74
00:03:13,540 --> 00:03:15,290
Είναι ακριβώς πρόκειται να
αποθηκεύσετε μια τιμή, η οποία είναι

75
00:03:15,290 --> 00:03:17,170
πρόκειται να είναι η διεύθυνση
από κάποιο άλλο κόμβο,

76
00:03:17,170 --> 00:03:20,810
και γι 'αυτό έχουμε πει struct
κόμβο αστέρι, το αστέρι που δηλώνει

77
00:03:20,810 --> 00:03:22,370
ένα δείκτη ή μια διεύθυνση.

78
00:03:22,370 --> 00:03:26,390
Εντάξει, έτσι και τώρα, αν υποθέσουμε ότι έχουμε
Αυτό το Ν στη διάθεσή μας, και ας

79
00:03:26,390 --> 00:03:29,490
υποθέσουμε ότι κάποιος άλλος έχει
παρεμβάλλεται ένα σωρό ακεραίων

80
00:03:29,490 --> 00:03:30,400
σε μια συνδεδεμένη λίστα.

81
00:03:30,400 --> 00:03:35,640
Και αυτό είναι συνδεδεμένη λίστα
τόνισε από κάποιο σημείο

82
00:03:35,640 --> 00:03:39,040
μια μεταβλητή που ονομάζεται λίστα που είναι
πέρασε εδώ ως παράμετρος,

83
00:03:39,040 --> 00:03:43,120
πώς μπορώ να πάω για γραμμή
14 εφαρμογή αναζήτησης;

84
00:03:43,120 --> 00:03:45,990
Με άλλα λόγια, αν είμαι εκτελεστικών
η λειτουργία του οποίου σκοπός στη ζωή

85
00:03:45,990 --> 00:03:48,889
είναι να λάβει μια int και στη συνέχεια το
ξεκινώντας από μια συνδεδεμένη λίστα,

86
00:03:48,889 --> 00:03:50,430
ότι είναι ένας δείκτης για τη συνδεδεμένη λίστα.

87
00:03:50,430 --> 00:03:52,992
Όπως και το πρώτο, ο οποίος πιστεύω ότι ο David
Ήταν εθελοντής μας την Δευτέρα,

88
00:03:52,992 --> 00:03:54,700
έδειχνε σε
ολόκληρη η συνδεδεμένη λίστα,

89
00:03:54,700 --> 00:03:57,820
είναι σαν να περνάτε
David σε όσο το επιχείρημά μας εδώ.

90
00:03:57,820 --> 00:03:59,990
Πώς θα πάτε για την διάσχιση αυτή τη λίστα;

91
00:03:59,990 --> 00:04:04,640
Λοιπόν, αποδεικνύεται ότι, ακόμη και αν
δείκτες είναι σχετικά νέα τώρα σε μας,

92
00:04:04,640 --> 00:04:07,010
μπορούμε να το κάνουμε αυτό σχετικά
ευθέως.

93
00:04:07,010 --> 00:04:09,500
>> Πάω να πάει μπροστά και να
να κηρύξει μια προσωρινή μεταβλητή που

94
00:04:09,500 --> 00:04:12,364
με σύμβαση πρόκειται ακριβώς
να ονομάζεται δείκτης ή PTR,

95
00:04:12,364 --> 00:04:14,030
αλλά θα μπορούσατε να το ονομάσετε οτιδήποτε θέλετε.

96
00:04:14,030 --> 00:04:16,470
Και Πάω να προετοιμαστεί
αυτό στην αρχή της λίστας.

97
00:04:16,470 --> 00:04:20,050
Έτσι, μπορείτε να σκεφτείτε το είδος αυτό
όπως μου το δάσκαλο την άλλη μέρα,

98
00:04:20,050 --> 00:04:23,580
είδος δείχνει σε κάποιον
μεταξύ των ανθρώπων μας ως εθελοντές.

99
00:04:23,580 --> 00:04:26,470
Έτσι, είμαι μια προσωρινή μεταβλητή που είναι
απλά δείχνοντας το ίδιο πράγμα

100
00:04:26,470 --> 00:04:31,390
ότι συμπτωματικά μας το όνομα
εθελοντής Δαβίδ επίσης να επισημανθούν.

101
00:04:31,390 --> 00:04:35,440
Τώρα, ενώ ο δείκτης είναι
Δεν μηδενική, γιατί ανάκληση

102
00:04:35,440 --> 00:04:40,350
null ότι είναι κάποια ιδιαίτερη αξία φρουρού
η οριοθετεί το τέλος του καταλόγου,

103
00:04:40,350 --> 00:04:44,280
Έτσι, ενώ δεν είμαι δείχνοντας το
εδάφους όπως και την περασμένη εθελοντή μας

104
00:04:44,280 --> 00:04:47,190
ήταν, ας πάμε μπροστά
και να κάνουμε το εξής.

105
00:04:47,190 --> 00:04:51,820
Αν pointer-- και τώρα έχω το είδος του θέλουν
να κάνουμε ό, τι κάναμε με τον μαθητή

106
00:04:51,820 --> 00:04:57,410
structure-- εάν δείκτη κουκκίδα δίπλα
equals-- μάλλον, αν ο δείκτης dot Ν ισούται

107
00:04:57,410 --> 00:05:02,290
ισούται η μεταβλητή Ν, ο
επιχείρημα που έχει περάσει μέσα,

108
00:05:02,290 --> 00:05:05,370
Στη συνέχεια θέλω να πάω μπροστά
και να πω επιστρέψει true.

109
00:05:05,370 --> 00:05:11,020
Έχω βρεθεί ο αριθμός Ν εσωτερικό του
ένας από τους κόμβους των συνδεδεμένων λίστα μου.

110
00:05:11,020 --> 00:05:13,500
Αλλά η τελεία δεν είναι πλέον
λειτουργεί στο πλαίσιο αυτό,

111
00:05:13,500 --> 00:05:17,260
επειδή δείκτη, PTR, είναι
πράγματι ένας δείκτης, μια διεύθυνση,

112
00:05:17,260 --> 00:05:20,632
μπορούμε πραγματικά να θαυμάσια
χρησιμοποιήσει τελικά ένα κομμάτι της σύνταξης

113
00:05:20,632 --> 00:05:22,590
ότι το είδος των σημάτων
διαισθητική λογική και πραγματικότητα

114
00:05:22,590 --> 00:05:27,870
χρησιμοποιήστε ένα βέλος εδώ, πράγμα που σημαίνει να πάει από
ότι η διεύθυνση στο ακέραιο εκεί.

115
00:05:27,870 --> 00:05:30,160
Γι 'αυτό είναι πολύ παρόμοια
πνεύματος στο χειριστή τελεία,

116
00:05:30,160 --> 00:05:33,860
αλλά επειδή δείκτης δεν είναι ένας δείκτης
και όχι η ίδια η πραγματική struct,

117
00:05:33,860 --> 00:05:35,380
εμείς απλά χρησιμοποιήστε το βέλος.

118
00:05:35,380 --> 00:05:40,620
>> Έτσι, εάν η τρέχουσα κόμβος που εγώ, ο
προσωρινή μεταβλητή, είμαι δείχνοντας

119
00:05:40,620 --> 00:05:43,060
δεν είναι Ν, τι θέλω να κάνω;

120
00:05:43,060 --> 00:05:45,910
Λοιπόν, με εθελοντές ανθρώπους μου
ότι είχαμε εδώ τις προάλλες,

121
00:05:45,910 --> 00:05:49,710
εάν η πρώτη μου άνθρωπος δεν είναι αυτός που
θέλετε, και ίσως ο δεύτερος άνθρωπος δεν είναι

122
00:05:49,710 --> 00:05:52,660
το ένα που θέλω, και η τρίτη, που
Πρέπει να τηρούνται φυσικά κινείται.

123
00:05:52,660 --> 00:05:54,690
Όπως και πώς μπορώ να το βήμα σε μια λίστα;

124
00:05:54,690 --> 00:05:57,470
Όταν σας είχαμε μια σειρά,
έκανε ακριβώς όπως εγώ συν συν.

125
00:05:57,470 --> 00:06:03,660
Αλλά στην περίπτωση αυτή, αρκεί να
κάνει δείκτη, παίρνει, το δείκτη, το επόμενο.

126
00:06:03,660 --> 00:06:07,580
Με άλλα λόγια, το επόμενο πεδίο
είναι σαν όλα τα αριστερά χέρια

127
00:06:07,580 --> 00:06:10,880
ότι η ανθρώπινη εθελοντές μας την Δευτέρα
χρησιμοποιούσαν το σημείο σε κάποιο άλλο κόμβο.

128
00:06:10,880 --> 00:06:12,890
Όσοι ήταν δίπλα τους γείτονές τους.

129
00:06:12,890 --> 00:06:17,060
>> Έτσι, αν θέλω να το βήμα μέσω αυτού του καταλόγου,
Δεν μπορώ να κάνω συν συν πια,

130
00:06:17,060 --> 00:06:20,120
Έχω αντί να πω
Εγώ, ο δείκτης, πρόκειται

131
00:06:20,120 --> 00:06:24,650
να ισούται με ό, τι το επόμενο πεδίο είναι,
Το επόμενο πεδίο είναι, το επόμενο πεδίο είναι,

132
00:06:24,650 --> 00:06:28,350
μετά από όλα αυτά τα αριστερά χέρια
ότι είχαμε στη σκηνή κατάδειξης

133
00:06:28,350 --> 00:06:30,000
σε κάποιες μεταγενέστερες τιμές.

134
00:06:30,000 --> 00:06:32,590
Και αν έχω περάσει
ότι ολόκληρη επανάληψη,

135
00:06:32,590 --> 00:06:39,330
και, τέλος, χτύπησα null δεν έχουν
Ν βρεθεί ακόμα, απλά επιστρέφει false.

136
00:06:39,330 --> 00:06:44,100
Έτσι και πάλι, όλα αυτά που κάνουμε εδώ,
σύμφωνα με την εικόνα πριν από λίγο,

137
00:06:44,100 --> 00:06:47,840
ξεκινά από δείχνοντας το
αρχή της λίστας προφανώς.

138
00:06:47,840 --> 00:06:50,970
Και τότε μπορώ να ελέγξω, είναι η αξία
Ψάχνω για ίσο με εννέα;

139
00:06:50,970 --> 00:06:52,650
Αν ναι, θα επιστρέψει αλήθεια και είμαι γίνει.

140
00:06:52,650 --> 00:06:56,450
Αν όχι, μπορώ να ενημερώσω το χέρι μου,
AKA δείκτη, με το σημείο

141
00:06:56,450 --> 00:06:59,540
στη θέση της επόμενης βέλους, και
Στη συνέχεια τοποθεσία της επόμενης βέλους,

142
00:06:59,540 --> 00:07:00,480
και το επόμενο.

143
00:07:00,480 --> 00:07:03,770
Είμαι απλά περπατώντας μέσα από αυτή τη σειρά.

144
00:07:03,770 --> 00:07:06,010
>> Έτσι και πάλι, ποιος νοιάζεται;

145
00:07:06,010 --> 00:07:07,861
Όπως και τι είναι αυτό το ένα συστατικό για;

146
00:07:07,861 --> 00:07:10,360
Λοιπόν, ας θυμηθούμε ότι εισαγάγαμε
η έννοια της στοίβας, η οποία

147
00:07:10,360 --> 00:07:15,400
είναι ένα αφηρημένο τύπο δεδομένων στο βαθμό που αυτό είναι
δεν είναι ένα πράγμα C, δεν είναι ένα πράγμα CS50,

148
00:07:15,400 --> 00:07:19,430
είναι μια αφηρημένη ιδέα, η ιδέα της
στοίβαξη πράγματα ένα πάνω στο άλλο

149
00:07:19,430 --> 00:07:21,820
ότι μπορεί να εφαρμοστεί σε
τσαμπιά από διαφορετικούς τρόπους.

150
00:07:21,820 --> 00:07:25,600
Και ένας τρόπος που προτάθηκε ήταν με
ένας πίνακας, ή με μία συνδεδεμένη λίστα.

151
00:07:25,600 --> 00:07:29,570
Και αποδεικνύεται ότι κανονικώς, ένα
στοίβα υποστηρίζει τουλάχιστον δύο πράξεις.

152
00:07:29,570 --> 00:07:32,320
Και οι λέξεις buzz είναι να ωθεί, να
ωθήσει κάτι στη στοίβα,

153
00:07:32,320 --> 00:07:34,770
σαν ένα καινούργιο δίσκο στο
τραπεζαρία, ή ποπ,

154
00:07:34,770 --> 00:07:39,000
που σημαίνει να αφαιρέσετε το ανώτερο
δίσκο από τη στοίβα στην τραπεζαρία

155
00:07:39,000 --> 00:07:41,500
αίθουσα, και τότε ίσως κάποιοι
άλλες λειτουργίες, όπως καλά.

156
00:07:41,500 --> 00:07:45,770
Λοιπόν, πώς θα μπορούσαμε να καθορίσει τη δομή
ότι είμαστε ζητούν τώρα μια στοίβα;

157
00:07:45,770 --> 00:07:50,020
>> Λοιπόν, έχουμε όλοι την απαιτούμενη
σύνταξη στη διάθεσή μας στην Γ λέω,

158
00:07:50,020 --> 00:07:53,830
να μου δώσει έναν ορισμό του τύπου
ένα struct εσωτερικό του μια στοίβα,

159
00:07:53,830 --> 00:07:58,030
Πάω να πω είναι ένας πίνακας, ενός
σωρό αριθμούς και στη συνέχεια το μέγεθος.

160
00:07:58,030 --> 00:08:00,930
Έτσι με άλλα λόγια, αν θέλω
να εφαρμόσουν αυτό τον κωδικό,

161
00:08:00,930 --> 00:08:03,830
επιτρέψτε μου να πάω και ακριβώς το είδος του
αντλήσει ό, τι λέει αυτό.

162
00:08:03,830 --> 00:08:06,317
Έτσι, αυτό που λέει, να μου δώσει μια
δομή που πήρε μια σειρά,

163
00:08:06,317 --> 00:08:09,400
και δεν ξέρω τι είναι χωρητικότητας,
Είναι προφανώς μια σταθερά που έχω

164
00:08:09,400 --> 00:08:10,858
ορίζεται αλλού, και αυτό είναι εντάξει.

165
00:08:10,858 --> 00:08:15,260
Αλλά ας υποθέσουμε ότι είναι μόνο μία,
δύο, τρία, τέσσερα, πέντε.

166
00:08:15,260 --> 00:08:16,700
Έτσι χωρητικότητα είναι 5.

167
00:08:16,700 --> 00:08:21,730
Αυτό το στοιχείο μέσα μου
δομή θα ονομάζεται αριθμούς.

168
00:08:21,730 --> 00:08:24,020
Και τότε θα χρειαστείτε ένα
άλλη μεταβλητή προφανώς

169
00:08:24,020 --> 00:08:27,814
ονομάζεται το μέγεθος που αρχικά Πάω
να ορίζουν έχει προετοιμαστεί με μηδέν.

170
00:08:27,814 --> 00:08:29,730
Αν δεν υπάρχει τίποτα
η στοίβα, το μέγεθος είναι μηδέν,

171
00:08:29,730 --> 00:08:31,420
και είναι σκουπίδια τιμές σε αριθμούς.

172
00:08:31,420 --> 00:08:33,450
Δεν έχω ιδέα τι είναι εκεί ακριβώς ακόμα.

173
00:08:33,450 --> 00:08:36,059
>> Έτσι, αν θέλω να ωθήσει
κάτι στη στοίβα,

174
00:08:36,059 --> 00:08:40,780
Υποθέτω Καλώ την ώθηση λειτουργία, και
Λέω ωθήσει 50, όπως και ο αριθμός 50,

175
00:08:40,780 --> 00:08:44,090
όπου θα προτείνατε
Μου επιστήσω σε αυτή την σειρά;

176
00:08:44,090 --> 00:08:47,124
Υπάρχουν πέντε διαφορετικές πιθανές απαντήσεις.

177
00:08:47,124 --> 00:08:48,790
Πού θέλετε να ωθήσει τον αριθμό 50;

178
00:08:48,790 --> 00:08:51,899
Αν ο στόχος εδώ, πάλι, καλέστε το
ώθηση λειτουργία, περνούν σε ένα επιχείρημα

179
00:08:51,899 --> 00:08:52,940
50, όπου μπορώ να το πω;

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Πέντε possible-- 20% πιθανότητα
μαντέψουν σωστά.

182
00:08:59,052 --> 00:08:59,896
Ναι;

183
00:08:59,896 --> 00:09:00,740
>> Κοινό: Πολύ σωστά.

184
00:09:00,740 --> 00:09:01,990
>> ΟΜΙΛΗΤΗΣ 1: Πολύ σωστά.

185
00:09:01,990 --> 00:09:08,359
Υπάρχει τώρα μια πιθανότητα 25%
μαντέψουν σωστά.

186
00:09:08,359 --> 00:09:09,650
Έτσι ώστε θα ήταν πραγματικά ωραία.

187
00:09:09,650 --> 00:09:12,770
Κατά σύμβαση, θα πω με μια σειρά,
θα ξεκινήσει γενικά στα αριστερά,

188
00:09:12,770 --> 00:09:14,519
αλλά θα μπορούσαμε σίγουρα
ξεκινούν από τη σωστή.

189
00:09:14,519 --> 00:09:17,478
Έτσι, η αεροτομή εδώ θα είμαι
κατά πάσα πιθανότητα πρόκειται να αντλήσει από την αριστερά,

190
00:09:17,478 --> 00:09:20,060
ακριβώς όπως σε μια κανονική σειρά, όπου
Αρχίζω να πηγαίνει αριστερά προς τα δεξιά.

191
00:09:20,060 --> 00:09:21,780
Αλλά αν μπορείτε να αναστρέψετε
η αριθμητική, πρόστιμο.

192
00:09:21,780 --> 00:09:23,060
Δεν είναι μόνο τα συμβατικά.

193
00:09:23,060 --> 00:09:24,880
Εντάξει, θέλω να κάνω μια
περισσότερες αλλαγές όμως.

194
00:09:24,880 --> 00:09:27,710
Τώρα που έχω έσπρωξε κάτι
στη στοίβα, τι γίνεται στη συνέχεια;

195
00:09:27,710 --> 00:09:29,400
>> Εντάξει, έχω να αυξήσετε το μέγεθος.

196
00:09:29,400 --> 00:09:32,600
Επιτρέψτε μου λοιπόν να προχωρήσουμε και λίγο
ενημέρωση αυτή, η οποία ήταν μηδέν.

197
00:09:32,600 --> 00:09:35,950
Και αντ 'αυτού τώρα, θα πάω
να θέσει σε αξία ένα.

198
00:09:35,950 --> 00:09:39,460
Και τώρα ας υποθέσουμε ότι πατάω ένα άλλο
αριθμός στη στοίβα, όπως 51.

199
00:09:39,460 --> 00:09:42,680
Λοιπόν, έχω να κάνω ένα ακόμη
αλλαγή, η οποία είναι μέχρι το μέγεθος δύο.

200
00:09:42,680 --> 00:09:46,100
Και στη συνέχεια, ας υποθέσουμε ότι πατάω ένα ακόμη
αριθμός στη στοίβα όπως 61,

201
00:09:46,100 --> 00:09:52,530
τώρα θα πρέπει να ενημερώσετε το μέγεθος ενός πιο
το χρόνο, και να πάρετε την τιμή 3, όπως το μέγεθος.

202
00:09:52,530 --> 00:09:54,690
Και τώρα ας υποθέσουμε ότι καλώ ποπ.

203
00:09:54,690 --> 00:09:57,250
Τώρα pop, κατά συνθήκη,
δεν παίρνει ένα επιχείρημα.

204
00:09:57,250 --> 00:10:00,430
Με μια στοίβα, το σύνολο
το σημείο της μεταφοράς δίσκου

205
00:10:00,430 --> 00:10:03,450
είναι ότι δεν έχετε την κρίση
να πάει να πάρει αυτό το δίσκο, το μόνο που έχετε να κάνετε

206
00:10:03,450 --> 00:10:06,330
έχει σκάσει το ανώτατο μία από
η στοίβα, μόνο και μόνο επειδή.

207
00:10:06,330 --> 00:10:08,010
Αυτό είναι ό, τι κάνει αυτή η δομή δεδομένων.

208
00:10:08,010 --> 00:10:12,250
>> Έτσι, με αυτή τη λογική, αν μου
λένε ποπ, τι βγαίνει;

209
00:10:12,250 --> 00:10:13,080
Έτσι, 61.

210
00:10:13,080 --> 00:10:15,402
Έτσι, αυτό που πραγματικά είναι ο υπολογιστής
πρόκειται να κάνω στη μνήμη;

211
00:10:15,402 --> 00:10:16,610
Τι σημαίνει κωδικό μου πρέπει να κάνω;

212
00:10:16,610 --> 00:10:20,330
Τι θα προτείνατε
αλλάζουμε στην οθόνη;

213
00:10:20,330 --> 00:10:23,410
Τι πρέπει να αλλάξει;

214
00:10:23,410 --> 00:10:24,960
Συγνώμη;

215
00:10:24,960 --> 00:10:26,334
Έτσι, μπορούμε να απαλλαγούμε από 61.

216
00:10:26,334 --> 00:10:27,500
Έτσι, σίγουρα μπορώ να το κάνω.

217
00:10:27,500 --> 00:10:28,640
Και μπορώ να απαλλαγούμε από 61.

218
00:10:28,640 --> 00:10:30,980
Και τότε τι άλλο
αλλαγή πρέπει να συμβεί;

219
00:10:30,980 --> 00:10:33,160
Μέγεθος μάλλον έχει να πάει πίσω σε δύο.

220
00:10:33,160 --> 00:10:34,210
Και έτσι αυτό είναι εντάξει.

221
00:10:34,210 --> 00:10:36,690
Αλλά περιμένετε ένα λεπτό, το μέγεθος
πριν από λίγο ήταν τρεις.

222
00:10:36,690 --> 00:10:38,240
Ας κάνουμε ένα γρήγορο έλεγχο λογικότητας.

223
00:10:38,240 --> 00:10:41,810
Πώς ξέρουμε ότι
ήθελε να ξεφορτωθεί των 61;

224
00:10:41,810 --> 00:10:42,760
Επειδή είμαστε βρεθώ.

225
00:10:42,760 --> 00:10:46,450
Και έτσι έχω αυτό το δεύτερο μέγεθος της περιουσίας.

226
00:10:46,450 --> 00:10:48,470
>> Περιμένετε ένα λεπτό, είμαι
σκέψης πίσω σε δύο εβδομάδες

227
00:10:48,470 --> 00:10:51,660
όταν αρχίσαμε να μιλάμε για
συστοιχίες, όπου αυτό ήταν μηδενική θέση,

228
00:10:51,660 --> 00:10:55,920
Αυτή ήταν η θέση ενός, αυτό ήταν τοποθεσίας
δυο, αυτό είναι η τοποθεσία τρία, τέσσερα,

229
00:10:55,920 --> 00:10:58,460
μοιάζει με το
σχέση μεταξύ του μεγέθους

230
00:10:58,460 --> 00:11:02,780
και το στοιχείο που θέλετε να καταργήσετε
από τον πίνακα φαίνεται να είναι ακριβώς ό, τι;

231
00:11:02,780 --> 00:11:05,120
Μέγεθος μείον ένα.

232
00:11:05,120 --> 00:11:07,786
Και έτσι αυτό είναι το πώς οι άνθρωποι
Γνωρίζουμε 61 έρχεται πρώτη.

233
00:11:07,786 --> 00:11:09,160
Πώς είναι ο υπολογιστής πρόκειται να ξέρει;

234
00:11:09,160 --> 00:11:11,701
Όταν κωδικό σας, όπου μπορείτε πιθανώς
θέλουμε να κάνουμε το μέγεθος μείον ένα,

235
00:11:11,701 --> 00:11:14,950
έτσι τρείς μείον ένα είναι δύο και ότι
Σημαίνει ότι θέλουμε να απαλλαγούμε από 61.

236
00:11:14,950 --> 00:11:18,000
Και τότε μπορούμε πράγματι να ενημερώσετε
το μέγεθος, έτσι ώστε το μέγεθος τώρα

237
00:11:18,000 --> 00:11:20,300
πηγαίνει από τρεις σε δύο μόνο.

238
00:11:20,300 --> 00:11:24,520
Και ακριβώς για να είναι σχολαστικός, Πάω
να προτείνει ότι είμαι γίνει, έτσι δεν είναι;

239
00:11:24,520 --> 00:11:27,660
Μπορείτε προτεινόμενη διαισθητικά
σωστά θα πρέπει να απαλλαγούμε από 61.

240
00:11:27,660 --> 00:11:30,700
Αλλά δεν έχουν 'αυτό το είδος
είδος ξεφορτωθεί 61;

241
00:11:30,700 --> 00:11:33,790
Έχω ξεχάσει αποτελεσματικά
ότι είναι πραγματικά εκεί.

242
00:11:33,790 --> 00:11:37,680
Και σκεφτείτε ότι πίσω σε PSET4, αν έχετε διαβάσει
Το άρθρο σχετικά με την εγκληματολογία, το PDF

243
00:11:37,680 --> 00:11:40,780
ότι είχαμε εσείς διαβάζετε, ή θα
Θα διαβάσετε αυτή την εβδομάδα για PSET4.

244
00:11:40,780 --> 00:11:44,300
Θυμηθείτε ότι αυτό είναι πραγματικά συναφές με
η όλη ιδέα της εγκληματολογίας υπολογιστή.

245
00:11:44,300 --> 00:11:47,820
Τι κάνει ένας υπολογιστής είναι γενικά
απλά ξεχνάει όπου κάτι είναι,

246
00:11:47,820 --> 00:11:51,300
αλλά δεν πάει και όπως
προσπαθήστε να το μηδέν ή η παράκαμψη

247
00:11:51,300 --> 00:11:54,560
εκείνα τα κομμάτια με μηδενικά και μονάδες
ή κάποιο άλλο τυχαίο πρότυπο

248
00:11:54,560 --> 00:11:56,690
αν δεν το πράξουν οι ίδιοι σκόπιμα.

249
00:11:56,690 --> 00:11:58,930
Έτσι ήταν η διαίσθησή σας
Εντάξει, ας απαλλαγούμε από 61.

250
00:11:58,930 --> 00:12:00,650
Αλλά στην πραγματικότητα, δεν έχουμε να ενοχλεί.

251
00:12:00,650 --> 00:12:04,040
Εμείς απλά πρέπει να ξεχνάμε ότι
είναι εκεί με την αλλαγή του μεγέθους μας.

252
00:12:04,040 --> 00:12:05,662
>> Τώρα υπάρχει ένα πρόβλημα με αυτή την στοίβα.

253
00:12:05,662 --> 00:12:07,620
Αν μπορώ να συνεχίσουμε να πιέζουμε τα πράγματα
στη στοίβα, τι είναι

254
00:12:07,620 --> 00:12:11,167
Προφανώς πρόκειται να συμβεί
σε μόλις λίγες στιγμές;

255
00:12:11,167 --> 00:12:12,500
Εμείς πάμε για να εξαντληθεί ο χώρος.

256
00:12:12,500 --> 00:12:13,580
Και τι κάνουμε;

257
00:12:13,580 --> 00:12:14,680
Είμαστε είδος βιδωθεί.

258
00:12:14,680 --> 00:12:19,000
Αυτή η εφαρμογή δεν επιτρέπει
μας να αλλάξετε το μέγεθος του πίνακα, επειδή η χρήση

259
00:12:19,000 --> 00:12:21,240
Αυτή η σύνταξη, αν
σκεφτείτε ότι πίσω σε δύο εβδομάδες,

260
00:12:21,240 --> 00:12:23,520
τη στιγμή που έχετε δηλώσει
το μέγεθος ενός πίνακα,

261
00:12:23,520 --> 00:12:26,780
δεν έχουμε δει ακόμα ένα μηχανισμό όπου
μπορείτε να αλλάξετε το μέγεθος του πίνακα.

262
00:12:26,780 --> 00:12:29,020
Και πράγματι C δεν έχει αυτό το χαρακτηριστικό.

263
00:12:29,020 --> 00:12:32,524
Εάν λέτε να μου δώσετε πέντε
Nths, καλέστε τους αριθμούς,

264
00:12:32,524 --> 00:12:33,940
αυτό είναι όλο πρόκειται να το πάρει.

265
00:12:33,940 --> 00:12:38,790
Γι 'αυτό κάνουμε τώρα από τη Δευτέρα, έχουν
η ικανότητα να εκφράσουν ένα διάλυμα

266
00:12:38,790 --> 00:12:42,480
όμως, εμείς απλά πρέπει να ρυθμίσετε
ο ορισμός της στοίβας μας

267
00:12:42,480 --> 00:12:46,840
δεν είναι κάποια σκληρά κωδικοποιημένο πίνακα,
αλλά απλώς για να αποθηκεύσετε μια διεύθυνση.

268
00:12:46,840 --> 00:12:47,890
>> Τώρα γιατί συμβαίνει αυτό;

269
00:12:47,890 --> 00:12:51,690
Τώρα απλά πρέπει να αισθάνονται άνετα με
το γεγονός ότι όταν το πρόγραμμά μου τρέχει,

270
00:12:51,690 --> 00:12:53,730
Προφανώς Πάω να
πρέπει να ζητήσει από τον άνθρωπο,

271
00:12:53,730 --> 00:12:55,110
πόσους αριθμούς θέλετε να αποθηκεύσετε;

272
00:12:55,110 --> 00:12:56,776
Έτσι, η είσοδος πρέπει να προέλθει από κάπου.

273
00:12:56,776 --> 00:12:59,140
Αλλά από τη στιγμή ξέρω ότι
αριθμός, τότε μπορώ μόνο

274
00:12:59,140 --> 00:13:02,470
χρησιμοποιήσετε ό, τι λειτουργεί για να δώσει
μου ένα κομμάτι της μνήμης;

275
00:13:02,470 --> 00:13:03,580
Μπορώ να χρησιμοποιήσω malloc.

276
00:13:03,580 --> 00:13:06,710
Και μπορώ να πω οποιοδήποτε αριθμό των
bytes Θέλω πίσω για αυτές τις Nths.

277
00:13:06,710 --> 00:13:10,910
Και το μόνο που έχω να αποθηκεύουν σε αριθμούς
μεταβλητή εδώ μέσα αυτού του struct

278
00:13:10,910 --> 00:13:13,480
θα πρέπει να είναι αυτό;

279
00:13:13,480 --> 00:13:18,440
Τι πηγαίνει πραγματικά σε το
αριθμοί σε αυτό το σενάριο;

280
00:13:18,440 --> 00:13:21,300
Ναι, ένας δείκτης για την πρώτη
byte του εν λόγω κομμάτι της μνήμης,

281
00:13:21,300 --> 00:13:24,940
ή πιο συγκεκριμένα, η διεύθυνση
από το πρώτο από τα bytes.

282
00:13:24,940 --> 00:13:27,300
Δεν έχει σημασία αν είναι ένα
byte ή ένα δισεκατομμύριο bytes,

283
00:13:27,300 --> 00:13:28,890
Απλά πρέπει να νοιάζονται για το πρώτο.

284
00:13:28,890 --> 00:13:31,530
Επειδή ό, τι εγγυήσεις και malloc
εγγυήσεις λειτουργικό σύστημα μου,

285
00:13:31,530 --> 00:13:34,170
είναι ότι το κομμάτι της μνήμης μου
πάρει, πρόκειται να είναι συνεχόμενες.

286
00:13:34,170 --> 00:13:35,378
Δεν πρόκειται να είναι κενά.

287
00:13:35,378 --> 00:13:38,576
Έτσι, αν έχω ζητήσει 50
byte ή 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
όλοι πηγαίνουν να
πλάτη με πλάτη με πλάτη.

289
00:13:40,450 --> 00:13:44,500
Και εφ 'όσον θυμάμαι πόσο μεγάλη, πόσο
πολύ ζήτησα, όλα όσα πρέπει να ξέρετε

290
00:13:44,500 --> 00:13:46,230
Είναι η πρώτη τέτοια διεύθυνση.

291
00:13:46,230 --> 00:13:48,660
>> Έτσι τώρα έχουμε τη δυνατότητα στον κώδικα.

292
00:13:48,660 --> 00:13:51,280
Αν και, πρόκειται να μας πάρει
περισσότερο χρόνο για να γράψω αυτό επάνω,

293
00:13:51,280 --> 00:13:55,900
θα μπορούσαμε τώρα να ανακατανείμει τις μνήμες από
μόνο την αποθήκευση σε διαφορετική διεύθυνση εκεί

294
00:13:55,900 --> 00:13:59,060
αν θέλουμε ένα μεγαλύτερο ή ακόμη και
ένα μικρότερο κομμάτι της μνήμης.

295
00:13:59,060 --> 00:14:00,170
Έτσι, εδώ σε ένα εμπόριο off.

296
00:14:00,170 --> 00:14:01,360
Τώρα έχουμε δυναμισμό.

297
00:14:01,360 --> 00:14:03,350
Έχουμε ακόμα
contiguousness είμαι διεκδίκηση.

298
00:14:03,350 --> 00:14:05,881
Επειδή malloc θα μας δώσει
ένα συνεχές κομμάτι της μνήμης.

299
00:14:05,881 --> 00:14:08,630
Αλλά αυτό πρόκειται να είναι ένας πόνος στο
ο λαιμός μας, ο προγραμματιστής,

300
00:14:08,630 --> 00:14:09,770
πραγματικά να κωδικοποιήσει επάνω.

301
00:14:09,770 --> 00:14:10,730
Είναι απλά περισσότερη δουλειά.

302
00:14:10,730 --> 00:14:13,930
Χρειαζόμαστε κώδικα παρόμοιο με αυτό που ήμουν
χτυπώντας έξω μόλις πριν από ένα χρόνο.

303
00:14:13,930 --> 00:14:16,120
Πολύ εφικτό, αλλά προσθέτει πολυπλοκότητα.

304
00:14:16,120 --> 00:14:19,520
Και έτσι ο χρόνος του έργου, προγραμματιστής
ο χρόνος είναι ένα ακόμη πόρο

305
00:14:19,520 --> 00:14:22,520
ότι ίσως χρειαστεί να δαπανήσει
κάποια στιγμή να πάρει νέα χαρακτηριστικά.

306
00:14:22,520 --> 00:14:24,020
Και τότε φυσικά υπάρχει μια ουρά.

307
00:14:24,020 --> 00:14:26,227
Δεν θα υπεισέλθω σε αυτό
μία στις πολλές λεπτομέρειες.

308
00:14:26,227 --> 00:14:27,560
Αλλά είναι πολύ παρόμοια στο πνεύμα.

309
00:14:27,560 --> 00:14:31,220
Θα μπορούσε να εφαρμόσει μια ουρά, και
αντίστοιχων ενεργειών της,

310
00:14:31,220 --> 00:14:35,660
Τοποθέτηση στην ουρά ή dequeue, όπως προσθέσετε ή να αφαιρέσετε,
είναι ακριβώς ένα φανταχτερό τρόπο λέγοντας ότι,

311
00:14:35,660 --> 00:14:38,100
Τοποθέτηση στην ουρά ή dequeue, ως εξής.

312
00:14:38,100 --> 00:14:41,170
Μπορώ να δώσω στον εαυτό μου μόνο ένα struct
ότι έχει και πάλι έναν αριθμό σειρά του,

313
00:14:41,170 --> 00:14:44,000
ότι και πάλι έχει ένα μέγεθος,
αλλά γιατί χρειάζομαι τώρα

314
00:14:44,000 --> 00:14:46,940
να παρακολουθείτε την μπροστά από μια ουρά;

315
00:14:46,940 --> 00:14:50,630
Δεν χρειάζεται να γνωρίζετε
το μπροστινό μέρος του stack μου.

316
00:14:50,630 --> 00:14:53,570
Λοιπόν, αν και πάλι για μια
queue-- ας σκληρά

317
00:14:53,570 --> 00:14:57,870
κώδικα, όπως έχει σαν πέντε
ακέραιοι εδώ δυνητικά.

318
00:14:57,870 --> 00:15:00,940
Έτσι, αυτό είναι μηδέν, ένα, δύο, τρία, τέσσερα.

319
00:15:00,940 --> 00:15:03,430
Αυτό πρόκειται να είναι
κάλεσε και πάλι τους αριθμούς.

320
00:15:03,430 --> 00:15:06,940
Και αυτό θα πρέπει να ονομάζεται μέγεθος.

321
00:15:06,940 --> 00:15:10,056
>> Γιατί δεν αρκεί
να έχουν μόνο το μέγεθος;

322
00:15:10,056 --> 00:15:11,680
Λοιπόν, ας πιέσουμε τις ίδιες αριθμούς.

323
00:15:11,680 --> 00:15:14,220
Γι 'αυτό και εγώ pushed-- enqueued, ή έσπρωξε.

324
00:15:14,220 --> 00:15:20,150
Τώρα θα Τοποθέτηση στην ουρά 50, και στη συνέχεια,
51, 61 και στη συνέχεια, και dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Έτσι ώστε να είναι Τοποθέτηση στην ουρά.

326
00:15:21,070 --> 00:15:23,176
Ι enqueued 50, τότε 51, τότε 61.

327
00:15:23,176 --> 00:15:25,050
Και αυτό είναι ολόιδια
σε μια στοίβα μέχρι στιγμής,

328
00:15:25,050 --> 00:15:27,190
πλην I χρειάζεται να κάνετε μία αλλαγή.

329
00:15:27,190 --> 00:15:33,680
Θα πρέπει να ενημερώσετε αυτό το μέγεθος, γι 'αυτό πάω
από μηδέν έως ένα και δύο με τρεις τώρα.

330
00:15:33,680 --> 00:15:35,760
Πώς μπορώ να dequeue;

331
00:15:35,760 --> 00:15:36,890
Τι συμβαίνει με dequeue;

332
00:15:36,890 --> 00:15:41,950
Ποιος θα βγει από αυτήν την πρώτη λίστα
αν είναι η γραμμή στο Apple Store;

333
00:15:41,950 --> 00:15:42,780
Έτσι, 50.

334
00:15:42,780 --> 00:15:44,700
Έτσι είναι το είδος της πιο περίπλοκη αυτή τη φορά.

335
00:15:44,700 --> 00:15:47,880
Εκτιμώντας τελευταία φορά που ήταν σούπερ
εύκολο να κάνει ακριβώς το μέγεθος μείον ένα,

336
00:15:47,880 --> 00:15:51,440
Θα φτάσουμε στο τέλος του πίνακα αποτελεσματικά μου
όπου βρίσκονται οι αριθμοί, αφαιρεί 61.

337
00:15:51,440 --> 00:15:52,920
Αλλά δεν θέλω να καταργήσετε 61.

338
00:15:52,920 --> 00:15:55,030
Θέλω να πάρω 50, ο οποίος
υπήρχε στις 5:00 π.μ.

339
00:15:55,030 --> 00:15:56,790
να παρατάξει για το
νέο iPhone ή οτιδήποτε.

340
00:15:56,790 --> 00:16:01,200
Και έτσι για να απαλλαγούμε από 50, Ι
Δεν μπορούμε απλά να το κάνετε αυτό, σωστά;

341
00:16:01,200 --> 00:16:02,547
Μπορώ να περάσουν από 50.

342
00:16:02,547 --> 00:16:04,380
Αλλά εμείς απλά είπαμε
Δεν χρειάζεται να είναι τόσο πρωκτική

343
00:16:04,380 --> 00:16:06,330
ως προς το μηδέν ή να αποκρύψετε τα δεδομένα.

344
00:16:06,330 --> 00:16:08,090
Εμείς απλά να ξεχνάμε από πού είναι.

345
00:16:08,090 --> 00:16:12,330
>> Αλλά αν μπορώ να αλλάξω το νούμερό μου τώρα
δυο, είναι αυτό επαρκείς πληροφορίες

346
00:16:12,330 --> 00:16:15,711
να γνωρίζουν τι συμβαίνει στην ουρά μου;

347
00:16:15,711 --> 00:16:16,680
Όχι ακριβώς.

348
00:16:16,680 --> 00:16:19,830
Όπως το νούμερό μου είναι δύο, αλλά
πού αρχίζει η ουρά,

349
00:16:19,830 --> 00:16:22,980
ειδικά αν έχω ακόμα
αυτοί ίδιους αριθμούς στη μνήμη.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Γι 'αυτό πρέπει να θυμάστε
τώρα, όπου το μέτωπο είναι.

352
00:16:27,090 --> 00:16:29,630
Και έτσι όπως προτείνεται μέχρι
εκεί, θα έχουμε μόλις που ονομάζεται

353
00:16:29,630 --> 00:16:33,729
Νιοστή μπροστά, του οποίου η αρχική
αξία θα έπρεπε να είναι αυτό;

354
00:16:33,729 --> 00:16:35,270
Μηδέν, μόνο η αρχή της λίστας.

355
00:16:35,270 --> 00:16:40,876
Τώρα, όμως, εκτός από την Decrementing
το μέγεθος, εμείς απλά αυξήσετε το μέτωπο.

356
00:16:40,876 --> 00:16:42,000
Τώρα εδώ είναι ένα άλλο πρόβλημα.

357
00:16:42,000 --> 00:16:43,030
Έτσι, τη στιγμή συνεχίζω.

358
00:16:43,030 --> 00:16:47,520
Ας υποθέσουμε ότι αυτή είναι ο αριθμός των
όπως 121, 124, και στη συνέχεια, διάολε,

359
00:16:47,520 --> 00:16:48,610
Είμαι έξω χώρο.

360
00:16:48,610 --> 00:16:50,390
Αλλά περιμένετε ένα λεπτό, δεν είμαι.

361
00:16:50,390 --> 00:16:55,630
Έτσι, σε αυτό το σημείο στην ιστορία,
ας υποθέσουμε ότι το μέγεθος είναι ένα, δύο,

362
00:16:55,630 --> 00:17:00,370
τρία, τέσσερα, έτσι υποθέσουμε ότι η
μέγεθος είναι τέσσερα, το μέτωπο είναι ένα,

363
00:17:00,370 --> 00:17:01,621
έτσι 51 βρίσκεται στο μπροστινό μέρος.

364
00:17:01,621 --> 00:17:04,329
Θέλω να βάλω έναν άλλο αριθμό εδώ,
αλλά, διάολε, είμαι από το διάστημα.

365
00:17:04,329 --> 00:17:06,710
Αλλά δεν είμαι πραγματικά, έτσι δεν είναι;

366
00:17:06,710 --> 00:17:11,192
Πού θα μπορούσε να βάζω μερικά
πρόσθετη αξία, όπως 171;

367
00:17:11,192 --> 00:17:13,400
Ναι, θα μπορούσα ακριβώς το είδος του
επιστρέψω εκεί, σωστά;

368
00:17:13,400 --> 00:17:18,161
Και στη συνέχεια διασχίζουν το 50, ή
απλά το αντικαταστήσετε με 171.

369
00:17:18,161 --> 00:17:20,410
Και αν αναρωτιέστε γιατί
αριθμοί μας πήρε τόσο τυχαία,

370
00:17:20,410 --> 00:17:24,150
αυτά είναι συνήθως λαμβάνονται υπολογιστή
μαθήματα επιστήμης στο Χάρβαρντ μετά CS50.

371
00:17:24,150 --> 00:17:27,510
Αλλά αυτό ήταν μια καλή βελτιστοποίηση,
γιατί τώρα δεν είμαι σπατάλη χώρου.

372
00:17:27,510 --> 00:17:30,750
Έχω ακόμα να θυμόμαστε
πόσο μεγάλο είναι αυτό το πράγμα είναι συνολική.

373
00:17:30,750 --> 00:17:31,500
Είναι πέντε συνολικά.

374
00:17:31,500 --> 00:17:33,375
Επειδή δεν θέλω να
ξεκινήσετε την αντικατάσταση 51.

375
00:17:33,375 --> 00:17:36,260
Έτσι τώρα είμαι ακόμα έξω από το διάστημα,
έτσι ώστε το ίδιο πρόβλημα όπως και πριν.

376
00:17:36,260 --> 00:17:39,140
Αλλά μπορείτε να δείτε πώς τώρα
στον κώδικά σας, ίσως

377
00:17:39,140 --> 00:17:41,910
Πρέπει να γράψω ένα λίγο πιο
πολυπλοκότητα για να συμβεί αυτό.

378
00:17:41,910 --> 00:17:44,510
Και στην πραγματικότητα, ό, τι χειριστή
σε C πιθανότατα αφήνει

379
00:17:44,510 --> 00:17:48,110
κάνετε μαγικά αυτό το κυκλικότητα;

380
00:17:48,110 --> 00:17:50,160
Ναι τελεστής του υπόλοιπου,
το σύμβολο τοις εκατό.

381
00:17:50,160 --> 00:17:53,160
Έτσι τι είναι είδος δροσερό για μια ουρά,
ακόμα κι αν κρατάμε την κατάρτιση πινάκων

382
00:17:53,160 --> 00:17:56,520
όπως αυτές όπως ευθείες γραμμές, αν
είδος σκεφτείτε ως κάμπτοντας

383
00:17:56,520 --> 00:18:00,341
περίπου ως έναν κύκλο, τότε απλά
διαισθητικά αυτό το είδος των έργων ψυχικά

384
00:18:00,341 --> 00:18:01,590
Νομίζω ότι λίγο πιο καθαρά.

385
00:18:01,590 --> 00:18:05,190
Θα πρέπει ακόμα να εφαρμόσουν
ότι νοητικό μοντέλο στον κώδικα.

386
00:18:05,190 --> 00:18:07,550
Έτσι δεν είναι ότι σκληρά,
εν τέλει, για την εφαρμογή της,

387
00:18:07,550 --> 00:18:12,430
αλλά εξακολουθεί να χάνουμε την size-- μάλλον, η
δυνατότητα να αλλάξετε το μέγεθος, αν δεν κάνουμε αυτό.

388
00:18:12,430 --> 00:18:15,310
>> Πρέπει να απαλλαγούμε από τη σειρά, θα
αντικαταστήσει με ένα μόνο δείκτη,

389
00:18:15,310 --> 00:18:20,010
και, στη συνέχεια, κάπου στον κώδικά μου έχω
μια κλήση ό, τι λειτουργεί για να δημιουργήσει πραγματικά

390
00:18:20,010 --> 00:18:23,720
η σειρά που ονομάζεται αριθμούς;

391
00:18:23,720 --> 00:18:26,190
Malloc, ή κάποια παρόμοια
λειτουργία, ακριβώς.

392
00:18:26,190 --> 00:18:30,481
Οποιεσδήποτε ερωτήσεις σχετικά με στοίβες ή ουρές.

393
00:18:30,481 --> 00:18:30,980
Ναι;

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Καλή ερώτηση.

396
00:18:34,240 --> 00:18:35,830
Τι modulo θα χρησιμοποιήσετε εδώ.

397
00:18:35,830 --> 00:18:38,520
Έτσι γενικά, κατά τη χρήση
mod, θα το κάνω

398
00:18:38,520 --> 00:18:40,620
με το μέγεθος της
ολόκληρη η δομή των δεδομένων.

399
00:18:40,620 --> 00:18:44,120
Έτσι, κάτι σαν πέντε ή ικανότητα, εάν
είναι σταθερή, είναι πιθανόν να εμπλέκονται.

400
00:18:44,120 --> 00:18:47,100
Αλλά ακριβώς κάνει modulo πέντε
πιθανόν να μην είναι επαρκής,

401
00:18:47,100 --> 00:18:51,380
γιατί πρέπει να ξέρουμε να κάνουμε
τυλίξτε γύρω από εδώ ή εδώ ή εδώ.

402
00:18:51,380 --> 00:18:54,160
Έτσι, είστε πιθανώς επίσης
πρόκειται να θέλουν να συμμετέχουν

403
00:18:54,160 --> 00:18:57,220
το μέγεθος του πράγματος, ή
το μπροστινό μεταβλητή, καθώς και.

404
00:18:57,220 --> 00:19:00,140
Έτσι είναι ακριβώς αυτό το σχετικά
απλή αριθμητική έκφραση,

405
00:19:00,140 --> 00:19:02,000
αλλά με μέτρο θα είναι το βασικό συστατικό.

406
00:19:02,000 --> 00:19:03,330
>> Έτσι, ταινία μικρού μήκους, αν θέλετε.

407
00:19:03,330 --> 00:19:05,780
Μια κίνηση που ορισμένοι
λαούς σε ένα άλλο πανεπιστήμιο

408
00:19:05,780 --> 00:19:08,060
μαζί ότι έχουμε
προσαρμοσμένο για αυτή τη συζήτηση.

409
00:19:08,060 --> 00:19:12,630
Πρόκειται Τζακ εκμάθηση της
στοιχεία σχετικά με τις ουρές και τα στατιστικά.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> ΦΙΛΜ: Μια φορά κι έναν καιρό,
υπήρχε ένας τύπος που ονομάζεται Jack.

412
00:19:21,890 --> 00:19:25,330
Όταν ήρθε να κάνει φίλους,
Τζακ δεν είχε ταλέντο.

413
00:19:25,330 --> 00:19:28,220
Έτσι ο Jack πήγε να μιλήσει με το
πιο δημοφιλής τύπος ήξερε.

414
00:19:28,220 --> 00:19:30,920
Πήγε στο Λου και ρώτησε, τι μπορώ να κάνω;

415
00:19:30,920 --> 00:19:33,400
Lou είδε ότι ο φίλος του
Ήταν πραγματικά στενοχωρημένος.

416
00:19:33,400 --> 00:19:36,050
Λοιπόν, άρχισε, μόλις
κοίτα πώς είστε ντυμένοι.

417
00:19:36,050 --> 00:19:38,680
Δεν έχετε ρούχα
με μια διαφορετική ματιά;

418
00:19:38,680 --> 00:19:39,660
Ναι, είπε ο Τζακ.

419
00:19:39,660 --> 00:19:40,840
Εγώ σίγουρα κάνω.

420
00:19:40,840 --> 00:19:43,320
Έλα στο σπίτι μου και
Θα τους δείξω.

421
00:19:43,320 --> 00:19:44,550
Έτσι πήγε να του Jack.

422
00:19:44,550 --> 00:19:47,520
Και ο Τζακ έδειξε Lou το παράθυρο
όπου φυλάσσονται όλα τα πουκάμισα του,

423
00:19:47,520 --> 00:19:49,260
και το παντελόνι του, και τις κάλτσες του.

424
00:19:49,260 --> 00:19:52,290
Lou είπε, βλέπω ότι έχετε
όλα τα ρούχα σας σε ένα σωρό.

425
00:19:52,290 --> 00:19:54,870
Γιατί δεν φορούν μερικά
άλλα μόλις για λίγο;

426
00:19:54,870 --> 00:19:58,020
>> Τζακ είπε, καλά, όταν
αφαιρέστε τα ρούχα και κάλτσες,

427
00:19:58,020 --> 00:20:00,780
Τους πλένουμε και το βάζουμε
τους μακριά στο κουτί.

428
00:20:00,780 --> 00:20:03,210
Στη συνέχεια, έρχεται το επόμενο
το πρωί και μέχρι I hop.

429
00:20:03,210 --> 00:20:06,380
Πηγαίνω στο παράθυρο και να πάρει
τα ρούχα μου από την κορυφή.

430
00:20:06,380 --> 00:20:09,070
Lou συνειδητοποίησε γρήγορα
το πρόβλημα με τον Τζακ.

431
00:20:09,070 --> 00:20:12,080
Συνέχισε ρούχα, CD,
και βιβλία στη στοίβα.

432
00:20:12,080 --> 00:20:14,420
Όταν έφτασε για
κάτι για να διαβάσετε ή να φορέσει,

433
00:20:14,420 --> 00:20:17,100
ότι θα επιλέξουν την κορυφή βιβλίο ή εσώρουχα.

434
00:20:17,100 --> 00:20:19,500
Στη συνέχεια, όταν είχε κάνει,
Θα το διορθώσουμε πίσω.

435
00:20:19,500 --> 00:20:21,970
Επιστροφή θα πάει, στην κορυφή της στοίβας.

436
00:20:21,970 --> 00:20:24,460
Γνωρίζω τη λύση,
είπε μια θριαμβευτική δυνατά.

437
00:20:24,460 --> 00:20:27,090
Θα πρέπει να μάθουν να
αρχίσετε να χρησιμοποιείτε μια ουρά.

438
00:20:27,090 --> 00:20:29,870
Λου πήρε τα ρούχα του Jack και
κρέμασαν τους στην ντουλάπα.

439
00:20:29,870 --> 00:20:32,710
Και όταν είχε αδειάσει
το πλαίσιο, ο ίδιος απλά πετιέται.

440
00:20:32,710 --> 00:20:36,500
>> Στη συνέχεια, είπε, τώρα Τζακ, στο τέλος της
η ημέρα, βάλτε τα ρούχα σας στο αριστερό

441
00:20:36,500 --> 00:20:37,990
Όταν βάζετε μακριά.

442
00:20:37,990 --> 00:20:41,300
Στη συνέχεια, αύριο το πρωί, όταν
δείτε τον ήλιο, να πάρει τα ρούχα σας

443
00:20:41,300 --> 00:20:43,440
στα δεξιά, από το τέλος της γραμμής.

444
00:20:43,440 --> 00:20:44,880
Μην βλέπετε; δήλωσε ο Lou.

445
00:20:44,880 --> 00:20:46,370
Θα είναι τόσο ωραία.

446
00:20:46,370 --> 00:20:49,770
Θα φοράτε πάντα μια φορά
πριν φορέσετε κάτι δύο φορές.

447
00:20:49,770 --> 00:20:52,670
Και με τα πάντα στις ουρές
ντουλάπα και ράφι του,

448
00:20:52,670 --> 00:20:55,160
Τζακ άρχισε να αισθάνεται
αρκετά σίγουρος για τον εαυτό του.

449
00:20:55,160 --> 00:20:59,720
Όλες οι ευχαριστίες προς τον Lou και
υπέροχη ουρά του.

450
00:20:59,720 --> 00:21:01,220
ΟΜΙΛΗΤΗΣ 1: Εντάξει, αυτό είναι αξιολάτρευτο.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Έτσι, αυτό που έχει πραγματικά συμβαίνει
για κάτω από το καπό τώρα;

453
00:21:10,080 --> 00:21:12,370
Ότι έχουμε δείκτες,
ότι έχουμε malloc,

454
00:21:12,370 --> 00:21:15,680
ότι έχουμε τη δυνατότητα να δημιουργήσουμε
κομμάτια της μνήμης για τους εαυτούς μας

455
00:21:15,680 --> 00:21:16,344
δυναμικά.

456
00:21:16,344 --> 00:21:18,510
Έτσι, αυτό είναι μια εικόνα που
είδαμε τις προάλλες.

457
00:21:18,510 --> 00:21:21,180
Δεν είχαμε πραγματικά να κατοικήσει
σε αυτό, αλλά αυτή η εικόνα

458
00:21:21,180 --> 00:21:24,180
έχει αρχίσει εδώ και κάτω
Η κουκούλα για εβδομάδες τώρα.

459
00:21:24,180 --> 00:21:27,050
Και έτσι αυτό αντιπροσωπεύει, απλά
ένα ορθογώνιο που έχουμε ζωγραφίσει,

460
00:21:27,050 --> 00:21:28,180
μνήμη του υπολογιστή σας.

461
00:21:28,180 --> 00:21:31,850
Και ίσως υπολογιστή σας, ή CS50
ID, έχει ένα gigabyte μνήμης RAM ή

462
00:21:31,850 --> 00:21:33,050
ή δύο gigabytes ή τέσσερις.

463
00:21:33,050 --> 00:21:34,450
Δεν έχει τόση σημασία.

464
00:21:34,450 --> 00:21:37,240
Το λειτουργικό σας σύστημα
Windows ή Mac OS ή Linux,

465
00:21:37,240 --> 00:21:41,120
επιτρέπει ουσιαστικά το πρόγραμμά σας
να πιστεύω ότι έχει πρόσβαση

466
00:21:41,120 --> 00:21:42,982
στο σύνολο του
μνήμη του υπολογιστή σας,

467
00:21:42,982 --> 00:21:45,440
ακόμα κι αν μπορούσε να τρέχει
πολλαπλά προγράμματα ταυτόχρονα.

468
00:21:45,440 --> 00:21:46,990
Έτσι, στην πραγματικότητα, ότι δεν λειτουργεί πραγματικά.

469
00:21:46,990 --> 00:21:49,448
Αλλά αυτό είναι το είδος της μια ψευδαίσθηση
δοθεί σε όλα τα προγράμματα σας.

470
00:21:49,448 --> 00:21:53,110
Έτσι, αν είχατε δύο συναυλίες της μνήμης RAM, αυτό
είναι το πώς ο υπολογιστής μπορεί να το σκέφτομαι αυτό.

471
00:21:53,110 --> 00:21:57,110
>> Τώρα συμπτωματικά, ένα από αυτά
πράγματα, ένα από αυτά τα τμήματα της μνήμης,

472
00:21:57,110 --> 00:21:58,350
ονομάζεται στοίβα.

473
00:21:58,350 --> 00:22:01,680
Και πράγματι, κάθε φορά που
μέχρι στιγμής το γράψιμο κώδικα

474
00:22:01,680 --> 00:22:05,900
ότι έχετε ονομάζεται
λειτουργία, για παράδειγμα κύριο.

475
00:22:05,900 --> 00:22:08,410
Υπενθυμίζουμε ότι κάθε φορά που έχω
μνήμη του υπολογιστή που,

476
00:22:08,410 --> 00:22:10,640
Πάντα επιστήσω είδος
το μισό ενός ορθογωνίου εδώ

477
00:22:10,640 --> 00:22:12,520
και δεν χρειάζεται να μιλάμε
σχετικά με το τι είναι πιο πάνω.

478
00:22:12,520 --> 00:22:15,980
Διότι όταν η κύρια λέγεται, αξιώνω
ότι μπορείτε να πάρετε αυτή την αγκίδα της μνήμης

479
00:22:15,980 --> 00:22:16,970
ότι κατεβαίνει εδώ.

480
00:22:16,970 --> 00:22:20,650
Και αν ο κύριος που ονομάζεται συνάρτηση
όπως swap, και ανταλλαγής πηγαίνει εδώ.

481
00:22:20,650 --> 00:22:23,720
Και αποδεικνύεται, ότι είναι
όπου είναι καταλήξουμε.

482
00:22:23,720 --> 00:22:26,277
Σε κάτι που ονομάζεται στοίβα
στο εσωτερικό της μνήμης του υπολογιστή σας.

483
00:22:26,277 --> 00:22:28,360
Τώρα στο τέλος της ημέρας,
αυτό είναι ακριβώς αντιμετωπίζει.

484
00:22:28,360 --> 00:22:30,680
Είναι σαν byte μηδέν,
byte ένα byte 2 δισ.

485
00:22:30,680 --> 00:22:33,130
Αλλά αν το σκεφτείτε
όπως αυτή ορθογώνιο αντικείμενο,

486
00:22:33,130 --> 00:22:35,130
όλοι κάνουμε κάθε
φορά καλούμε μια συνάρτηση είναι

487
00:22:35,130 --> 00:22:37,180
layering ένα νέο κομμάτι της μνήμης.

488
00:22:37,180 --> 00:22:41,700
Δίνουμε τη λειτουργία αυτή μια φέτα
από τη δική του μνήμη για να εργαστεί με.

489
00:22:41,700 --> 00:22:44,490
>> Και υπενθυμίζουν τώρα ότι αυτό είναι σημαντικό.

490
00:22:44,490 --> 00:22:46,400
Διότι αν δεν έχουν
κάτι σαν ανταλλαγής

491
00:22:46,400 --> 00:22:51,610
και δύο τοπικές μεταβλητές όπως Α και Β και
αλλάζουμε αυτές τις αξίες από τη μία και δύο

492
00:22:51,610 --> 00:22:55,130
σε δύο και, ανάκληση
ότι, όταν επιστρέφει ανταλλαγής,

493
00:22:55,130 --> 00:22:58,330
είναι σαν τη φέτα,
της μνήμης είναι μόλις φύγει.

494
00:22:58,330 --> 00:23:00,080
Στην πραγματικότητα, είναι ακόμα
forensically εκεί.

495
00:23:00,080 --> 00:23:01,940
Και κάτι ακόμα πραγματικά εκεί.

496
00:23:01,940 --> 00:23:05,410
Αλλά εννοιολογικά, είναι όπως
αν και είναι εντελώς φύγει.

497
00:23:05,410 --> 00:23:10,910
Και έτσι η κύρια δεν γνωρίζει οποιαδήποτε από τις εργασίες
ότι έγινε σε αυτή την λειτουργία εναλλαγής,

498
00:23:10,910 --> 00:23:14,890
αν δεν είναι στην πραγματικότητα πέρασε σε εκείνους
επιχειρήματα από το δείκτη ή με αναφορά.

499
00:23:14,890 --> 00:23:17,790
Τώρα, η θεμελιώδης λύση
σε αυτό το πρόβλημα με την ανταλλαγή

500
00:23:17,790 --> 00:23:19,970
περνά από τα πράγματα στη διεύθυνση.

501
00:23:19,970 --> 00:23:23,250
Αλλά αποδεικνύεται, πάρα πολύ, τι είναι
συνεχίζεται πάνω από αυτό το μέρος

502
00:23:23,250 --> 00:23:26,330
του ορθογωνίου όλο αυτό το διάστημα είναι
Υπάρχει όμως περισσότερη μνήμη μέχρι εκεί.

503
00:23:26,330 --> 00:23:28,790
Και όταν δυναμικά
εκχώρηση μνήμης,

504
00:23:28,790 --> 00:23:32,020
είτε πρόκειται για εσωτερικό της GetString, η οποία
έχουμε κάνει για σας στο CS50

505
00:23:32,020 --> 00:23:34,710
βιβλιοθήκη, ή αν εσείς
καλέστε malloc και να ζητήσει

506
00:23:34,710 --> 00:23:37,950
το λειτουργικό σύστημα για ένα κομμάτι της
μνήμη, δεν προέρχεται από τη στοίβα.

507
00:23:37,950 --> 00:23:40,960
Προέρχεται από μια άλλη χώρα
στη μνήμη του υπολογιστή σας

508
00:23:40,960 --> 00:23:42,220
αυτό ονομάζεται ο σωρός.

509
00:23:42,220 --> 00:23:43,430
Και αυτό δεν είναι κάτι διαφορετικό.

510
00:23:43,430 --> 00:23:44,285
Είναι η ίδια μνήμη RAM.

511
00:23:44,285 --> 00:23:45,160
Είναι η ίδια μνήμη.

512
00:23:45,160 --> 00:23:49,080
Είναι ακριβώς η μνήμη RAM που είναι μέχρι
εκεί, αντί του εδώ κάτω.

513
00:23:49,080 --> 00:23:50,750
>> Και ναι, τι σημαίνει αυτό;

514
00:23:50,750 --> 00:23:53,650
Λοιπόν, αν ο υπολογιστής σας έχει
μια πεπερασμένη ποσότητα μνήμης

515
00:23:53,650 --> 00:23:57,450
και η στοίβα μεγαλώνει, έτσι
να μιλήσει, και ο σωρός, σύμφωνα

516
00:23:57,450 --> 00:23:59,349
σε αυτό το βέλος, αυξάνεται προς τα κάτω.

517
00:23:59,349 --> 00:24:01,140
Με άλλα λόγια, κάθε
φορά που θα καλέσετε malloc,

518
00:24:01,140 --> 00:24:03,430
είστε δίνεται μια φέτα
της μνήμης από πάνω,

519
00:24:03,430 --> 00:24:06,630
τότε ίσως λίγο πιο κάτω, στη συνέχεια, μια μικρή
κάτω, κάθε φορά που θα καλέσετε malloc,

520
00:24:06,630 --> 00:24:10,100
ο σωρός, την χρήση της,
είναι το είδος της καλλιέργειας,

521
00:24:10,100 --> 00:24:11,950
αυξάνεται όλο και πιο κοντά σε ό, τι;

522
00:24:11,950 --> 00:24:13,382
Η στοίβα.

523
00:24:13,382 --> 00:24:14,840
Έτσι, αυτό δεν φαίνεται σαν μια καλή ιδέα;

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Θέλω να πω, όταν δεν είναι πραγματικά σαφής
ό, τι άλλο μπορείτε να κάνετε αν έχετε μόνο

526
00:24:22,140 --> 00:24:23,910
έχουν πεπερασμένη ποσότητα μνήμης.

527
00:24:23,910 --> 00:24:25,200
Αλλά αυτό είναι σίγουρα κακό.

528
00:24:25,200 --> 00:24:27,920
Αυτά τα δύο βέλη είναι για ένα
Crash Course ένας για τον άλλο.

529
00:24:27,920 --> 00:24:31,930
>> Και αποδεικνύεται ότι κακός, τους λαούς που
είναι ιδιαίτερα καλή με τον προγραμματισμό,

530
00:24:31,930 --> 00:24:36,140
και προσπαθεί να χαράξει σε ηλεκτρονικούς υπολογιστές,
μπορεί να εκμεταλλευτεί αυτή την πραγματικότητα.

531
00:24:36,140 --> 00:24:38,290
Στην πραγματικότητα, ας εξετάσουμε
ένα μικρό απόσπασμα.

532
00:24:38,290 --> 00:24:41,350
Έτσι, αυτό είναι ένα παράδειγμα μπορείτε να διαβάσετε
για περισσότερες λεπτομέρειες σχετικά με την Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Θα δείξετε το
Το άρθρο αν και περίεργη.

534
00:24:43,100 --> 00:24:45,650
Αλλά υπάρχει μια επίθεση σε γενικές γραμμές
γνωστή ως υπερχείλιση μνήμης που

535
00:24:45,650 --> 00:24:49,570
έχει υπάρξει για όσο χρονικό διάστημα οι άνθρωποι
είχαν την ικανότητα να χειραγωγούν

536
00:24:49,570 --> 00:24:53,120
μνήμη του υπολογιστή, ειδικά σε C.
Έτσι, αυτό είναι ένα πολύ αυθαίρετο πρόγραμμα,

537
00:24:53,120 --> 00:24:55,130
αλλά ας το διαβάσει από κάτω προς τα πάνω.

538
00:24:55,130 --> 00:24:57,650
Κύρια μέσα argc char αστέρων argv.

539
00:24:57,650 --> 00:24:59,830
Έτσι είναι ένα πρόγραμμα που διαρκεί
επιχειρήματα της γραμμής εντολών.

540
00:24:59,830 --> 00:25:03,620
Και όλα τα βασικά δεν φαίνεται να είναι η κλήση
μια λειτουργία, την αποκαλούν F για την απλότητα.

541
00:25:03,620 --> 00:25:04,610
Και σε ό, τι περνάει;

542
00:25:04,610 --> 00:25:05,490
Argv του ενός.

543
00:25:05,490 --> 00:25:09,320
Γι 'αυτό περνά στο F ανεξαρτήτως
η λέξη είναι ότι ο χρήστης πληκτρολογήσει

544
00:25:09,320 --> 00:25:11,500
στη γραμμή μετά από την
Το όνομά προγράμματος σε όλα.

545
00:25:11,500 --> 00:25:15,730
Τόσο πολύ, όπως Καίσαρα ή Vigenere, η οποία
Θα θυμάστε ίσως να κάνει με argv.

546
00:25:15,730 --> 00:25:16,680
>> Έτσι τι είναι F;

547
00:25:16,680 --> 00:25:19,760
F παίρνει σε μια σειρά
ως μοναδικό επιχείρημα,

548
00:25:19,760 --> 00:25:22,100
AKA ένα αστέρι κάρβουνου, το ίδιο
πράγμα, σαν ένα string.

549
00:25:22,100 --> 00:25:24,920
Και αυτό λέγεται αυθαίρετα
μπαρ σε αυτό το παράδειγμα.

550
00:25:24,920 --> 00:25:27,710
Και στη συνέχεια, char c 12,
μόνο σε απλή γλώσσα,

551
00:25:27,710 --> 00:25:31,750
τι είναι char c βραχίονα 12 κάνει για μας;

552
00:25:31,750 --> 00:25:33,440
Τι θα κάνουμε;

553
00:25:33,440 --> 00:25:36,490
Διαθέτοντας τη μνήμη, ειδικά
12 byte για 12 χαρακτήρες.

554
00:25:36,490 --> 00:25:36,990
Ακριβώς.

555
00:25:36,990 --> 00:25:40,000
Και τότε η τελευταία γραμμή, ανακατεύουμε και
αντίγραφο, πιθανώς έχετε δει.

556
00:25:40,000 --> 00:25:43,360
Αυτό είναι ένα αντίγραφο συμβολοσειράς
η λειτουργία του οποίου σκοπός στη ζωή

557
00:25:43,360 --> 00:25:48,160
είναι να αντιγράψετε το δεύτερο επιχείρημα της
σε πρώτο επιχείρημά της,

558
00:25:48,160 --> 00:25:51,190
αλλά μόνο μέχρι ένα
ορισμένο αριθμό bytes.

559
00:25:51,190 --> 00:25:53,860
Έτσι, το τρίτο επιχείρημα λέει,
πόσα bytes θα πρέπει να αντιγράψετε;

560
00:25:53,860 --> 00:25:56,720
Το μήκος της ράβδου,
ανεξάρτητα από το χρήστης πληκτρολογήσει.

561
00:25:56,720 --> 00:25:59,320
Και τα περιεχόμενα του
Μπαρ, ότι χορδών,

562
00:25:59,320 --> 00:26:02,330
αντιγραφεί στη μνήμη στραμμένο στο C.

563
00:26:02,330 --> 00:26:04,060
>> Έτσι, αυτό φαίνεται κάπως ανόητο, και αυτό είναι.

564
00:26:04,060 --> 00:26:06,300
Είναι μια σκηνοθετημένη παράδειγμα,
αλλά είναι αντιπροσωπευτικό

565
00:26:06,300 --> 00:26:10,100
της τάξης των φορέων επίθεσης,
ένας τρόπος για να επιτεθεί σε ένα πρόγραμμα.

566
00:26:10,100 --> 00:26:15,050
Όλα είναι ωραία και καλά, αν ο χρήστης
τύποι σε μια λέξη που είναι 11 χαρακτήρες

567
00:26:15,050 --> 00:26:18,040
ή λιγότερες, καθώς η αντίστροφη κάθετος μηδέν.

568
00:26:18,040 --> 00:26:22,830
Τι θα συμβεί αν ο χρήστης πληκτρολογήσει σε περισσότερες από
11 ή 12 ή 20 ή 50 χαρακτήρες;

569
00:26:22,830 --> 00:26:25,090
Τι είναι αυτό το πρόγραμμα πρόκειται να κάνει;

570
00:26:25,090 --> 00:26:29,360
Δυνητικά SEG σφάλμα. Είναι πρόκειται
να αντιγράψετε τυφλά ό, τι στο μπαρ μέχρι

571
00:26:29,360 --> 00:26:31,750
με το μήκος του, η οποία είναι
κυριολεκτικά τα πάντα στο μπαρ,

572
00:26:31,750 --> 00:26:36,307
στην διεύθυνση επισήμανε σε C. Αλλά C
έχει μόνο προληπτικά δίνεται ως 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Αλλά δεν υπάρχει κανένας πρόσθετος έλεγχος.

574
00:26:37,640 --> 00:26:38,700
Δεν υπάρχει, αν οι συνθήκες.

575
00:26:38,700 --> 00:26:40,580
Δεν υπάρχει έλεγχος σφαλμάτων εδώ.

576
00:26:40,580 --> 00:26:43,270
>> Και έτσι ό, τι αυτό το πρόγραμμα είναι
πρόκειται να κάνουμε είναι ακριβώς τυφλά

577
00:26:43,270 --> 00:26:45,750
αντιγράψετε ένα πράγμα στο άλλο.

578
00:26:45,750 --> 00:26:47,880
Και έτσι, αν βγάλουμε αυτό
ως εικόνα, είναι εδώ

579
00:26:47,880 --> 00:26:49,860
μόνο μια φέτα του χώρου μνήμης.

580
00:26:49,860 --> 00:26:53,470
Έτσι παρατηρήσετε στο κάτω μέρος, που
έχουν την τοπική μεταβλητή γραμμή.

581
00:26:53,470 --> 00:26:57,330
Έτσι, αυτό το δείκτη που πρόκειται να store--
και όχι ότι η τοπική επιχείρημα ότι είναι

582
00:26:57,330 --> 00:26:58,672
πρόκειται να αποθηκεύσετε τη γραμμή κορδόνι.

583
00:26:58,672 --> 00:27:00,380
Και στη συνέχεια, μόλις παρατηρήσετε
πάνω από αυτό σε μια στοίβα,

584
00:27:00,380 --> 00:27:02,505
γιατί κάθε φορά που θα ρωτήσω
για τη μνήμη στη στοίβα,

585
00:27:02,505 --> 00:27:04,310
πηγαίνει λίγο
πάνω από αυτό με εικόνες,

586
00:27:04,310 --> 00:27:06,270
Παρατηρήστε ότι έχουμε 12 bytes εκεί.

587
00:27:06,270 --> 00:27:10,690
Το κορυφαίο αριστερό βραχίονα C είναι μηδέν και
το κάτω δεξιά ένα είναι C βραχίονα 11.

588
00:27:10,690 --> 00:27:12,870
Αυτό είναι ακριβώς το πώς οι υπολογιστές
πρόκειται να το βάλω έξω.

589
00:27:12,870 --> 00:27:18,300
Έτσι απλά διαισθητικά, αν έχει περισσότερες
από 12 χαρακτήρες συνολικά, συμπεριλαμβανομένων

590
00:27:18,300 --> 00:27:25,790
η ανάστροφη κάθετο μηδέν, όπου είναι η
12 ή το βραχίονα C 12 πρόκειται να πάει;

591
00:27:25,790 --> 00:27:28,440
Ή μάλλον, όπου είναι η 12η
χαρακτήρα ή το 13ο χαρακτήρα,

592
00:27:28,440 --> 00:27:30,900
η εκατοστή χαρακτήρα θα
για να καταλήξει στην εικόνα;

593
00:27:30,900 --> 00:27:33,400
Πάνω ή κάτω;

594
00:27:33,400 --> 00:27:36,300
>> Δεξιά, γιατί ακόμα κι αν
η ίδια η στοίβα μεγαλώνει προς τα πάνω,

595
00:27:36,300 --> 00:27:39,590
τη στιγμή που έχετε βάλει τα πράγματα σε
αυτό, για λόγους σχεδίασης,

596
00:27:39,590 --> 00:27:41,294
βάζει τη μνήμη από πάνω προς τα κάτω.

597
00:27:41,294 --> 00:27:44,460
Έτσι, αν έχετε περισσότερα από 12 bytes,
θα πάμε να αρχίσουν να αντικαταστήσετε μπαρ.

598
00:27:44,460 --> 00:27:47,280
Τώρα αυτό είναι ένα bug, αλλά είναι
δεν είναι πραγματικά μια μεγάλη υπόθεση.

599
00:27:47,280 --> 00:27:51,130
Αλλά είναι μια μεγάλη υπόθεση, γιατί υπάρχει
περισσότερα πράγματα συμβαίνουν στη μνήμη.

600
00:27:51,130 --> 00:27:53,074
Τόσο εδώ είναι πώς μπορούμε να
θέσει ένα γεια, να είναι σαφής.

601
00:27:53,074 --> 00:27:54,490
Αν έχω πληκτρολογήσει στο γεια στη γραμμή.

602
00:27:54,490 --> 00:27:59,330
Η-Ε-Ε-Ε-Ο ανάποδη μηδέν, καταλήγει στο
αυτά τα 12 bytes, και είμαστε εξαιρετικά ασφαλή.

603
00:27:59,330 --> 00:28:00,330
Όλα είναι καλά.

604
00:28:00,330 --> 00:28:03,020
Αλλά αν πληκτρολογήσετε κάτι
πλέον, είναι δυνητικά

605
00:28:03,020 --> 00:28:05,860
πρόκειται να παρεισφρήσουν χώρο μπαρ.

606
00:28:05,860 --> 00:28:08,405
Ακόμα χειρότερα όμως, αποδεικνύεται
από όλο αυτό το διάστημα,

607
00:28:08,405 --> 00:28:11,530
ακόμα κι αν ποτέ δεν έχουμε μιλήσει για
αυτό, η στοίβα χρησιμοποιείται για άλλα πράγματα.

608
00:28:11,530 --> 00:28:13,560
Δεν είναι μόνο τοπικές μεταβλητές.

609
00:28:13,560 --> 00:28:15,100
>> C είναι ένα πολύ χαμηλό επίπεδο γλώσσας.

610
00:28:15,100 --> 00:28:17,810
Και αυτό το είδος της κρυφά
χρησιμοποιεί τη στοίβα επίσης

611
00:28:17,810 --> 00:28:21,260
πρέπει να θυμάστε όταν ένας
λειτουργία ονομάζεται, τι

612
00:28:21,260 --> 00:28:26,040
η διεύθυνση είναι της προηγούμενης λειτουργίας,
έτσι ώστε να μπορεί να πηδήσει πίσω σε αυτή τη λειτουργία.

613
00:28:26,040 --> 00:28:29,980
Έτσι, όταν η κύρια κλήσεις ανταλλάξουν, μεταξύ
τα πράγματα ωθούνται στη στοίβα

614
00:28:29,980 --> 00:28:34,380
Δεν είναι μόνο swaps τοπικές μεταβλητές,
ή τα επιχειρήματά της, επίσης κρυφά έσπρωξε

615
00:28:34,380 --> 00:28:37,510
στη στοίβα όπως αντιπροσωπεύεται
από το κόκκινο φέτα εδώ,

616
00:28:37,510 --> 00:28:40,520
είναι η διεύθυνση του κύριου φυσικώς
στη μνήμη του υπολογιστή σας,

617
00:28:40,520 --> 00:28:44,180
έτσι ώστε όταν ανταλλαγής γίνεται, ο υπολογιστής
ξέρει ότι πρέπει να πάμε πίσω στο κύριο

618
00:28:44,180 --> 00:28:46,760
και να τελειώσει την εκτέλεση της κύριας λειτουργίας.

619
00:28:46,760 --> 00:28:51,960
Έτσι, αυτό είναι επικίνδυνο τώρα, γιατί αν
πληκτρολογεί ο χρήστης και περισσότερο από ένα γεια,

620
00:28:51,960 --> 00:28:57,030
έτσι ώστε είσοδος του χρήστη clobbers
ή αντικαθιστά το κόκκινο τμήμα,

621
00:28:57,030 --> 00:28:59,820
λογικά αν ο υπολογιστή
ακριβώς πρόκειται να αναλάβει τυφλά

622
00:28:59,820 --> 00:29:03,830
ότι τα bytes σε αυτό το κόκκινο φέτα είναι
τη διεύθυνση στην οποία πρέπει να επιστρέψει,

623
00:29:03,830 --> 00:29:09,020
Τι κι αν ο αντίπαλος είναι αρκετά έξυπνος ή
αρκετά τυχεροί να θέσει μια σειρά από bytes

624
00:29:09,020 --> 00:29:13,450
εκεί που μοιάζει με μια διεύθυνση,
αλλά είναι η διεύθυνση του κώδικα

625
00:29:13,450 --> 00:29:18,730
ότι αυτός ή αυτή θέλει τον υπολογιστή
να εκτελέσει αντί του κύριου;

626
00:29:18,730 --> 00:29:21,670
>> Με άλλα λόγια, αν αυτό το
χρήστης πληκτρολογεί στη γραμμή,

627
00:29:21,670 --> 00:29:23,850
Δεν είναι μόνο κάτι
αβλαβείς, όπως γειά σου,

628
00:29:23,850 --> 00:29:28,210
αλλά στην πραγματικότητα είναι κώδικας που είναι ισοδύναμη
για να διαγράψετε όλα τα αρχεία του χρήστη;

629
00:29:28,210 --> 00:29:30,060
Ή email Κωδικός πρόσβασης τους σε μένα;

630
00:29:30,060 --> 00:29:31,940
Ή ξεκινήσει η καταγραφή τους
πληκτρολογήσεις, σωστά;

631
00:29:31,940 --> 00:29:34,920
Υπάρχει ένας τρόπος, ας προβλέπουν σήμερα,
ότι θα μπορούσαν να πληκτρολογήσετε όχι μόνο γεια

632
00:29:34,920 --> 00:29:36,711
κόσμο ή το όνομά τους,
θα μπορούσαν κατ 'ουσίαν

633
00:29:36,711 --> 00:29:39,570
περνούν στον κώδικα, και μηδενικά
αυτά, ότι ο υπολογιστής

634
00:29:39,570 --> 00:29:43,450
τα λάθη και για τις δύο κώδικα και μια διεύθυνση.

635
00:29:43,450 --> 00:29:48,950
Έτσι, αν και κάπως αφηρημένα, εάν η
πληκτρολογεί ο χρήστης σε αρκετά αντιμωλία κώδικα

636
00:29:48,950 --> 00:29:52,330
ότι θα γενικεύσουμε εδώ
Α Α είναι επίθεση ή αντιπάλους.

637
00:29:52,330 --> 00:29:53,140
Έτσι απλά κακά πράγματα.

638
00:29:53,140 --> 00:29:55,306
Εμείς δεν νοιάζονται για το
αριθμούς ή τα μηδενικά ή αυτές

639
00:29:55,306 --> 00:29:59,470
σήμερα, έτσι ώστε να καταλήξουμε
αντικαθιστώντας το κόκκινο τμήμα,

640
00:29:59,470 --> 00:30:01,580
παρατηρήσετε ότι η ακολουθία των bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C μηδέν οκτώ μηδέν.

642
00:30:05,020 --> 00:30:08,960
Και τώρα, όπως το άρθρο της Wikipedia εδώ
έχει προτείνει, αν τώρα πραγματικά να αρχίσετε

643
00:30:08,960 --> 00:30:12,460
επισήμανση των bytes στο του υπολογιστή σας
μνήμη, ό, τι το άρθρο της Wikipedia είναι

644
00:30:12,460 --> 00:30:19,060
προτείνουσα είναι ότι, ό, τι και αν η διεύθυνση
του εν λόγω πάνω αριστερά byte είναι 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Με άλλα λόγια, αν ο κακός είναι
αρκετά έξυπνος με τον κωδικό του ή της

646
00:30:22,200 --> 00:30:26,650
να βάλει πραγματικά έναν αριθμό που εδώ
αντιστοιχεί στη διεύθυνση του κώδικα

647
00:30:26,650 --> 00:30:29,180
αυτός ή αυτή εγχέεται
στον υπολογιστή, μπορείτε

648
00:30:29,180 --> 00:30:31,050
μπορεί να εξαπατήσει τον υπολογιστή
στο να κάνει κάτι.

649
00:30:31,050 --> 00:30:34,140
Αφαίρεση αρχείων, ηλεκτρονικό ταχυδρομείο
πράγματα, εισπνοή της κυκλοφορίας σας,

650
00:30:34,140 --> 00:30:36,710
κυριολεκτικά οτιδήποτε θα μπορούσε να είναι
εγχέεται μέσα στον υπολογιστή.

651
00:30:36,710 --> 00:30:39,220
Και έτσι η υπερχείλιση του buffer
επίθεση στον πυρήνα της

652
00:30:39,220 --> 00:30:43,530
είναι απλά μια ηλίθια, ηλίθια
επιτακτικών έναν πίνακα που

653
00:30:43,530 --> 00:30:45,840
δεν έχει τα όριά της ελεγχθούν.

654
00:30:45,840 --> 00:30:48,850
Και αυτό είναι ό, τι είναι εξαιρετικά επικίνδυνη
και ταυτόχρονα σούπερ ισχυρό

655
00:30:48,850 --> 00:30:52,560
σε C είναι ότι έχουμε πράγματι
πρόσβαση σε οποιοδήποτε σημείο στη μνήμη.

656
00:30:52,560 --> 00:30:55,320
Είναι στο χέρι μας, οι προγραμματιστές,
που γράφουν το αρχικό κώδικα

657
00:30:55,320 --> 00:30:59,330
για να ελέγξετε το μήκος του κάθε καταριέται
πίνακες που είμαστε χειρισμό.

658
00:30:59,330 --> 00:31:00,750
Έτσι για να είναι σαφές, ποια είναι η λύση;

659
00:31:00,750 --> 00:31:03,190
Αν επαναφέρετε σε αυτό
κώδικα, δεν πρέπει απλώς να

660
00:31:03,190 --> 00:31:08,000
αλλάξετε το μήκος της ράβδου, τι
αλλιώς θα πρέπει να είμαι έλεγχο;

661
00:31:08,000 --> 00:31:10,620
Τι άλλο πρέπει να να κάνει για να
αποτρέψετε αυτήν την επίθεση εξ ολοκλήρου;

662
00:31:10,620 --> 00:31:14,110
Δεν θέλω να πω ακριβώς τυφλά
ότι θα πρέπει να αντιγράψετε και πολλά bytes

663
00:31:14,110 --> 00:31:16,140
όπως είναι το μήκος της ράβδου.

664
00:31:16,140 --> 00:31:18,910
Θέλω να πω, όπως αντιγραφή
ο αριθμός των bytes που βρίσκονται σε μπαρ

665
00:31:18,910 --> 00:31:24,090
μέχρι η χορηγούμενη
μνήμη, ή 12 μέγιστα.

666
00:31:24,090 --> 00:31:27,450
Γι 'αυτό χρειάζεται κάποιο είδος αν η κατάσταση
ότι δεν ελέγχει το μήκος της ράβδου,

667
00:31:27,450 --> 00:31:32,800
αλλά αν υπερβαίνει το 12, εμείς απλά σκληρά κώδικα
12 ως η μέγιστη δυνατή απόσταση.

668
00:31:32,800 --> 00:31:35,910
Διαφορετικά, η λεγόμενη ρυθμιστικό
επίθεση υπερχείλισης μπορεί να συμβεί.

669
00:31:35,910 --> 00:31:38,451
Στο κάτω μέρος των εν λόγω διαφάνειες,
αν είστε περίεργοι να διαβάσετε περισσότερα

670
00:31:38,451 --> 00:31:41,200
είναι η πραγματική αρχικό άρθρο
αν θέλετε να ρίξετε μια ματιά.

671
00:31:41,200 --> 00:31:44,550
>> Αλλά τώρα, μεταξύ των τιμών
που καταβάλλονται εδώ ήταν ανεπάρκειες.

672
00:31:44,550 --> 00:31:46,680
Έτσι ώστε ήταν μια γρήγορη
χαμηλό επίπεδο ματιά σε ό, τι

673
00:31:46,680 --> 00:31:49,709
μπορεί να προκύψουν προβλήματα τώρα που έχουμε
να έχουν πρόσβαση σε μνήμη υπολογιστή.

674
00:31:49,709 --> 00:31:51,750
Αλλά ένα άλλο πρόβλημα που
ήδη σκόνταψε τη Δευτέρα

675
00:31:51,750 --> 00:31:53,800
ήταν μόνο η αναποτελεσματικότητα
από μία συνδεδεμένη λίστα.

676
00:31:53,800 --> 00:31:56,019
Είμαστε πίσω σε γραμμικό χρόνο.

677
00:31:56,019 --> 00:31:57,560
Δεν έχουμε πλέον ένα συνεχόμενο πίνακα.

678
00:31:57,560 --> 00:31:58,980
Δεν έχουμε τυχαίας προσπέλασης.

679
00:31:58,980 --> 00:32:00,710
Δεν μπορούμε να χρησιμοποιήσουμε πλατεία συμβολισμός βραχίονα.

680
00:32:00,710 --> 00:32:04,590
Έχουμε κυριολεκτικά πρέπει να χρησιμοποιήσετε ένα βρόχο while
όπως αυτό που έγραψα πριν από λίγο.

681
00:32:04,590 --> 00:32:09,740
Αλλά τη Δευτέρα, εμείς ισχυρίστηκε ότι μπορούμε
σέρνονται πίσω στη σφαίρα της αποτελεσματικότητας

682
00:32:09,740 --> 00:32:13,040
επιτυγχάνοντας κάτι που είναι
λογαριθμική ίσως, ή καλύτερα ακόμα,

683
00:32:13,040 --> 00:32:16,120
ίσως ακόμα και κάτι που είναι
λεγόμενη σταθερά χρόνου.

684
00:32:16,120 --> 00:32:19,840
Λοιπόν, πώς μπορούμε να το κάνουμε αυτό με την χρήση αυτών των νέων
εργαλεία, αυτές οι διευθύνσεις, οι δείκτες,

685
00:32:19,840 --> 00:32:22,210
threading και τα πράγματα του δικού μας;

686
00:32:22,210 --> 00:32:23,960
Λοιπόν, ας υποθέσουμε ότι
Εδώ, αυτά είναι ένα μάτσο

687
00:32:23,960 --> 00:32:27,170
των αριθμών που θέλετε να αποθηκεύσετε σε ένα
δομή των δεδομένων και την αναζήτηση αποτελεσματικά.

688
00:32:27,170 --> 00:32:30,960
Πρέπει οπωσδήποτε να κάνετε rewind σε εβδομάδα
δύο, να ρίξει αυτά σε μια σειρά,

689
00:32:30,960 --> 00:32:33,150
και να κάνετε χρήση της δυαδικής αναζήτησης.

690
00:32:33,150 --> 00:32:34,040
Διαίρει και βασίλευε.

691
00:32:34,040 --> 00:32:37,720
Και στην πραγματικότητα γράψατε
δυαδική αναζήτηση στο PSET3,

692
00:32:37,720 --> 00:32:40,100
όπου θα εφαρμοστεί το πρόγραμμα εύρημα.

693
00:32:40,100 --> 00:32:40,890
Αλλά ξέρετε τι.

694
00:32:40,890 --> 00:32:45,060
Υπάρχει το είδος της μια πιο
έξυπνος τρόπος για να γίνει αυτό.

695
00:32:45,060 --> 00:32:47,390
Είναι λίγο πιο
εξελιγμένα και ίσως

696
00:32:47,390 --> 00:32:50,830
μας επιτρέπει να δούμε γιατί δυαδικό
αναζήτησης είναι τόσο πολύ πιο γρήγορα.

697
00:32:50,830 --> 00:32:52,980
Κατ 'αρχάς, ας εισάγουν
η έννοια ενός δέντρου.

698
00:32:52,980 --> 00:32:54,730
Που αν και σε
δέντρα πραγματικότητα το είδος του

699
00:32:54,730 --> 00:32:57,730
μεγαλώνουν σαν αυτό, στον κόσμο των υπολογιστών
επιστήμη που το είδος του μεγαλώνουν προς τα κάτω

700
00:32:57,730 --> 00:33:00,830
σαν ένα οικογενειακό δέντρο, όπου έχετε
παππούδες σας ή μεγάλη παππούδες και γιαγιάδες

701
00:33:00,830 --> 00:33:04,580
ή οτιδήποτε στην κορυφή, τον πατριάρχη και
η γυναίκα αρχηγός φυλής της οικογένειας, μόνο ένα

702
00:33:04,580 --> 00:33:07,930
λεγόμενη ρίζα, κόμβος, παρακάτω
που είναι τα παιδιά της,

703
00:33:07,930 --> 00:33:11,442
κάτω από το οποίο είναι παιδιά της, ή
απόγονοι του γενικότερα.

704
00:33:11,442 --> 00:33:13,400
Και ο καθένας κρέμεται από
το κάτω μέρος της οικογένειας

705
00:33:13,400 --> 00:33:16,070
δέντρο, εκτός του ότι η
νεότερος στην οικογένεια,

706
00:33:16,070 --> 00:33:19,520
Μπορείτε επίσης απλά να είναι γενικά
ονομάζονται τα φύλλα του δέντρου.

707
00:33:19,520 --> 00:33:21,800
>> Έτσι, αυτό είναι απλά ένα μάτσο
των λέξεων και ορισμοί

708
00:33:21,800 --> 00:33:25,790
για κάτι που ονομάζεται ένα δέντρο στον υπολογιστή
επιστήμη, σαν ένα οικογενειακό δέντρο.

709
00:33:25,790 --> 00:33:28,770
Αλλά υπάρχει εκτροφέα ενσαρκώσεις
δέντρα, ένας από τους οποίους

710
00:33:28,770 --> 00:33:30,780
ονομάζεται δυαδικό δένδρο αναζήτησης.

711
00:33:30,780 --> 00:33:34,380
Και μπορείτε να το είδος της πειράζω
πέρα τι κάνει αυτό το πράγμα.

712
00:33:34,380 --> 00:33:37,180
Λοιπόν, αυτό είναι δυαδικό με ποια έννοια;

713
00:33:37,180 --> 00:33:41,455
Πού το δυαδικό προέρχονται από εδώ;

714
00:33:41,455 --> 00:33:41,955
Συγνώμη;

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Δεν είναι τόσο πολύ ένα ή.

717
00:33:47,210 --> 00:33:52,000
Είναι περισσότερο ότι κάθε ένα από τους κόμβους δεν έχει
περισσότερα από δύο παιδιά, όπως βλέπουμε εδώ.

718
00:33:52,000 --> 00:33:54,990
Σε γενικές γραμμές, μια tree-- και
τους γονείς και τους παππούδες σας

719
00:33:54,990 --> 00:33:57,640
μπορεί να έχει ως πολλά παιδιά ή
εγγόνια που πραγματικά θέλουν,

720
00:33:57,640 --> 00:34:00,820
και έτσι, για παράδειγμα, εκεί έχουμε τρεις
τα παιδιά μακριά από τον κόμβο δεξί χέρι,

721
00:34:00,820 --> 00:34:05,480
αλλά σε ένα δυαδικό δένδρο, ένας κόμβος έχει
μηδέν, ένα, ή δύο παιδιά μέγιστα.

722
00:34:05,480 --> 00:34:08,496
Και αυτό είναι μια ωραία ιδιοκτησία,
γιατί αν είναι καλυμμένο από δύο,

723
00:34:08,496 --> 00:34:10,620
θα πάμε να είναι σε θέση να
πάρετε μια μικρή βάση καταγραφής δύο

724
00:34:10,620 --> 00:34:11,975
δράση που συμβαίνει εδώ τελικά.

725
00:34:11,975 --> 00:34:13,350
Έτσι έχουμε κάτι λογαριθμική.

726
00:34:13,350 --> 00:34:14,558
Αλλά περισσότερα για αυτό σε μια στιγμή.

727
00:34:14,558 --> 00:34:19,810
Αναζήτηση δέντρο σημαίνει ότι οι αριθμοί είναι
διευθετείται έτσι ώστε το αριστερό του παιδιού

728
00:34:19,810 --> 00:34:22,429
τιμή είναι μεγαλύτερη από τη ρίζα.

729
00:34:22,429 --> 00:34:26,010
Και το δικαίωμα του παιδιού της είναι
μεγαλύτερο από τη ρίζα.

730
00:34:26,010 --> 00:34:29,290
Με άλλα λόγια, εάν παίρνετε οποιοδήποτε από τα
κόμβους, οι κύκλοι σε αυτή την εικόνα,

731
00:34:29,290 --> 00:34:31,840
και κοιτάζει αριστερά του
το παιδί και το δικαίωμα του παιδιού του,

732
00:34:31,840 --> 00:34:34,739
η πρώτη θα πρέπει να είναι μικρότερη από,
το δεύτερο θα πρέπει να είναι μεγαλύτερη από ό, τι.

733
00:34:34,739 --> 00:34:36,159
Έτσι, η λογική ελέγχει 55.

734
00:34:36,159 --> 00:34:37,780
Είναι άφησε το παιδί είναι 33.

735
00:34:37,780 --> 00:34:38,620
Είναι λιγότερο από ό, τι.

736
00:34:38,620 --> 00:34:40,929
55, το δικαίωμα του παιδιού της είναι 77.

737
00:34:40,929 --> 00:34:41,783
Είναι περισσότερο από ό, τι.

738
00:34:41,783 --> 00:34:43,199
Και αυτό είναι ένα αναδρομικό ορισμό.

739
00:34:43,199 --> 00:34:46,480
Θα μπορούσαμε να ελέγχει κάθε ένα από αυτά
κόμβους και το ίδιο μοτίβο θα κρατήσει.

740
00:34:46,480 --> 00:34:49,389
>> Έτσι τι είναι ωραίο σε μια
δυαδικό δένδρο αναζήτησης, είναι

741
00:34:49,389 --> 00:34:52,204
ότι το ένα, μπορούμε να την εφαρμόσουν
με ένα struct, όπως ακριβώς αυτό.

742
00:34:52,204 --> 00:34:54,620
Και ακόμα κι αν είμαστε ρίχνουν
παρτίδες των δομών σε σας,

743
00:34:54,620 --> 00:34:56,560
ότι είναι κάπως
διαισθητική τώρα ελπίζουμε.

744
00:34:56,560 --> 00:35:00,570
Η σύνταξη είναι ακόμα σίγουροι για απόκρυφες,
αλλά τα περιεχόμενα ενός κόμβου σε αυτό

745
00:35:00,570 --> 00:35:02,786
context-- και κρατάμε
χρησιμοποιώντας τη λέξη κόμβο,

746
00:35:02,786 --> 00:35:04,910
είτε πρόκειται για ένα ορθογώνιο
στην οθόνη ή έναν κύκλο,

747
00:35:04,910 --> 00:35:08,970
είναι μερικά μόνο από γενική δοχείο,
σε αυτή την περίπτωση ενός δέντρου, όπως εκείνη

748
00:35:08,970 --> 00:35:11,780
είδαμε, χρειαζόμαστε έναν ακέραιο
σε κάθε ένα από τους κόμβους

749
00:35:11,780 --> 00:35:15,460
και στη συνέχεια θα πρέπει δίποντα κατάδειξης
προς τα αριστερά παιδιού και το δικαίωμα του παιδιού,

750
00:35:15,460 --> 00:35:16,590
αντίστοιχα.

751
00:35:16,590 --> 00:35:20,730
Έτσι, αυτό είναι το πώς θα μπορούσαμε
εφαρμόσουν ότι σε μια struct.

752
00:35:20,730 --> 00:35:22,315
Και πώς θα μπορούσε να μπορώ να εφαρμόσουν τον κωδικό;

753
00:35:22,315 --> 00:35:26,730
Λοιπόν, ας ρίξουμε μια γρήγορη
ματιά σε αυτό το μικρό παράδειγμα.

754
00:35:26,730 --> 00:35:29,820
Δεν είναι λειτουργική, αλλά έχω
αντιγραφεί και επικολληθεί αυτή τη δομή.

755
00:35:29,820 --> 00:35:33,510
Και αν η λειτουργία μου για ένα δυαδικό
δέντρο αναζήτησης ονομάζεται αναζήτηση,

756
00:35:33,510 --> 00:35:36,980
και αυτό παίρνει δύο επιχειρήματα,
ένας ακέραιος Ν και ένα δείκτη

757
00:35:36,980 --> 00:35:41,400
σε ένα κόμβο, έτσι ένα δείκτη στο δέντρο
ή ένας δείκτης στη ρίζα ενός δέντρου,

758
00:35:41,400 --> 00:35:43,482
πώς μπορώ να πάω για την αναζήτηση για το Ν;

759
00:35:43,482 --> 00:35:45,440
Λοιπόν, πρώτα, γιατί είμαι
που ασχολούνται με δείκτες,

760
00:35:45,440 --> 00:35:46,750
Πάω να κάνω μια επιταγή λογική.

761
00:35:46,750 --> 00:35:54,279
Αν ίσων δέντρο ισούται με null, είναι Ν
σε αυτό το δέντρο ή όχι σε αυτό το δέντρο;

762
00:35:54,279 --> 00:35:55,070
Δεν μπορεί να είναι, σωστά;

763
00:35:55,070 --> 00:35:56,870
Αν είμαι παρελθόν null,
δεν υπάρχει τίποτα εκεί.

764
00:35:56,870 --> 00:35:59,230
Θα μπορούσαμε απλώς να
τυφλά λένε επιστρέφει false.

765
00:35:59,230 --> 00:36:04,050
Αν μου δώσεις τίποτα, εγώ σίγουρα δεν μπορεί να
βρείτε οποιοδήποτε αριθμό Ν Λοιπόν, τι άλλο μπορεί να μου

766
00:36:04,050 --> 00:36:04,750
ελέγχει τώρα;

767
00:36:04,750 --> 00:36:12,830
Πάω να πω και άλλο αν το Ν είναι
λιγότερο από ό, τι είναι στο κόμβο του δένδρου

768
00:36:12,830 --> 00:36:16,300
ότι έχω παραδοθεί Ν αξία.

769
00:36:16,300 --> 00:36:20,270
Με άλλα λόγια, εάν ο αριθμός είμαι
ψάχνουν, N, είναι μικρότερο από τον κόμβο

770
00:36:20,270 --> 00:36:21,340
ότι κοιτάω.

771
00:36:21,340 --> 00:36:23,190
Και ο κόμβος Ψάχνω
σε ονομάζεται δέντρο,

772
00:36:23,190 --> 00:36:26,370
και ανάκληση από το προηγούμενο παράδειγμα
για να πάρει την τιμή σε ένα δείκτη,

773
00:36:26,370 --> 00:36:28,310
Μπορώ να χρησιμοποιήσω το συμβολισμό βέλος.

774
00:36:28,310 --> 00:36:35,960
Έτσι, αν το Ν είναι μικρότερο από το βέλος δέντρο
Ν, θέλω να πάω εννοιολογικά αριστερά.

775
00:36:35,960 --> 00:36:38,590
Πώς μπορώ να εκφράζουν τα αριστερά η αναζήτηση;

776
00:36:38,590 --> 00:36:41,560
Για να είμαι σαφής, αν αυτό είναι
η εν λόγω εικόνα,

777
00:36:41,560 --> 00:36:44,612
και έχω περάσει ότι κορυφαιους
arrow ότι είναι στραμμένο προς τα κάτω.

778
00:36:44,612 --> 00:36:45,570
Αυτός είναι ο δείκτης δέντρο μου.

779
00:36:45,570 --> 00:36:48,060
Είμαι δείχνει στη ρίζα του δέντρου.

780
00:36:48,060 --> 00:36:52,100
Και ψάχνω για παράδειγμα, για
ο αριθμός 44, αυθαίρετα.

781
00:36:52,100 --> 00:36:55,300
Είναι 44 ή μικρότερη
μεγαλύτερη από 55 προφανώς;

782
00:36:55,300 --> 00:36:56,360
Γι 'αυτό είναι λιγότερο από ό, τι.

783
00:36:56,360 --> 00:36:58,760
Και έτσι αυτή η προϋπόθεση δεν ισχύει αν.

784
00:36:58,760 --> 00:37:03,981
Έτσι εννοιολογικά, τι θέλω να
αναζήτηση Επόμενο αν ψάχνω για 44;

785
00:37:03,981 --> 00:37:04,480
Ναι;

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Ακριβώς, θέλω να
αναζήτηση στο αριστερό παιδί,

788
00:37:11,100 --> 00:37:12,789
ή το αριστερό υπο-δέντρο αυτής της εικόνας.

789
00:37:12,789 --> 00:37:14,830
Και στην πραγματικότητα, επιτρέψτε μου μέσα
η εικόνα εδώ κάτω

790
00:37:14,830 --> 00:37:17,770
για μια στιγμή, δεδομένου ότι
Δεν μπορώ να το μηδέν αυτό.

791
00:37:17,770 --> 00:37:21,150
Αν αρχίσω εδώ στο 55, και
Γνωρίζω ότι η τιμή 44

792
00:37:21,150 --> 00:37:23,180
Ψάχνω για να
η αριστερά, είναι το είδος

793
00:37:23,180 --> 00:37:26,010
σαν λυσσασμένο τον τηλεφωνικό κατάλογο στο
το μισό ή το σχίσιμο του δέντρου στο μισό.

794
00:37:26,010 --> 00:37:29,660
Δεν έχω πλέον να νοιάζονται για
όλη αυτή μισο του δέντρου.

795
00:37:29,660 --> 00:37:33,270
Και όμως, περιέργως από την άποψη της
δομή, αυτό το πράγμα εδώ ότι

796
00:37:33,270 --> 00:37:36,682
ξεκινά με 33, ότι η ίδια η
είναι ένα δυαδικό δένδρο αναζήτησης.

797
00:37:36,682 --> 00:37:39,890
Είπα τη λέξη αναδρομικό πριν, διότι
Πράγματι, αυτό είναι μια δομή δεδομένων που

798
00:37:39,890 --> 00:37:41,707
εξ ορισμού είναι αναδρομική.

799
00:37:41,707 --> 00:37:44,540
Μπορεί να έχετε ένα δέντρο που είναι αυτό
μεγάλο, αλλά κάθε ένα από τα παιδιά του

800
00:37:44,540 --> 00:37:46,870
αντιπροσωπεύει ένα δέντρο λίγο μικρότερο.

801
00:37:46,870 --> 00:37:50,910
Αντί να είναι ο παππούς
ή γιαγιά, τώρα είναι απλά η μαμά

802
00:37:50,910 --> 00:37:54,300
or-- Δεν μπορώ να μην say-- μαμά
ή τον μπαμπά, ότι θα ήταν παράξενο.

803
00:37:54,300 --> 00:37:59,000
Αντ 'αυτού τα δύο παιδιά εκεί
θα ήταν σαν τον αδελφό και αδελφών.

804
00:37:59,000 --> 00:38:01,120
Μια νέα γενιά του οικογενειακού δέντρου.

805
00:38:01,120 --> 00:38:02,900
Αλλά δομικά, είναι η ίδια ιδέα.

806
00:38:02,900 --> 00:38:06,790
Και αποδεικνύεται έχω μια λειτουργία
με την οποία μπορώ να αναζητήσω μια δυαδική αναζήτηση

807
00:38:06,790 --> 00:38:07,290
δέντρο.

808
00:38:07,290 --> 00:38:08,680
Ονομάζεται αναζήτησης.

809
00:38:08,680 --> 00:38:17,870
Ψάχνει για Ν στο δέντρο βέλος αριστερά
αλλιώς εάν Ν είναι μεγαλύτερη από την τιμή

810
00:38:17,870 --> 00:38:18,870
ότι είμαι σήμερα σε.

811
00:38:18,870 --> 00:38:20,800
55 στην ιστορία πριν από λίγο.

812
00:38:20,800 --> 00:38:23,780
Έχω μια λειτουργία που ονομάζεται
αναζήτησης που μπορώ μόνο

813
00:38:23,780 --> 00:38:29,660
Ν περάσει αυτό και αναδρομικά αναζήτηση
η υπο-δέντρο και μόλις επιστροφή

814
00:38:29,660 --> 00:38:30,620
όποια και αν είναι η απάντηση.

815
00:38:30,620 --> 00:38:33,530
Αλλιώς έχω κάποια τελευταία περίπτωση βάση εδώ.

816
00:38:33,530 --> 00:38:35,310
>> Ποια είναι η τελική υπόθεση;

817
00:38:35,310 --> 00:38:36,570
Δέντρο είναι είτε μηδενική.

818
00:38:36,570 --> 00:38:39,980
Η αξία Είμαι είτε ψάχνετε είναι
λιγότερο από ό, ή μεγαλύτερη από εκείνη

819
00:38:39,980 --> 00:38:42,610
ή ίση με αυτό.

820
00:38:42,610 --> 00:38:44,750
Και θα μπορούσα να πω ίση
ίσα, αλλά λογικά είναι

821
00:38:44,750 --> 00:38:46,500
ισοδύναμη με απλά λέγοντας άλλο εδώ.

822
00:38:46,500 --> 00:38:49,150
Έτσι αλήθεια είναι πώς μπορώ να βρω κάτι.

823
00:38:49,150 --> 00:38:51,710
Έτσι, ελπίζουμε ότι αυτό είναι ένα
ακόμη πιο συναρπαστικό παράδειγμα

824
00:38:51,710 --> 00:38:54,900
από τη λειτουργία ηλίθιο σίγμα
Κάναμε μερικές διαλέξεις πίσω,

825
00:38:54,900 --> 00:38:58,360
όπου ήταν εξίσου εύκολο να χρησιμοποιήσετε ένα βρόχο
να μετρήσετε όλους τους αριθμούς από το ένα

826
00:38:58,360 --> 00:39:02,390
να N. Εδώ με μία δομή δεδομένων
ότι η ίδια είναι αναδρομικά

827
00:39:02,390 --> 00:39:07,050
ορίζεται αναδρομικά και που, τώρα είμαστε
έχουν την ικανότητα να εκφραστούμε

828
00:39:07,050 --> 00:39:09,780
στον κώδικα που η ίδια έχει επαναληπτικό.

829
00:39:09,780 --> 00:39:12,580
Έτσι, αυτό είναι ακριβώς το ίδιο κωδικό εδώ.

830
00:39:12,580 --> 00:39:14,400
>> Λοιπόν, τι άλλα προβλήματα μπορούμε να λύσουμε;

831
00:39:14,400 --> 00:39:18,160
Έτσι, ένα γρήγορο βήμα μακριά από
δέντρα για μια στιγμή.

832
00:39:18,160 --> 00:39:20,130
Εδώ είναι, ας πούμε, τη γερμανική σημαία.

833
00:39:20,130 --> 00:39:22,020
Και είναι σαφές ότι υπάρχει
μοτίβο σε αυτήν τη σημαία.

834
00:39:22,020 --> 00:39:23,811
Και υπάρχουν πολλά
σημαίες στον κόσμο που

835
00:39:23,811 --> 00:39:27,560
είναι τόσο απλό όσο αυτό σε όρους
χρωμάτων και σχεδίων τους.

836
00:39:27,560 --> 00:39:31,930
Αλλά ας υποθέσουμε ότι αυτό αποθηκεύεται ως ένα
.gif, Ή σε μορφή JPEG ή bitmap, ή ping,

837
00:39:31,930 --> 00:39:34,240
οποιαδήποτε γραφική μορφή αρχείου
με το οποίο είστε εξοικειωμένοι,

838
00:39:34,240 --> 00:39:36,460
μερικά από τα οποία είμαστε
παίζουν με στο PSET4.

839
00:39:36,460 --> 00:39:41,550
Αυτό δεν φαίνεται να αποθηκεύσει αξιόλογη
μαύρο pixel, μαύρο pixel, μαύρο pixel,

840
00:39:41,550 --> 00:39:44,790
τελεία, τελεία, τελεία, ένα σωρό
μαύρα pixel για πρώτη scanline,

841
00:39:44,790 --> 00:39:47,430
ή γραμμή, τότε ένα σωρό
το ίδιο, τότε ένα σωρό

842
00:39:47,430 --> 00:39:49,530
του ίδιου, και στη συνέχεια μια
σωρό από κόκκινα εικονοστοιχεία,

843
00:39:49,530 --> 00:39:53,020
κόκκινα εικονοστοιχεία, κόκκινα εικονοστοιχεία, τότε ένας ολόκληρος
δέσμη των κίτρινα pixels, κίτρινο, σωστά;

844
00:39:53,020 --> 00:39:55,050
>> Υπάρχει τέτοια αναποτελεσματικότητα εδώ.

845
00:39:55,050 --> 00:39:59,040
Πώς θα διαισθητικά
συμπιέσει τη γερμανική σημαία

846
00:39:59,040 --> 00:40:01,320
όταν η εφαρμογή της ως ένα αρχείο;

847
00:40:01,320 --> 00:40:04,940
Όπως και το είδος των πληροφοριών δεν μπορούμε να
κόπο αποθήκευση στο δίσκο, προκειμένου

848
00:40:04,940 --> 00:40:08,040
για να μειώσετε το μέγεθος του αρχείου μας από παρόμοια
ένα megabyte σε kilobyte, κάτι

849
00:40:08,040 --> 00:40:09,430
μικρότερα;

850
00:40:09,430 --> 00:40:13,130
Όπου βρίσκεται η απόλυση
εδώ να είναι σαφές;

851
00:40:13,130 --> 00:40:13,880
Τι μπορείτε να κάνετε;

852
00:40:13,880 --> 00:40:14,380
Ναι;

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Ακριβώς.

855
00:40:21,970 --> 00:40:24,550
Γιατί δεν θυμόμαστε όχι
το χρώμα του κάθε pixel καταριέται

856
00:40:24,550 --> 00:40:28,200
όπως ακριβώς κάνετε στο PSET4
με τη μορφή αρχείου bitmap,

857
00:40:28,200 --> 00:40:32,060
γιατί δεν αντιπροσωπεύουν μόλις το
αριστερότερη στήλη εικονοστοιχείων, για παράδειγμα

858
00:40:32,060 --> 00:40:35,370
μια δέσμη των μαύρων pixels, ένα μάτσο
κόκκινο, και ένα σωρό κίτρινο,

859
00:40:35,370 --> 00:40:39,210
και στη συνέχεια απλά με κάποιο τρόπο να κωδικοποιεί το
ιδέα Επαναλάβετε αυτήν 100 φορές

860
00:40:39,210 --> 00:40:41,020
ή επαναλάβετε αυτό 1.000 φορές;

861
00:40:41,020 --> 00:40:43,430
Όταν το 100 ή 1.000 είναι
απλά ένας ακέραιος αριθμός, έτσι ώστε να

862
00:40:43,430 --> 00:40:47,290
μπορεί να περάσει με ένα μόνο αριθμό
αντί εκατοντάδες ή χιλιάδες

863
00:40:47,290 --> 00:40:48,270
πρόσθετων pixels.

864
00:40:48,270 --> 00:40:50,990
Και πράγματι, αυτό είναι το πώς εμείς
θα μπορούσε να συμπιέσει τη γερμανική σημαία.

865
00:40:50,990 --> 00:40:51,490
Και

866
00:40:51,490 --> 00:40:53,470
Τώρα τι γίνεται με τη γαλλική σημαία;

867
00:40:53,470 --> 00:40:58,930
Και λίγο κάποιο είδος
ψυχική άσκηση, η οποία σημαίας

868
00:40:58,930 --> 00:41:01,040
μπορεί να συμπιεστεί περισσότερο στο δίσκο;

869
00:41:01,040 --> 00:41:05,720
Η γερμανική σημαία ή η γαλλική
σημαία, αν πάρουμε αυτή την προσέγγιση;

870
00:41:05,720 --> 00:41:08,490
Η γερμανική σημαία, επειδή υπάρχει
περισσότερο οριζόντιες απολύσεις.

871
00:41:08,490 --> 00:41:12,190
Και από το σχεδιασμό, πολλά γραφικά αρχείο
μορφές όντως λειτουργούν ως γραμμές σάρωσης

872
00:41:12,190 --> 00:41:12,830
οριζόντια.

873
00:41:12,830 --> 00:41:14,674
Θα μπορούσε να λειτουργήσει
κάθετα, ακριβώς ανθρωπότητα

874
00:41:14,674 --> 00:41:17,090
αποφάσισε χρόνια πριν ότι θα
γενικά σκέφτομαι σειρά πραγμάτων

875
00:41:17,090 --> 00:41:18,880
από σειρά αντί ανά στήλη.

876
00:41:18,880 --> 00:41:20,820
Έτσι, πράγματι, αν ήταν
να εξετάσουμε το αρχείο

877
00:41:20,820 --> 00:41:24,670
το μέγεθος της μια γερμανική σημαία και ένα γαλλικό
σημαία, εφ 'όσον η ανάλυση είναι

878
00:41:24,670 --> 00:41:27,530
το ίδιο, το ίδιο πλάτος
και ύψος, αυτό

879
00:41:27,530 --> 00:41:31,580
Εδώ πρόκειται να είναι μεγαλύτερο, γιατί
Πρέπει να επαναλάβω τον εαυτό σας τρεις φορές.

880
00:41:31,580 --> 00:41:35,570
Θα πρέπει να καθορίσετε μπλε, επαναλάβετε
τον εαυτό σας, το λευκό, επαναλαμβάνω τον εαυτό σας, το κόκκινο,

881
00:41:35,570 --> 00:41:36,740
επαναλάβετε τον εαυτό σας.

882
00:41:36,740 --> 00:41:39,000
Μπορείτε όχι μόνο να πάνε όλα
ο τρόπος προς τα δεξιά.

883
00:41:39,000 --> 00:41:41,200
Και, παρεμπιπτόντως, να κάνει
καταργήστε την συμπίεση

884
00:41:41,200 --> 00:41:43,910
είναι παντού, αν αυτά είναι
τέσσερα καρέ από ένα video-- σας

885
00:41:43,910 --> 00:41:45,890
Ίσως να θυμάστε ότι μια ταινία
ή βίντεο είναι γενικά

886
00:41:45,890 --> 00:41:47,286
όπως 29 ή 30 καρέ ανά δευτερόλεπτο.

887
00:41:47,286 --> 00:41:50,410
Είναι σαν ένα μικρό κτύπημα βιβλίο όπου θα
απλά δείτε την εικόνα, εικόνα, εικόνα, εικόνα,

888
00:41:50,410 --> 00:41:54,410
εικόνα, απλά σούπερ γρήγορα ώστε να μοιάζει με
οι ηθοποιοί στην οθόνη κινούνται.

889
00:41:54,410 --> 00:41:57,130
Εδώ είναι ένα αγριομελισσών για
πάνω από ένα μπουκέτο λουλούδια.

890
00:41:57,130 --> 00:41:59,790
Και αν και θα μπορούσε να είναι το είδος του
δύσκολο να δει κανείς με την πρώτη ματιά,

891
00:41:59,790 --> 00:42:04,020
το μόνο πράγμα κινείται
Αυτή η ταινία είναι η μέλισσα.

892
00:42:04,020 --> 00:42:06,880
>> Τι είναι χαζή σχετικά με την αποθήκευση
βίντεο ασυμπίεστα;

893
00:42:06,880 --> 00:42:11,420
Είναι το είδος των αποβλήτων για την αποθήκευση βίντεο
και τέσσερις σχεδόν πανομοιότυπες εικόνες που

894
00:42:11,420 --> 00:42:13,670
διαφέρουν μόνο στο βαθμό που όταν η μέλισσα είναι.

895
00:42:13,670 --> 00:42:16,280
Μπορείτε να πετάξετε τα περισσότερα
των εν λόγω πληροφοριών

896
00:42:16,280 --> 00:42:20,190
και να θυμάστε μόνο, για παράδειγμα,
το πρώτο καρέ και το τελευταίο πλαίσιο,

897
00:42:20,190 --> 00:42:22,180
βασικά καρέ αν έχετε
ακούσει ποτέ τη λέξη,

898
00:42:22,180 --> 00:42:24,337
και αποθηκεύουν μόνο στην
μέση, όπου η μέλισσα είναι.

899
00:42:24,337 --> 00:42:26,170
Και δεν χρειάζεται να
Αποθηκεύουμε όλα τα ροζ,

900
00:42:26,170 --> 00:42:28,330
και το μπλε, και η
πράσινο τιμές, καθώς και.

901
00:42:28,330 --> 00:42:31,200
Έτσι, αυτό είναι για να πω μόνο ότι
συμπίεση είναι παντού.

902
00:42:31,200 --> 00:42:34,900
Είναι μια τεχνική που χρησιμοποιούμε συχνά
ή να λάβει ως δεδομένο αυτές τις μέρες.

903
00:42:34,900 --> 00:42:38,750
>> Αλλά πώς μπορείτε να συμπιέσετε κείμενο;

904
00:42:38,750 --> 00:42:40,450
Πώς θα πάτε για τη συμπίεση κειμένου;

905
00:42:40,450 --> 00:42:45,410
Λοιπόν, κάθε ένα από τους χαρακτήρες
Ascii είναι ένα byte, ή οκτώ κομμάτια.

906
00:42:45,410 --> 00:42:47,360
Και αυτό είναι το είδος των χαζή, σωστά;

907
00:42:47,360 --> 00:42:51,160
Επειδή ίσως τύπου Α
και Ε και Ι και Ο και U πολύ

908
00:42:51,160 --> 00:42:55,270
πιο συχνά από ό, τι, όπως W ή Q ή Ζ,
ανάλογα με τη γλώσσα στην οποία

909
00:42:55,270 --> 00:42:56,610
είστε γραπτώς βεβαίως.

910
00:42:56,610 --> 00:42:59,600
Και έτσι γιατί είμαστε χρησιμοποιώντας
οκτώ bits για κάθε γράμμα,

911
00:42:59,600 --> 00:43:02,040
συμπεριλαμβανομένων των λιγότερο
δημοφιλή γράμματα, έτσι δεν είναι;

912
00:43:02,040 --> 00:43:05,300
Γιατί να μην χρησιμοποιούν λιγότερα bits για
τα σούπερ δημοφιλής γράμματα,

913
00:43:05,300 --> 00:43:07,760
όπως Ε, τα πράγματα να μαντέψετε
για πρώτη φορά στην Τροχός της Τύχης,

914
00:43:07,760 --> 00:43:10,450
και να χρησιμοποιούν περισσότερα bits για
τα λιγότερο δημοφιλή γράμματα;

915
00:43:10,450 --> 00:43:10,950
Γιατί;

916
00:43:10,950 --> 00:43:13,130
Επειδή είμαστε ακριβώς πρόκειται να
χρησιμοποιούν λιγότερο συχνά.

917
00:43:13,130 --> 00:43:15,838
>> Λοιπόν, αποδεικνύεται ότι έχουν υπάρξει
ήταν προσπάθειες που έγιναν για να γίνει αυτό.

918
00:43:15,838 --> 00:43:18,630
Και αν θυμάστε από το βαθμό
το σχολείο ή το γυμνάσιο, τον κώδικα Μορς.

919
00:43:18,630 --> 00:43:20,400
Κώδικα Μορς έχει τελείες
και παύλες που μπορεί να είναι

920
00:43:20,400 --> 00:43:24,270
μεταδίδονται κατά μήκος ενός καλωδίου, όπως
ήχων ή σήματα κάποιου είδους.

921
00:43:24,270 --> 00:43:25,930
Αλλά κώδικα Μορς είναι ένα εξαιρετικά καθαρό.

922
00:43:25,930 --> 00:43:29,010
Είναι το είδος του ένα δυαδικό σύστημα στο
ότι έχετε κουκκίδες ή παύλες.

923
00:43:29,010 --> 00:43:30,977
Αλλά αν δείτε, για παράδειγμα, δύο τελείες.

924
00:43:30,977 --> 00:43:33,810
Ή αν νομίζετε ότι πίσω στο χειριστή
που πηγαίνει όπως μπιπ, μπιπ, μπιπ,

925
00:43:33,810 --> 00:43:36,760
μπιπ, χτυπώντας ένα μικρό σκανδάλη
ότι μεταδίδει ένα σήμα,

926
00:43:36,760 --> 00:43:40,360
αν εσείς, ο παραλήπτης, λαμβάνει δύο
τελείες, τι μήνυμα λάβατε;

927
00:43:40,360 --> 00:43:43,490
Εντελώς αυθαίρετη.

928
00:43:43,490 --> 00:43:44,450
>> Ι;

929
00:43:44,450 --> 00:43:45,060
Ι;

930
00:43:45,060 --> 00:43:47,500
Ή τι about-- ή εγώ;

931
00:43:47,500 --> 00:43:49,570
Ίσως ήταν μόνο δύο δεξιά της Ε;

932
00:43:49,570 --> 00:43:52,480
Έτσι υπάρχει αυτό το πρόβλημα
της decodability με Morse

933
00:43:52,480 --> 00:43:54,890
κώδικα, σύμφωνα με την οποία, εκτός αν η
άτομο που σας έστειλε το μήνυμα

934
00:43:54,890 --> 00:43:59,510
στην πραγματικότητα διακόπτει έτσι μπορείτε να ταξινομήσετε του
δουν ή να ακούσουν τα κενά μεταξύ των γραμμάτων,

935
00:43:59,510 --> 00:44:02,990
δεν είναι επαρκής μόνο για να
στείλετε ένα ρεύμα από μηδενικά και μονάδες,

936
00:44:02,990 --> 00:44:05,610
ή τελείες και παύλες,
επειδή υπάρχει ασάφεια.

937
00:44:05,610 --> 00:44:08,640
Ε είναι μια μοναδική τελεία, οπότε αν
δείτε δύο τελείες ή να ακούσετε δύο τελείες,

938
00:44:08,640 --> 00:44:11,254
ίσως είναι δυο Ε ή ίσως είναι ένα I.

939
00:44:11,254 --> 00:44:13,670
Έτσι, χρειαζόμαστε ένα σύστημα το οποίο είναι ένα
λίγο πιο έξυπνοι από αυτό.

940
00:44:13,670 --> 00:44:16,851
Έτσι, ένας άνθρωπος που ονομάζεται Huffman χρόνια
Πριν ήρθε με ακριβώς αυτό.

941
00:44:16,851 --> 00:44:18,600
Γι 'αυτό ακριβώς πρόκειται
να λάβει μια γρήγορη ματιά

942
00:44:18,600 --> 00:44:20,114
κατά πόσο τα δέντρα είναι συναφές με αυτό.

943
00:44:20,114 --> 00:44:22,530
Ας υποθέσουμε ότι αυτή είναι κάποια
ηλίθιο μήνυμα που θέλετε να στείλετε,

944
00:44:22,530 --> 00:44:26,342
που αποτελείται από μόλις Α, Β, Γ D's και της Ε,
αλλά υπάρχει πολλή απόλυσης εδώ.

945
00:44:26,342 --> 00:44:27,550
Δεν είναι γραφτό να είναι η αγγλική.

946
00:44:27,550 --> 00:44:28,341
Δεν είναι κρυπτογραφημένα.

947
00:44:28,341 --> 00:44:30,540
Είναι απλά ένα ηλίθιο μήνυμα
με πολλές επαναλήψεις.

948
00:44:30,540 --> 00:44:34,010
Έτσι, αν πραγματικά μετράνε όλα τα
Α, Β, Γ, D, και Ε, είναι εδώ είναι

949
00:44:34,010 --> 00:44:34,890
η συχνότητα.

950
00:44:34,890 --> 00:44:37,800
20% των γραμμάτων είναι
Α, το 45% από τα γράμματα

951
00:44:37,800 --> 00:44:39,660
είναι Ε, καθώς και τρεις άλλες συχνότητες.

952
00:44:39,660 --> 00:44:41,960
Εμείς υπολογίζονται μέχρι εκεί με το χέρι
και έκανε ακριβώς τα μαθηματικά.

953
00:44:41,960 --> 00:44:44,579
>> Έτσι αποδεικνύεται ότι
Huffman, πριν από λίγο καιρό,

954
00:44:44,579 --> 00:44:46,620
συνειδητοποίησε ότι, ξέρετε
τι, αν μπορώ να ξεκινήσω κτίριο

955
00:44:46,620 --> 00:44:51,172
Ένα δέντρο ή δάσος από δέντρα, αν θέλετε,
ως εξής, μπορώ να κάνω το εξής.

956
00:44:51,172 --> 00:44:53,880
Πάω να δώσει σε κάθε κόμβο
από τις επιστολές που με νοιάζει

957
00:44:53,880 --> 00:44:55,530
και θα πάω να αποθηκεύσετε
εντός αυτού του κόμβου

958
00:44:55,530 --> 00:44:58,610
οι συχνότητες ως πλωτό σημείο
τιμή, ή θα μπορούσατε να χρησιμοποιήσετε μια Ν, πάρα πολύ,

959
00:44:58,610 --> 00:45:00,210
αλλά θα χρησιμοποιούν μόνο ένα πλωτήρα εδώ.

960
00:45:00,210 --> 00:45:03,100
Και ο αλγόριθμος που
πρότεινε ότι θα είναι

961
00:45:03,100 --> 00:45:07,210
λαμβάνουν αυτό το δάσος του ενιαίου κόμβου
δέντρα, τόσο σούπερ δέντρα βραχείας περιόδου,

962
00:45:07,210 --> 00:45:11,920
και ξεκινάτε τη σύνδεση τους με
νέες ομάδες, νέους γονείς, αν θέλετε.

963
00:45:11,920 --> 00:45:16,150
Και το κάνετε αυτό επιλέγοντας το
δύο μικρότερα συχνότητες σε μια στιγμή.

964
00:45:16,150 --> 00:45:18,110
Έτσι πήρα 10% και 10%.

965
00:45:18,110 --> 00:45:19,090
Μπορώ να δημιουργήσω ένα νέο κόμβο.

966
00:45:19,090 --> 00:45:20,910
Και καλώ Ο νέος κόμβος 20%.

967
00:45:20,910 --> 00:45:22,750
>> Ποια δύο κόμβοι που συνδυάζουν το επόμενο βήμα;

968
00:45:22,750 --> 00:45:23,810
Είναι λίγο διφορούμενη.

969
00:45:23,810 --> 00:45:26,643
Έτσι, υπάρχει κάποια γωνιά περιπτώσεις να
να εξετάσει, αλλά για να κρατήσει τα πράγματα αρκετά,

970
00:45:26,643 --> 00:45:29,300
Πάω να επιλέξετε 20% -
Θα ήθελα τώρα να αγνοήσει τα παιδιά.

971
00:45:29,300 --> 00:45:33,640
Πάω να επιλέξετε 20% και
15% και σχεδιάστε δύο νέα άκρα.

972
00:45:33,640 --> 00:45:35,624
Και τώρα που δύο κόμβοι
μπορώ λογικά συνδυάζουν;

973
00:45:35,624 --> 00:45:38,540
Αγνοήστε όλα τα παιδιά, όλα τα
εγγόνια, μόλις δούμε τις ρίζες

974
00:45:38,540 --> 00:45:39,070
τώρα.

975
00:45:39,070 --> 00:45:42,220
Ποια δύο κόμβους μπορώ να συνδέσει μαζί;

976
00:45:42,220 --> 00:45:44,530
Σημείο δύο και 0.35.

977
00:45:44,530 --> 00:45:45,890
Επιτρέψτε μου λοιπόν να εξαγάγουμε δύο νέα άκρα.

978
00:45:45,890 --> 00:45:47,570
Και τότε έχω μόνο μία αριστερά.

979
00:45:47,570 --> 00:45:48,650
Έτσι, εδώ είναι ένα δέντρο.

980
00:45:48,650 --> 00:45:51,160
Και έχει συντάχθηκε σκόπιμα
να εξετάσουμε το είδος της αρκετά,

981
00:45:51,160 --> 00:45:55,870
αλλά παρατηρήσετε ότι οι άκρες έχουν
επίσης επισημανθεί μηδέν και ένα.

982
00:45:55,870 --> 00:45:59,510
Έτσι, το σύνολο των αριστερών άκρων είναι μηδέν
αυθαίρετα, αλλά σταθερά.

983
00:45:59,510 --> 00:46:01,170
Όλα τα δεξιά άκρα είναι αυτά.

984
00:46:01,170 --> 00:46:05,070
>> Και έτσι αυτό που προτείνεται είναι Hoffman,
αν θέλετε να αντιπροσωπεύουν ένα Β,

985
00:46:05,070 --> 00:46:10,080
αντί να αντιπροσωπεύουν τον αριθμό 66 ως
ένα αρχείο ASCII το οποίο είναι οκτώ ολόκληρο bits,

986
00:46:10,080 --> 00:46:13,360
ξέρετε τι, ακριβώς κατάστημα
το πρότυπο μηδέν, μηδέν, μηδέν,

987
00:46:13,360 --> 00:46:17,030
μηδέν, επειδή αυτό είναι το μονοπάτι
από το δέντρο μου, κ δέντρο Huffman του,

988
00:46:17,030 --> 00:46:18,600
στο φύλλο από τη ρίζα.

989
00:46:18,600 --> 00:46:20,970
Αν θέλετε να αποθηκεύσετε το
Ε, αντιθέτως, δεν

990
00:46:20,970 --> 00:46:26,290
στείλει οκτώ bits που αποτελούν Ε
Αντ 'αυτού, να στείλετε ποιο μοτίβο των bits;

991
00:46:26,290 --> 00:46:26,890
Ένα.

992
00:46:26,890 --> 00:46:30,410
Και τι είναι καλό για αυτό είναι
ότι το E είναι η πιο δημοφιλής επιστολή,

993
00:46:30,410 --> 00:46:32,340
και προσπαθείτε να χρησιμοποιήσετε το
συντομότερη κώδικα για αυτό.

994
00:46:32,340 --> 00:46:34,090
Η επόμενη πιο δημοφιλή
επιστολή μοιάζει να

995
00:46:34,090 --> 00:46:37,380
Ήταν A. Και έτσι πόσα bits
έκανε να προτείνει τη χρήση γι 'αυτό;

996
00:46:37,380 --> 00:46:38,270
Μηδέν, ένα.

997
00:46:38,270 --> 00:46:41,060
>> Και επειδή είναι υλοποιούνται
όπως αυτό το δέντρο, για τώρα

998
00:46:41,060 --> 00:46:43,350
επιτρέψτε μου να ορίζουν υπάρχει
καμία αμφισημία ως Μορς στο

999
00:46:43,350 --> 00:46:46,090
κώδικα, επειδή όλα τα
γράμματα που σας ενδιαφέρουν

1000
00:46:46,090 --> 00:46:48,780
βρίσκονται στο τέλος αυτών των άκρων.

1001
00:46:48,780 --> 00:46:50,580
Έτσι, αυτό είναι μόνο ένα
εφαρμογή ενός δέντρου.

1002
00:46:50,580 --> 00:46:52,538
Αυτό is-- και εγώ θα το κύμα
το χέρι μου σε αυτό το πώς θα

1003
00:46:52,538 --> 00:46:55,570
μπορεί να εφαρμόσει αυτό ως μια δομή C.

1004
00:46:55,570 --> 00:46:58,260
Πρέπει απλώς να συνδυάσουμε
ένα σύμβολο, όπως μια χαρα,

1005
00:46:58,260 --> 00:46:59,910
και η συχνότητα σε αριστερά και δεξιά.

1006
00:46:59,910 --> 00:47:02,510
Αλλά ας ρίξουμε μια ματιά σε δύο
τελικό παραδείγματα που θα

1007
00:47:02,510 --> 00:47:06,070
να πάρει αρκετά εξοικειωμένοι με το μετά
κουίζ μηδέν στο πρόβλημα που πέντε.

1008
00:47:06,070 --> 00:47:09,210
>> Έτσι, υπάρχει η δομή δεδομένων
γνωστό ως ένα πίνακα κατακερματισμού.

1009
00:47:09,210 --> 00:47:12,247
Και ένας πίνακας κατακερματισμού είναι το είδος του
ψυχθούν σε ότι έχει κουβάδες.

1010
00:47:12,247 --> 00:47:14,830
Και ας υποθέσουμε ότι υπάρχει τέσσερις κάδους
εδώ, μόλις τέσσερα κενά.

1011
00:47:14,830 --> 00:47:20,830
Εδώ είναι μια τράπουλα, και εδώ
κλαμπ, φτυάρι, κλαμπ, διαμάντια, club,

1012
00:47:20,830 --> 00:47:25,960
διαμάντια, κλαμπ, διαμάντια,
clubs-- έτσι αυτό είναι το τυχαίο.

1013
00:47:25,960 --> 00:47:30,330
Καρδιές, hearts-- έτσι είμαι
bucketizing όλες τις εισόδους εδώ.

1014
00:47:30,330 --> 00:47:32,430
Και ένα πίνακα κατακερματισμού ανάγκες
να εξετάσουμε τη συμβολή σας,

1015
00:47:32,430 --> 00:47:34,850
και στη συνέχεια το βάζουμε σε μια ορισμένη
διενεργούνται με βάση αυτό που βλέπετε.

1016
00:47:34,850 --> 00:47:35,600
Είναι ένας αλγόριθμος.

1017
00:47:35,600 --> 00:47:37,980
Και ήμουν με ένα σούπερ
απλή οπτική αλγόριθμο.

1018
00:47:37,980 --> 00:47:40,030
Το πιο δύσκολο μέρος της οποίας ήταν
θυμόμαστε ποιες είναι οι εικόνες ήταν.

1019
00:47:40,030 --> 00:47:41,590
Και έπειτα υπάρχει τέσσερα συνολικά πράγματα.

1020
00:47:41,590 --> 00:47:45,440
>> Τώρα οι στοίβες μεγάλωναν, η οποία
Είναι μια σκόπιμη σχεδιασμό πράγμα εδώ.

1021
00:47:45,440 --> 00:47:46,540
Αλλά τι άλλο θα μπορούσε να κάνω;

1022
00:47:46,540 --> 00:47:49,080
Έτσι, στην πραγματικότητα, εδώ έχουμε ένα
μάτσο παλιά σχολικά βιβλία εξετάσεις.

1023
00:47:49,080 --> 00:47:51,240
Ας υποθέσουμε ότι ένα μάτσο
ονόματα μαθητές είναι εδώ.

1024
00:47:51,240 --> 00:47:52,570
Εδώ είναι ένα μεγαλύτερο πίνακα κατακερματισμού.

1025
00:47:52,570 --> 00:47:54,867
Αντί των τεσσάρων κάδων,
Έχω, ας πούμε 26.

1026
00:47:54,867 --> 00:47:57,950
Και δεν ήθελε να πάει να δανειστεί 26
τα πράγματα από το εξωτερικό [? Annenberg?], Έτσι

1027
00:47:57,950 --> 00:48:00,289
Εδώ είναι πέντε, που αντιπροσωπεύουν
Α έως Ζ Κι αν

1028
00:48:00,289 --> 00:48:03,580
δείτε ένα μαθητή του οποίου το όνομα αρχίζει με Α,
Πάω να του κουίζ ή να την βάλει εκεί.

1029
00:48:03,580 --> 00:48:08,850
Αν κάποιος ξεκινά με C, πάνω από εκεί,
A-- στην πραγματικότητα, δεν ήθελε να το κάνει αυτό.

1030
00:48:08,850 --> 00:48:10,060
Β πηγαίνει εδώ.

1031
00:48:10,060 --> 00:48:13,390
Έτσι έχω Α και Β και C. Και
Τώρα εδώ είναι ένα άλλο μαθητή.

1032
00:48:13,390 --> 00:48:16,212
Αλλά αν αυτό πίνακα κατακερματισμού είναι
υλοποιείται με μια σειρά,

1033
00:48:16,212 --> 00:48:17,920
Είμαι το είδος του βιδωθεί
σε αυτό το σημείο, έτσι δεν είναι;

1034
00:48:17,920 --> 00:48:19,510
Ι το είδος πρέπει να θέσει αυτό το κάπου.

1035
00:48:19,510 --> 00:48:24,380
>> Έτσι, ένας τρόπος που μπορώ να λύσει αυτό, όλα
δεξιά, Α είναι απασχολημένος, Β είναι απασχολημένος, C είναι απασχολημένος.

1036
00:48:24,380 --> 00:48:28,880
Πάω να τον βάλουν στο Δ Έτσι, στο
Κατ 'αρχάς, έχω τυχαία άμεση πρόσβαση

1037
00:48:28,880 --> 00:48:31,064
σε καθένα από τους κάδους για τους μαθητές.

1038
00:48:31,064 --> 00:48:33,230
Αλλά τώρα αυτό είναι το είδος των αποκεντρωμένων
σε κάτι γραμμικό,

1039
00:48:33,230 --> 00:48:36,750
γιατί αν θέλετε να ψάξετε για κάποιον
του οποίου το όνομα αρχίζει με Α, μπορώ να ελέγξω εδώ.

1040
00:48:36,750 --> 00:48:38,854
Αλλά αν αυτό δεν είναι η A
φοιτητής Ψάχνω για,

1041
00:48:38,854 --> 00:48:41,520
Ι το είδος πρέπει να αρχίσετε να ελέγχετε
οι κάδοι, γιατί ό, τι έκανα

1042
00:48:41,520 --> 00:48:44,530
Ήταν ένα είδος γραμμικά
εξετάσουν τη δομή των δεδομένων.

1043
00:48:44,530 --> 00:48:47,710
Ένας ηλίθιος τρόπος για να πούμε απλά κοιτάξτε
για το πρώτο διαθέσιμο άνοιγμα,

1044
00:48:47,710 --> 00:48:51,850
και να θέσει ως σχέδιο Β, να το πω έτσι,
ή το σχέδιο Α στην περίπτωση αυτή, η αξία

1045
00:48:51,850 --> 00:48:53,340
στη θέση αυτή αντ 'αυτού.

1046
00:48:53,340 --> 00:48:56,470
Αυτό είναι ακριβώς έτσι ώστε αν έχετε
πήρε 26 θέσεις και δεν φοιτητών

1047
00:48:56,470 --> 00:49:00,600
με την επωνυμία Q ή Ζ, ή κάτι παρόμοιο
ότι, τουλάχιστον είστε με τη χρήση του χώρου.

1048
00:49:00,600 --> 00:49:03,140
>> Αλλά έχουμε ήδη δει περισσότερα
έξυπνες λύσεις εδώ, σωστά;

1049
00:49:03,140 --> 00:49:04,870
Τι θα κάνετε αντί
εάν έχετε μια σύγκρουση;

1050
00:49:04,870 --> 00:49:06,670
Αν δύο άνθρωποι έχουν
το όνομα Α, τι θα

1051
00:49:06,670 --> 00:49:09,160
έχουν μια πιο έξυπνη και άνω
διαισθητική λύση όχι μόνο

1052
00:49:09,160 --> 00:49:12,840
Μια θέση όπου D είναι υποτίθεται ότι είναι;

1053
00:49:12,840 --> 00:49:14,810
Γιατί δεν μπορώ ακριβώς να πάτε
εκτός [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
όπως malloc, έναν άλλο κόμβο, το έθεσε
εδώ, και στη συνέχεια βάλτε ότι ένας μαθητής εδώ.

1055
00:49:19,960 --> 00:49:22,120
Έτσι ώστε να έχουν ουσιαστικά
κάποιο είδος μιας συστοιχίας,

1056
00:49:22,120 --> 00:49:25,590
ή ίσως και πιο κομψά, όπως είμαστε
Αρχίζουμε να βλέπουμε μια συνδεδεμένη λίστα.

1057
00:49:25,590 --> 00:49:29,520
>> Και έτσι ένα πίνακα κατακερματισμού είναι μια δομή
ότι θα μπορούσε να μοιάζει ακριβώς όπως αυτό,

1058
00:49:29,520 --> 00:49:33,900
αλλά πιο έξυπνα, σας κάτι που ονομάζεται
Ξεχωριστές αλυσίδες, όπου ένα πίνακα κατακερματισμού

1059
00:49:33,900 --> 00:49:38,340
απλούστατα είναι ένας πίνακας, κάθε ένα από
του οποίου τα στοιχεία δεν είναι ένας αριθμός,

1060
00:49:38,340 --> 00:49:40,470
είναι η ίδια συνδεδεμένη λίστα.

1061
00:49:40,470 --> 00:49:45,080
Έτσι ώστε να μπορείτε να πάρετε σούπερ γρήγορη πρόσβαση
αποφασίζουν πού να hash αξία σας.

1062
00:49:45,080 --> 00:49:48,059
Μοιάζει πολύ με τον κάρτες παράδειγμα,
Έκανα εξαιρετικά γρήγορες αποφάσεις.

1063
00:49:48,059 --> 00:49:49,600
Καρδιές πηγαίνει εδώ, τα διαμάντια πηγαίνει εδώ.

1064
00:49:49,600 --> 00:49:52,180
Ίδιο εδώ, Α πηγαίνει εδώ,
Δ πηγαίνει εδώ, Β πηγαίνει εδώ.

1065
00:49:52,180 --> 00:49:55,740
Έτσι σούπερ γρήγορη ματιά-ups, και εάν
τυχαίνει να τρέχει σε μια υπόθεση

1066
00:49:55,740 --> 00:49:59,429
όπου έχεις συγκρούσεις, δύο
οι άνθρωποι με το ίδιο όνομα, καλά τότε

1067
00:49:59,429 --> 00:50:00,970
μπορείτε απλά να αρχίσετε τα συνδέουν μεταξύ τους.

1068
00:50:00,970 --> 00:50:03,900
Και ίσως να τους κρατήσει ταξινομημένο
αλφαβητικά, ίσως όχι.

1069
00:50:03,900 --> 00:50:05,900
Αλλά τουλάχιστον τώρα έχουμε τον δυναμισμό.

1070
00:50:05,900 --> 00:50:10,250
Έτσι, από τη μία πλευρά έχουμε σούπερ γρήγορο
χρονική σταθερά, και το είδος του γραμμικού χρόνου

1071
00:50:10,250 --> 00:50:14,110
που εμπλέκονται, αν αυτές συνδέονται με τις λίστες
να αρχίσει να πάρει λίγο καιρό.

1072
00:50:14,110 --> 00:50:16,880
>> Έτσι, αυτό το είδος της μια ανόητη,
geeky αστείο χρόνια.

1073
00:50:16,880 --> 00:50:19,590
Στο CS50 hack-a-thon,
όταν οι μαθητές κάνουν check-in,

1074
00:50:19,590 --> 00:50:22,040
μερικά TF ή CA κάθε χρόνο
νομίζει ότι είναι αστείο να ανεχτούμε

1075
00:50:22,040 --> 00:50:27,772
ένα σημάδι σαν αυτό, όπου μόνο
σημαίνει ότι εάν το όνομά σας ξεκινά με ένα Α,

1076
00:50:27,772 --> 00:50:28,870
πάει με αυτόν τον τρόπο.

1077
00:50:28,870 --> 00:50:31,110
Αν το όνομα σας ξεκινά
με Β, πηγαίνετε this-- ΟΚ,

1078
00:50:31,110 --> 00:50:33,290
Είναι αστείο ίσως αργότερα στο εξάμηνο.

1079
00:50:33,290 --> 00:50:36,420
Αλλά υπάρχει και μια άλλη
τρόπος για να γίνει αυτό, πάρα πολύ.

1080
00:50:36,420 --> 00:50:37,410
Γύρνα πίσω σε αυτό.

1081
00:50:37,410 --> 00:50:38,600
>> Έτσι υπάρχει αυτή η δομή.

1082
00:50:38,600 --> 00:50:40,420
Και αυτή είναι η τελευταία μας
δομή για σήμερα,

1083
00:50:40,420 --> 00:50:42,400
το οποίο είναι κάτι που ονομάζεται trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-Ι-Ε, η οποία για κάποιο λόγο είναι μικρή
για την ανάκτηση, αλλά αυτό λέγεται trie.

1085
00:50:47,140 --> 00:50:51,389
Έτσι, ένα trie είναι μια άλλη ενδιαφέρουσα
αμάλγαμα από πολλές από αυτές τις ιδέες.

1086
00:50:51,389 --> 00:50:52,930
Είναι ένα δέντρο, που έχουμε δει στο παρελθόν.

1087
00:50:52,930 --> 00:50:54,180
Δεν είναι ένα δυαδικό δένδρο αναζήτησης.

1088
00:50:54,180 --> 00:50:58,410
Είναι ένα δέντρο με οποιοδήποτε αριθμό των παιδιών,
αλλά κάθε ένα από τα παιδιά σε ένα trie

1089
00:50:58,410 --> 00:51:00,090
είναι ένας πίνακας.

1090
00:51:00,090 --> 00:51:04,790
Μια σειρά μεγέθους, δηλαδή, 26 ή ίσως και 27
αν θέλετε να υποστηρίξετε ενωτικό ονόματα

1091
00:51:04,790 --> 00:51:06,790
ή σε αποστρόφους τα ονόματα των ανθρώπων.

1092
00:51:06,790 --> 00:51:08,280
>> Και έτσι αυτή είναι μια δομή δεδομένων.

1093
00:51:08,280 --> 00:51:10,290
Και αν δει κανείς από την κορυφή
προς τα κάτω, σαν να

1094
00:51:10,290 --> 00:51:13,710
κοιτάξουμε την κορυφή κόμβο εκεί, Μ, είναι
που δείχνουν προς το αριστερότερο πράγμα εκεί,

1095
00:51:13,710 --> 00:51:17,665
η οποία στη συνέχεια τα Α, Χ, W, E, L, L. Αυτό είναι
απλά μια δομή δεδομένων που αυθαίρετα

1096
00:51:17,665 --> 00:51:19,120
αποθηκεύει τα ονόματα των ανθρώπων.

1097
00:51:19,120 --> 00:51:25,720
Και Maxwell αποθηκεύονται μόνο μετά από
ένα μονοπάτι της συστοιχίας σε συστοιχίας σε σειρά.

1098
00:51:25,720 --> 00:51:30,050
Αλλά τι είναι καταπληκτικό για μια trie είναι
ότι, λαμβάνοντας υπόψη ότι μια συνδεδεμένη λίστα και ακόμη

1099
00:51:30,050 --> 00:51:34,520
μια σειρά, το καλύτερο που έχουμε πάρει ποτέ είναι
γραμμικό χρόνο ή λογαριθμική χρόνο ψάχνοντας

1100
00:51:34,520 --> 00:51:35,600
κάποιος επάνω.

1101
00:51:35,600 --> 00:51:40,530
Σε αυτή τη δομή δεδομένων μιας trie, εάν
δομή δεδομένων μου έχει ένα όνομα σε αυτό

1102
00:51:40,530 --> 00:51:43,720
και ψάχνω για Maxwell, είμαι
Θα τον βρείτε αρκετά γρήγορα.

1103
00:51:43,720 --> 00:51:47,910
Απλά κοιτάξτε για το Μ-Α-Χ-W-Ε-Ε-Ε. Αν
αυτό δομή δεδομένων, αντιθέτως,

1104
00:51:47,910 --> 00:51:51,830
αν το Ν είναι ένα εκατομμύριο, αν υπάρχει
εκατομμύρια ονόματα σε αυτή τη δομή δεδομένων,

1105
00:51:51,830 --> 00:51:57,100
Maxwell είναι ακόμα πρόκειται να είναι
ανιχνεύσιμο μετά από μόλις Μ-Α-Χ-W-Ε-Ε-Ε

1106
00:51:57,100 --> 00:51:58,090
βήματα.

1107
00:51:58,090 --> 00:52:01,276
Και τα βήματα David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Με άλλα λόγια, με την οικοδόμηση
μια δομή δεδομένων που είναι

1109
00:52:03,400 --> 00:52:07,240
πήρε όλες αυτές τις συστοιχίες, τα οποία όλα
αυτοσυντηρηθούν τυχαίας προσπέλασης,

1110
00:52:07,240 --> 00:52:11,090
Μπορώ να αρχίσετε να ψάχνετε μέχρι ανθρώπων
όνομα χρησιμοποιώντας ένα χρονικό διάστημα που είναι

1111
00:52:11,090 --> 00:52:14,340
ανάλογη με τον αριθμό δεν
πράγματα στη δομή δεδομένων,

1112
00:52:14,340 --> 00:52:16,330
ένα εκατομμύριο, όπως τα υπάρχοντα ονόματα.

1113
00:52:16,330 --> 00:52:20,135
Ο χρόνος που χρειάζεται για να μου βρείτε
M-A-X-W-E-L-L σε αυτή τη δομή δεδομένων είναι

1114
00:52:20,135 --> 00:52:22,260
ανάλογη όχι προς τα
μέγεθος της δομής των δεδομένων,

1115
00:52:22,260 --> 00:52:25,930
αλλά με το μήκος του ονόματος.

1116
00:52:25,930 --> 00:52:28,440
Και πραγματικά η
ονόματα ψάχνουμε μέχρι

1117
00:52:28,440 --> 00:52:29,970
δεν πρόκειται ποτέ να είναι τρελό καιρό.

1118
00:52:29,970 --> 00:52:32,600
Ίσως κάποιος να έχει ένα χαρακτήρα 10
αναφέρουμε, 20 το όνομα του χαρακτήρα.

1119
00:52:32,600 --> 00:52:33,900
Είναι σίγουρα πεπερασμένα, σωστά;

1120
00:52:33,900 --> 00:52:37,110
Υπάρχει ένας άνθρωπος στη Γη που
έχει τη μεγαλύτερη δυνατή όνομα,

1121
00:52:37,110 --> 00:52:39,920
αλλά αυτό το όνομα είναι μια σταθερά
Μήκος αξία, έτσι δεν είναι;

1122
00:52:39,920 --> 00:52:41,980
Αυτό δεν μεταβάλλεται με οποιαδήποτε έννοια.

1123
00:52:41,980 --> 00:52:45,090
Έτσι, με αυτόν τον τρόπο, έχουμε
επιτυγχάνεται μια δομή δεδομένων

1124
00:52:45,090 --> 00:52:47,800
που είναι σταθερά χρόνου look-up.

1125
00:52:47,800 --> 00:52:50,670
Θα έχει λάβει ορισμένα μέτρα
ανάλογα με το μήκος της εισόδου,

1126
00:52:50,670 --> 00:52:54,250
αλλά όχι ο αριθμός του ονόματος
στη δομή δεδομένων.

1127
00:52:54,250 --> 00:52:58,700
Έτσι, αν έχουμε διπλασιάσει τον αριθμό των ονομάτων
το επόμενο έτος από ένα δισεκατομμύριο σε δύο δισεκατομμύρια,

1128
00:52:58,700 --> 00:53:03,720
διαπίστωση Maxwell πρόκειται να πάρει
ακριβώς τον ίδιο αριθμό από επτά βήματα

1129
00:53:03,720 --> 00:53:04,650
να τον βρει.

1130
00:53:04,650 --> 00:53:08,810
Και έτσι φαίνεται να έχουμε επιτύχει
άγιο δισκοπότηρο μας χρόνου λειτουργίας.

1131
00:53:08,810 --> 00:53:10,860
>> Έτσι, μερικές γρήγορες ανακοινώσεις.

1132
00:53:10,860 --> 00:53:11,850
Quiz μηδέν έρχεται επάνω.

1133
00:53:11,850 --> 00:53:14,600
Περισσότερα για αυτό στην ιστοσελίδα του μαθήματος
κατά τις επόμενες δύο ημέρες.

1134
00:53:14,600 --> 00:53:17,120
Δευτέρα lecture-- είναι αργία
εδώ στο Harvard τη Δευτέρα.

1135
00:53:17,120 --> 00:53:18,850
Δεν είναι στο New Haven,
έτσι παίρνουμε την κατηγορία

1136
00:53:18,850 --> 00:53:20,310
προς Νιου Χέιβεν για διάλεξη την Δευτέρα.

1137
00:53:20,310 --> 00:53:22,550
Τα πάντα θα κινηματογραφηθεί
και μεταδοθεί ζωντανά ως συνήθως,

1138
00:53:22,550 --> 00:53:24,900
αλλά ας τελειώσει σήμερα
με ένα δεύτερο συνδετήρα 30

1139
00:53:24,900 --> 00:53:26,910
που ονομάζεται «βαθιές σκέψεις"
από Daven Farnham, η οποία

1140
00:53:26,910 --> 00:53:30,850
εμπνεύστηκε το περασμένο έτος μέχρι το Σάββατο
«Βαθιές σκέψεις" Night Live της

1141
00:53:30,850 --> 00:53:35,700
από τον Jack Handy, η οποία
θα πρέπει να κάνει τώρα νόημα.

1142
00:53:35,700 --> 00:53:38,810
>> ΦΙΛΜ: Και τώρα, "Deep
Σκέψεις "από Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Πίνακας κατακερματισμού.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ΟΜΙΛΗΤΗΣ 1: Εντάξει, αυτό είναι για τώρα.

1147
00:53:47,660 --> 00:53:48,805
Θα σας δούμε την επόμενη εβδομάδα.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Για να το δείτε σε δράση.

1150
00:53:56,680 --> 00:53:58,304
Έτσι, ας ρίξουμε μια ματιά σε αυτό τώρα.

1151
00:53:58,304 --> 00:53:59,890
Έτσι, εδώ, έχουμε μια σειρά αδιαχώριστα.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, μπορείτε να προχωρήσετε και επανεκκίνηση
αυτό για μόνο ένα δευτερόλεπτο, παρακαλώ.

1153
00:54:04,860 --> 00:54:08,562
Εντάξει, κάμερες τροχαίο, έτσι
δράσης, όταν είστε έτοιμοι, Νταγκ, εντάξει;

1154
00:54:08,562 --> 00:54:11,020
DOUG: Εντάξει, έτσι αυτό που
έχουμε εδώ είναι μια σειρά αδιαχώριστα.

1155
00:54:11,020 --> 00:54:13,960
Και έχω χρωματιστά όλα τα στοιχεία
κόκκινο για να δείξει ότι είναι, στην πραγματικότητα,

1156
00:54:13,960 --> 00:54:14,460
αδιαχώριστα.

1157
00:54:14,460 --> 00:54:17,960
Έτσι, υπενθυμίζουν ότι το πρώτο πράγμα που κάνουμε
είναι να ξεκαθαρίσουμε το αριστερό μισό του πίνακα.

1158
00:54:17,960 --> 00:54:20,630
Τότε θα λύσουμε το δικαίωμα
μισο της συστοιχίας.

1159
00:54:20,630 --> 00:54:22,830
Και ya-δα, ya-δα, ya-da,
Τους συγχωνεύονται.

1160
00:54:22,830 --> 00:54:24,520
Και έχουμε μια εντελώς ταξινομημένο πίνακα.

1161
00:54:24,520 --> 00:54:25,360
Έτσι, αυτό είναι το πώς λειτουργεί ταξινόμηση με συγχώνευση.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Πω πω, whoa, whoa,
κομμένα, κομμένα, κομμένα, κομμένα.

1163
00:54:27,109 --> 00:54:30,130
Doug, μπορείτε όχι μόνο να ya-δα, ya-da,
Ya-ντα, το δρόμο σας μέσα από τη συγχώνευση του είδους.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: έκανα ακριβώς.

1165
00:54:31,970 --> 00:54:32,832
Είναι εντάξει.

1166
00:54:32,832 --> 00:54:33,540
Είμαστε καλοί να πάτε.

1167
00:54:33,540 --> 00:54:34,760
Ας κρατήσει το τροχαίο.

1168
00:54:34,760 --> 00:54:35,380
Έτσι κι αλλιώς,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Θα πρέπει να εξηγήσουν
πληρέστερη από αυτό.

1170
00:54:37,800 --> 00:54:39,999
Αυτό απλά δεν είναι αρκετό.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, δεν το κάνουμε
Πρέπει να πάμε πίσω σε ένα.

1172
00:54:41,790 --> 00:54:42,350
Είναι εντάξει.

1173
00:54:42,350 --> 00:54:45,690
Έτσι κι αλλιώς, αν συνεχίσουμε με merge--
Ian, είμαστε στη μέση των γυρισμάτων.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ξέρω.

1175
00:54:46,612 --> 00:54:49,320
Και δεν μπορούμε απλώς να ya-δα, ya-da,
Ya-da, μέσα από την όλη διαδικασία.

1176
00:54:49,320 --> 00:54:52,200
Θα πρέπει να εξηγήσει πώς η
δύο πλευρές να συγχωνεύονται.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Αλλά έχουμε ήδη
εξήγησε πώς τα δύο sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Έχετε μόλις φαίνεται
τους μια σειρά συγχώνευσης.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ξέρουν τη διαδικασία.

1180
00:54:56,486 --> 00:54:57,172
Είναι μια χαρά.

1181
00:54:57,172 --> 00:54:58,380
Έχουμε περάσει πάνω από δέκα φορές.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Απλά παραληφθεί σωστά πάνω του.

1183
00:55:00,330 --> 00:55:03,360
Εμείς πάμε πίσω σε ένα,
δεν μπορείς Ya-δα, ya-δα πάνω του.

1184
00:55:03,360 --> 00:55:05,480
Εντάξει, πίσω σε ένα.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Πρέπει να πάω πίσω
μέσω όλων των διαφανειών;

1186
00:55:07,833 --> 00:55:08,332
Θεέ μου.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Είναι σαν έκτη φορά, Ian.

1189
00:55:13,004 --> 00:55:13,940
Είναι εντάξει.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Εντάξει.

1191
00:55:15,200 --> 00:55:16,590
Είστε έτοιμοι?

1192
00:55:16,590 --> 00:55:17,400
Εξαιρετική.

1193
00:55:17,400 --> 00:55:18,950
Δράση.