1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Έτσι σε CS50, καλύψαμε
πολλές διαφορετικές δομές δεδομένων,

3
00:00:08,300 --> 00:00:09,180
έτσι δεν είναι;

4
00:00:09,180 --> 00:00:11,420
Έχουμε δει συστοιχίες, και συνδέεται
λίστες και πίνακες κατακερματισμού,

5
00:00:11,420 --> 00:00:15,210
και προσπαθεί, στοίβες και ουρές.

6
00:00:15,210 --> 00:00:17,579
Επίσης, θα μάθετε λίγο
σχετικά με τα δέντρα και τους σωρούς,

7
00:00:17,579 --> 00:00:20,120
αλλά πραγματικά όλα αυτά μόλις τελειώσει
να είναι παραλλαγές σε ένα θέμα.

8
00:00:20,120 --> 00:00:22,840
Πραγματικά υπάρχουν αυτά
το είδος των τεσσάρων βασικών ιδεών

9
00:00:22,840 --> 00:00:25,190
ότι ό, τι άλλο μπορεί να συνοψίζεται σε.

10
00:00:25,190 --> 00:00:28,150
Πίνακες, συνδεδεμένες λίστες,
hash πίνακες, και προσπαθεί.

11
00:00:28,150 --> 00:00:30,720
Και όπως είπα, υπάρχει
είναι παραλλαγές τους,

12
00:00:30,720 --> 00:00:32,720
αλλά αυτό είναι αρκετά
πολύ θα συνοψίσω

13
00:00:32,720 --> 00:00:38,140
ό, τι θα πάμε να μιλήσουμε
περίπου σε αυτή την κατηγορία από την άποψη του C.

14
00:00:38,140 --> 00:00:40,140
>> Αλλά πώς το κάνουμε όλα αυτά πράξη επάνω, δεξιά;

15
00:00:40,140 --> 00:00:44,265
Έχουμε μιλήσει για τα πλεονεκτήματα και τα μειονεκτήματα
καθενός ξεχωριστά σε βίντεο τους,

16
00:00:44,265 --> 00:00:46,390
αλλά υπάρχει πολλή αριθμούς
να πάρει ρίχνονται γύρω.

17
00:00:46,390 --> 00:00:48,723
Υπάρχουν πολλές γενικές
σκέψεις να πάρει ρίχνονται γύρω.

18
00:00:48,723 --> 00:00:51,950
Ας προσπαθήσουμε και να ενοποιήσει
το σε ένα μόνο μέρος.

19
00:00:51,950 --> 00:00:55,507
Ας σταθμίσει τα υπέρ έναντι
Τα μειονεκτήματα, και να εξετάσει

20
00:00:55,507 --> 00:00:57,340
η οποία δομή δεδομένων
θα μπορούσε να είναι η σωστή δεδομένων

21
00:00:57,340 --> 00:01:01,440
δομή για την περίπτωσή σας,
Ανεξάρτητα από το είδος των δεδομένων που θέλετε να αποθηκεύσετε.

22
00:01:01,440 --> 00:01:06,625
Δεν χρειάζεται απαραιτήτως πρέπει πάντα να
χρησιμοποιήστε το σούπερ γρήγορη εισαγωγή, διαγραφή,

23
00:01:06,625 --> 00:01:10,761
και αναζήτηση ενός trie αν πραγματικά
Δεν με νοιάζει για την εισαγωγή και τη διαγραφή

24
00:01:10,761 --> 00:01:11,260
πάρα πολύ.

25
00:01:11,260 --> 00:01:13,968
Αν το μόνο που χρειάζεται γρήγορα τυχαία
πρόσβασης, ίσως ένας πίνακας είναι καλύτερη.

26
00:01:13,968 --> 00:01:15,340
Ας απόσταξη αυτό.

27
00:01:15,340 --> 00:01:18,530
Ας μιλήσουμε για καθένα από τα τέσσερα
μείζονα είδη δομών δεδομένων

28
00:01:18,530 --> 00:01:21,720
ότι έχουμε μιλήσει, και
απλά δείτε όταν θα μπορούσαν να είναι καλό,

29
00:01:21,720 --> 00:01:23,340
και όταν μπορεί να μην είναι τόσο καλή.

30
00:01:23,340 --> 00:01:24,610
Ας ξεκινήσουμε με συστοιχίες.

31
00:01:24,610 --> 00:01:27,300
Έτσι εισαγωγής, αυτό είναι το είδος των κακών.

32
00:01:27,300 --> 00:01:31,350
>> Εισαγωγής στο τέλος μίας συστοιχίας είναι ΟΚ,
αν χτίζουμε μια σειρά, όπως πάμε.

33
00:01:31,350 --> 00:01:33,570
Αλλά αν πρέπει να τοποθετήσετε
στοιχεία στη μέση,

34
00:01:33,570 --> 00:01:35,550
ότι πίσω από την εισαγωγή
είδος, υπάρχουν πολλά

35
00:01:35,550 --> 00:01:37,510
της μετατόπισης για να χωρέσει ένα στοιχείο εκεί.

36
00:01:37,510 --> 00:01:41,170
Και έτσι, αν θα πάμε για να εισάγετε
οπουδήποτε αλλά το τέλος μιας συστοιχίας,

37
00:01:41,170 --> 00:01:43,590
ότι δεν είναι πιθανώς τόσο μεγάλη.

38
00:01:43,590 --> 00:01:46,710
>> Ομοίως, διαγραφή, εκτός και αν είμαστε
διαγραφή από το τέλος μιας συστοιχίας,

39
00:01:46,710 --> 00:01:49,810
Είναι πιθανόν επίσης δεν είναι τόσο μεγάλη, αν
δεν θέλουμε να αφήσετε κενά κενά,

40
00:01:49,810 --> 00:01:50,790
η οποία συνήθως δεν το κάνουμε.

41
00:01:50,790 --> 00:01:54,700
Θέλουμε να καταργήσετε ένα στοιχείο, και
τότε το είδος του καθιστούν άνετη και πάλι.

42
00:01:54,700 --> 00:01:57,670
Και έτσι από τη διαγραφή στοιχείων
ένας πίνακας, επίσης, δεν είναι τόσο μεγάλη.

43
00:01:57,670 --> 00:01:58,820
>> Αναζήτηση, όμως, είναι μεγάλη.

44
00:01:58,820 --> 00:02:00,920
Έχουμε τυχαίας προσπέλασης,
συνεχής αναζήτηση του χρόνου.

45
00:02:00,920 --> 00:02:03,800
Θα πω μόνο επτά, και πάμε
σε σειρά μετεγκατάσταση επτά.

46
00:02:03,800 --> 00:02:05,907
Λέμε 20, με πηγαίνετε στο
μετεγκατάσταση πίνακα 20.

47
00:02:05,907 --> 00:02:07,240
Δεν έχουμε να επαναλάβει ολόκληρη.

48
00:02:07,240 --> 00:02:08,630
Αυτό είναι πολύ καλό.

49
00:02:08,630 --> 00:02:11,020
>> Οι πίνακες είναι επίσης σχετικά εύκολο να ταξινομήσετε.

50
00:02:11,020 --> 00:02:14,040
Κάθε φορά που μιλήσαμε για μια διαλογή
αλγόριθμο, όπως είδος επιλογής,

51
00:02:14,040 --> 00:02:18,820
ταξινόμηση με εισαγωγή, bubble sort, συγχώνευση
είδος, έχουμε χρησιμοποιήσει πάντα συστοιχίες να το κάνουμε,

52
00:02:18,820 --> 00:02:21,860
επειδή συστοιχίες είναι αρκετά εύκολο να
είδος, σε σχέση με τα δεδομένα των δομών

53
00:02:21,860 --> 00:02:22,970
έχουμε δει μέχρι τώρα.

54
00:02:22,970 --> 00:02:24,320
>> Είναι επίσης σχετικά μικρός.

55
00:02:24,320 --> 00:02:25,695
Δεν υπάρχει μια πολύ επιπλέον χώρο.

56
00:02:25,695 --> 00:02:29,210
Μπορείτε απλά να αναιρέσει ακριβώς όσο
όπως θα πρέπει να κρατήσει τα δεδομένα σας,

57
00:02:29,210 --> 00:02:30,320
και αυτό είναι λίγο πολύ αυτό.

58
00:02:30,320 --> 00:02:33,180
Έτσι είναι αρκετά μικρό
και αποτελεσματικό με αυτόν τον τρόπο.

59
00:02:33,180 --> 00:02:36,000
Αλλά ένα άλλο μειονέκτημα, όμως,
είναι ότι καθορίζονται σε μέγεθος.

60
00:02:36,000 --> 00:02:38,630
Έχουμε να δηλώσει πώς ακριβώς
μεγάλο θέλουμε σειρά μας να είναι,

61
00:02:38,630 --> 00:02:39,940
και παίρνουμε μόνο έναν πυροβολισμό σε αυτό.

62
00:02:39,940 --> 00:02:41,280
Εμείς δεν μπορεί να αναπτυχθεί και να συρρικνωθεί.

63
00:02:41,280 --> 00:02:44,582
>> Αν πρέπει να αυξηθεί ή να συρρικνωθεί, εμείς
πρέπει να δηλώσει μια εντελώς νέα σειρά,

64
00:02:44,582 --> 00:02:47,750
αντιγράψτε όλα τα στοιχεία του
πρώτη συστοιχία εντός του δεύτερου πίνακα.

65
00:02:47,750 --> 00:02:51,410
Και αν υπολόγισε σωστά ότι
φορά, θα πρέπει να το κάνουμε ξανά.

66
00:02:51,410 --> 00:02:52,760
Δεν είναι τόσο μεγάλη.

67
00:02:52,760 --> 00:02:58,750
Έτσι συστοιχίες δεν μας δίνουν την ευελιξία
να έχουν μεταβλητούς αριθμούς των στοιχείων.

68
00:02:58,750 --> 00:03:01,320
>> Με μια συνδεδεμένη λίστα,
εισαγωγής είναι αρκετά εύκολο.

69
00:03:01,320 --> 00:03:03,290
Εμείς απλά καρφί στο μπροστινό.

70
00:03:03,290 --> 00:03:04,892
Η διαγραφή είναι επίσης αρκετά εύκολο.

71
00:03:04,892 --> 00:03:06,100
Πρέπει να βρούμε τα στοιχεία.

72
00:03:06,100 --> 00:03:07,270
Αυτό συνεπάγεται κάποια έρευνα.

73
00:03:07,270 --> 00:03:10,270
>> Αλλά μόλις βρήκατε το στοιχείο
ψάχνετε για, το μόνο που πρέπει να κάνετε

74
00:03:10,270 --> 00:03:12,830
είναι να αλλάξετε ένα δείκτη,
ενδεχομένως δύο, αν έχετε

75
00:03:12,830 --> 00:03:15,151
ένα συνδεδεμένο list-- ένα διπλά
συνδεδεμένη λίστα, rather--

76
00:03:15,151 --> 00:03:16,650
και, στη συνέχεια, μπορείτε να ελευθερώσετε λίγο τον κόμβο.

77
00:03:16,650 --> 00:03:18,399
Δεν χρειάζεται να μετατοπίσει
τα πάντα γύρω.

78
00:03:18,399 --> 00:03:22,090
Απλά αλλάξετε δίποντα,
έτσι ώστε να είναι αρκετά γρήγορη.

79
00:03:22,090 --> 00:03:23,470
>> Αναζήτηση είναι κακό όμως, σωστά;

80
00:03:23,470 --> 00:03:26,280
Για να μπορέσουμε να βρούμε μια
στοιχείο σε μια συνδεδεμένη λίστα,

81
00:03:26,280 --> 00:03:29,154
είτε μεμονωμένα είτε διπλά συνδεδεμένες,
θα πρέπει να είναι γραμμική αναζήτηση.

82
00:03:29,154 --> 00:03:32,320
Πρέπει να ξεκινήσουμε από την αρχή και
μετακινήστε το τέλος, ή να αρχίσει στο τέλος κίνηση

83
00:03:32,320 --> 00:03:33,860
στην αρχή.

84
00:03:33,860 --> 00:03:35,474
Δεν έχουμε πια τυχαίας προσπέλασης.

85
00:03:35,474 --> 00:03:37,265
Έτσι, αν κάνουμε μια
πολλή αναζήτηση, ίσως

86
00:03:37,265 --> 00:03:39,830
μια συνδεδεμένη λίστα δεν είναι
είναι και τόσο καλό για εμάς.

87
00:03:39,830 --> 00:03:43,750
>> Είναι επίσης πολύ
δύσκολο να ταξινομήσετε, σωστά;

88
00:03:43,750 --> 00:03:45,666
Ο μόνος τρόπος για να
πραγματικά ταξινομήσετε μια συνδεδεμένη λίστα

89
00:03:45,666 --> 00:03:47,870
είναι να ταξινομήσετε όπως εσείς να το κατασκευάσει.

90
00:03:47,870 --> 00:03:50,497
Αλλά αν το ταξινομήσετε όπως εσείς
την κατασκευή τους, δεν είστε πλέον

91
00:03:50,497 --> 00:03:51,830
κάνοντας γρήγορη ενθέσεις πια.

92
00:03:51,830 --> 00:03:53,746
Δεν είστε μόνο στερέωση
πράγματα πάνω στο μέτωπο.

93
00:03:53,746 --> 00:03:55,710
Θα πρέπει να βρείτε το
σωστό σημείο για να το θέσω,

94
00:03:55,710 --> 00:03:57,820
και στη συνέχεια την εισαγωγή σας
γίνεται σχεδόν τόσο κακή

95
00:03:57,820 --> 00:03:59,390
ως εισαγωγή σε μια σειρά.

96
00:03:59,390 --> 00:04:03,130
Έτσι, συνδεδεμένες λίστες δεν είναι
τόσο μεγάλη για την ταξινόμηση των δεδομένων.

97
00:04:03,130 --> 00:04:05,830
>> Είναι επίσης αρκετά μικρό, το μέγεθος-σοφός.

98
00:04:05,830 --> 00:04:08,496
Διπλά συνδεδεμένη λίστα ελαφρώς
μεγαλύτερο από μεμονωμένα συνδεδεμένες λίστες,

99
00:04:08,496 --> 00:04:10,620
η οποία είναι ελαφρώς μεγαλύτερα
από συστοιχίες, αλλά δεν είναι

100
00:04:10,620 --> 00:04:13,330
ένα τεράστιο ποσό των σπατάλη χώρου.

101
00:04:13,330 --> 00:04:18,730
Έτσι, αν το διάστημα είναι σε ένα ασφάλιστρο, αλλά
δεν είναι μια πραγματικά έντονη πριμοδότηση,

102
00:04:18,730 --> 00:04:22,180
αυτό θα μπορούσε να είναι ο σωστός τρόπος να πάει.

103
00:04:22,180 --> 00:04:23,330
>> Hash πίνακες.

104
00:04:23,330 --> 00:04:25,850
Εισαγωγή σε έναν πίνακα κατακερματισμού
είναι αρκετά απλή.

105
00:04:25,850 --> 00:04:26,980
Είναι μια διαδικασία δύο σταδίων.

106
00:04:26,980 --> 00:04:30,700
Πρώτα πρέπει να τρέχει μέσα από τα δεδομένα μας
μια συνάρτηση κατακερματισμού για να πάρετε έναν κωδικό κατακερματισμού,

107
00:04:30,700 --> 00:04:37,550
και στη συνέχεια εισάγουμε το στοιχείο σε ο
hash πίνακα στη συγκεκριμένη τοποθεσία κωδικό κατακερματισμού.

108
00:04:37,550 --> 00:04:40,879
>> Διαγραφή, παρόμοια με συνδεδεμένη λίστα,
Είναι εύκολο μόλις βρείτε το στοιχείο.

109
00:04:40,879 --> 00:04:43,170
Θα πρέπει να το βρουν την πρώτη,
αλλά στη συνέχεια, όταν το διαγράψετε,

110
00:04:43,170 --> 00:04:45,128
το μόνο που χρειάζεται να ανταλλάσσουν
ένα ζευγάρι των δεικτών,

111
00:04:45,128 --> 00:04:47,250
αν χρησιμοποιείτε Ξεχωριστές αλυσίδες.

112
00:04:47,250 --> 00:04:49,942
Εάν χρησιμοποιείτε την ανίχνευση,
ή αν δεν είστε

113
00:04:49,942 --> 00:04:51,650
χρησιμοποιώντας την αλυσιδωτή σύνδεση σε όλα
στον πίνακα κατακερματισμού σας,

114
00:04:51,650 --> 00:04:53,040
διαγραφή είναι πραγματικά πολύ εύκολο.

115
00:04:53,040 --> 00:04:57,134
Το μόνο που χρειάζεται να κάνετε είναι να το hash
δεδομένων, και στη συνέχεια να πάμε σε αυτήν τη θέση.

116
00:04:57,134 --> 00:04:58,925
Και με την προϋπόθεση να μην κάνετε
έχετε οποιεσδήποτε συγκρούσεις,

117
00:04:58,925 --> 00:05:01,650
θα είστε σε θέση να διαγράψετε πολύ γρήγορα.

118
00:05:01,650 --> 00:05:04,930
>> Τώρα, αναζήτηση είναι όπου τα πράγματα
πάρετε μια λίγο πιο περίπλοκη.

119
00:05:04,930 --> 00:05:06,910
Είναι κατά μέσο όρο καλύτερη
από συνδεδεμένες λίστες.

120
00:05:06,910 --> 00:05:09,560
Εάν χρησιμοποιείτε αλυσιδωτή σύνδεση,
έχετε ακόμα μια συνδεδεμένη λίστα,

121
00:05:09,560 --> 00:05:13,170
πράγμα που σημαίνει ότι έχετε ακόμα το
αναζήτηση ζημιώνει μια συνδεδεμένη λίστα.

122
00:05:13,170 --> 00:05:18,390
Αλλά επειδή παίρνετε συνδέονται σας
κατάλογο και διάσπαση πάνω από 100 ή 1.000

123
00:05:18,390 --> 00:05:25,380
ή n στοιχεία στον πίνακα κατακερματισμού σας, είστε
συνδεδεμένες λίστες είναι όλα μια νιοστή το μέγεθος.

124
00:05:25,380 --> 00:05:27,650
Είναι όλα σημαντικά μικρότερα.

125
00:05:27,650 --> 00:05:32,080
Έχετε n συνδεδεμένες λίστες, αντί
μιας συνδεδεμένης λίστας μεγέθους n.

126
00:05:32,080 --> 00:05:34,960
>> Και έτσι αυτό πραγματικού κόσμου σταθερή
παράγοντα, το οποίο σε γενικές γραμμές

127
00:05:34,960 --> 00:05:39,730
δεν μιλάμε για πολυπλοκότητα χρόνου,
κάνει πραγματικά τη διαφορά εδώ.

128
00:05:39,730 --> 00:05:43,020
Έτσι αναζήτηση εξακολουθεί να είναι γραμμική
αναζήτηση αν χρησιμοποιείτε αλυσιδωτή σύνδεση,

129
00:05:43,020 --> 00:05:46,780
αλλά το μήκος του καταλόγου
ψάχνετε μέσω

130
00:05:46,780 --> 00:05:50,080
είναι πολύ, πολύ μικρό σε σύγκριση.

131
00:05:50,080 --> 00:05:52,995
Και πάλι, αν είναι διαλογής σας
Στόχος εδώ, hash πίνακα

132
00:05:52,995 --> 00:05:54,370
ίσως δεν είναι η σωστή τρόπος να πάει.

133
00:05:54,370 --> 00:05:56,830
Απλά χρησιμοποιήστε έναν πίνακα εάν η ταξινόμηση
Είναι πραγματικά σημαντικό για εσάς.

134
00:05:56,830 --> 00:05:58,590
>> Και μπορούν να διατρέξουν όλη την κλίμακα μεγέθους.

135
00:05:58,590 --> 00:06:01,640
Είναι δύσκολο να πούμε αν μια
hash πίνακα είναι μικρή ή μεγάλη,

136
00:06:01,640 --> 00:06:04,110
επειδή εξαρτάται πραγματικά από
πόσο μεγάλο τραπέζι hash σας είναι.

137
00:06:04,110 --> 00:06:07,340
Αν είστε μόνο πρόκειται να αποθήκευση
πέντε στοιχεία στον πίνακα κατακερματισμού σας,

138
00:06:07,340 --> 00:06:10,620
και έχετε ένα πίνακα κατακερματισμού
με 10.000 στοιχεία σε αυτό,

139
00:06:10,620 --> 00:06:12,614
είστε πιθανώς σπαταλάτε πολύ χώρο.

140
00:06:12,614 --> 00:06:15,030
Αντίθεση Μπορείτε να μπορεί επίσης να
έχουν πολύ συμπαγής πίνακες κατακερματισμού,

141
00:06:15,030 --> 00:06:18,720
αλλά το μικρότερο τραπέζι hash σας παίρνει,
ο πλέον κάθε μία από τις συνδεδεμένες λίστες

142
00:06:18,720 --> 00:06:19,220
παίρνει.

143
00:06:19,220 --> 00:06:22,607
Και έτσι πραγματικά δεν υπάρχει τρόπος να ορίσουμε
ακριβώς το μέγεθος ενός πίνακα κατακερματισμού,

144
00:06:22,607 --> 00:06:24,440
αλλά είναι μάλλον ασφαλές
να πω ότι είναι γενικά

145
00:06:24,440 --> 00:06:27,990
πρόκειται να είναι μεγαλύτερο από ένα συνδεδεμένο
Λίστα αποθήκευση των ίδιων στοιχείων,

146
00:06:27,990 --> 00:06:30,400
αλλά μικρότερο από ένα trie.

147
00:06:30,400 --> 00:06:32,720
>> Και προσπαθεί είναι η τέταρτη
αυτών των δομών

148
00:06:32,720 --> 00:06:34,070
ότι έχουμε μιλήσει.

149
00:06:34,070 --> 00:06:36,450
Τοποθέτηση σε trie είναι πολύπλοκη.

150
00:06:36,450 --> 00:06:38,400
Υπάρχει μια πολύ δυναμική
κατανομή μνήμης,

151
00:06:38,400 --> 00:06:40,780
ειδικά στην αρχή,
καθώς ξεκινάτε να οικοδομήσουμε.

152
00:06:40,780 --> 00:06:43,700
Αλλά είναι σταθερά χρόνου.

153
00:06:43,700 --> 00:06:47,690
Είναι μόνο το ανθρώπινο στοιχείο
Εδώ που το καθιστά δύσκολο.

154
00:06:47,690 --> 00:06:53,250
Έχοντας να αντιμετωπίσουν κενό δείκτη, malloc
χώρο, πηγαίνετε εκεί, ενδεχομένως malloc χώρο

155
00:06:53,250 --> 00:06:54,490
Από εκεί και πάλι.

156
00:06:54,490 --> 00:06:58,880
Το είδος του παράγοντα εκφοβισμό
δείκτες στη δυναμική κατανομή μνήμης

157
00:06:58,880 --> 00:07:00,130
είναι το εμπόδιο για να καθαρίσει.

158
00:07:00,130 --> 00:07:04,550
Αλλά από τη στιγμή που θα έχετε καθαριστεί, εισαγωγή
στην πραγματικότητα έρχεται αρκετά απλή,

159
00:07:04,550 --> 00:07:06,810
και σίγουρα είναι σταθερά χρόνου.

160
00:07:06,810 --> 00:07:07,680
>> Η διαγραφή είναι εύκολο.

161
00:07:07,680 --> 00:07:11,330
Το μόνο που χρειάζεται να κάνετε είναι να περιηγηθείτε κάτω από ένα
ζευγάρι των δεικτών και δωρεάν κόμβο,

162
00:07:11,330 --> 00:07:12,420
έτσι ώστε να είναι αρκετά καλή.

163
00:07:12,420 --> 00:07:13,930
Αναζήτηση είναι επίσης αρκετά γρήγορα.

164
00:07:13,930 --> 00:07:16,780
Είναι βασισμένο μόνο σχετικά με την
το μήκος των δεδομένων σας.

165
00:07:16,780 --> 00:07:19,924
Έτσι, αν όλα τα δεδομένα σας είναι
πέντε σειρές χαρακτήρα,

166
00:07:19,924 --> 00:07:22,590
για παράδειγμα, είστε αποθήκευση πέντε
στοιχειοσειρές στο Trie σας,

167
00:07:22,590 --> 00:07:25,439
διαρκεί μόνο πέντε βήματα για να
βρείτε αυτό που ψάχνετε.

168
00:07:25,439 --> 00:07:28,480
Πέντε είναι απλά ένας σταθερός παράγοντας, έτσι
πάλι, εισαγωγή, διαγραφή και αναζήτηση

169
00:07:28,480 --> 00:07:31,670
εδώ είναι όλα σταθερά χρόνου, αποτελεσματικά.

170
00:07:31,670 --> 00:07:34,880
>> Ένα άλλο πράγμα είναι ότι είναι trie σας
πραγματικά το είδος των ήδη διευθετηθεί, έτσι δεν είναι;

171
00:07:34,880 --> 00:07:36,800
Δυνάμει του πώς είμαστε
εισαγωγή στοιχείων,

172
00:07:36,800 --> 00:07:40,060
πηγαίνοντας επιστολή με την επιστολή της
κλειδί, ή κατά ψηφίο του κλειδιού,

173
00:07:40,060 --> 00:07:45,084
τυπικά, trie σας καταλήγει να είναι
είδος ταξινομημένο ως το φτιάξεις.

174
00:07:45,084 --> 00:07:47,250
Δεν κάνει πραγματικά
λογικό να σκεφτούμε διαλογής

175
00:07:47,250 --> 00:07:49,874
με τον ίδιο τρόπο που σκεφτόμαστε για
με συστοιχίες, ή συνδεδεμένες λίστες,

176
00:07:49,874 --> 00:07:51,070
ή πίνακες κατακερματισμού.

177
00:07:51,070 --> 00:07:54,780
Αλλά κατά κάποιο τρόπο, σας
trie ταξινομούνται as you go.

178
00:07:54,780 --> 00:07:58,630
>> Το μειονέκτημα, βέβαια, είναι ότι η
α trie γρήγορα γίνεται τεράστια.

179
00:07:58,630 --> 00:08:02,970
Από κάθε σημείο σύνδεσης, ίσως
have-- αν το κλειδί σας αποτελείται από ψηφία,

180
00:08:02,970 --> 00:08:04,880
έχετε 10 άλλους
μέρη που μπορείτε να πάτε, η οποία

181
00:08:04,880 --> 00:08:07,490
σημαίνει ότι κάθε κόμβος
Περιέχει πληροφορίες

182
00:08:07,490 --> 00:08:11,440
σχετικά με τα δεδομένα που θέλετε να αποθηκεύσετε
σε αυτόν τον κόμβο, καθώς και 10 δείκτες.

183
00:08:11,440 --> 00:08:14,430
Η οποία, σε CS50 IDE, είναι 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Έτσι είναι τουλάχιστον 80 byte για
κάθε κόμβος που δημιουργείτε,

185
00:08:17,220 --> 00:08:19,240
και ότι δεν είναι καν καταμέτρηση δεδομένων.

186
00:08:19,240 --> 00:08:24,950
Και αν οι κόμβοι σας
γράμματα αντί ψηφία,

187
00:08:24,950 --> 00:08:27,825
τώρα έχετε 26 δείκτες
από κάθε τοποθεσία.

188
00:08:27,825 --> 00:08:32,007
Και 26 φορές 8 είναι κατά πάσα πιθανότητα 200
bytes, ή κάτι τέτοιο.

189
00:08:32,007 --> 00:08:33,840
Και έχετε κεφαλαίων
και μπορείτε να lowercase--

190
00:08:33,840 --> 00:08:35,381
δείτε πού πάω με αυτό, έτσι δεν είναι;

191
00:08:35,381 --> 00:08:37,500
Κόμβους σας μπορεί να πάρει πραγματικά
μεγάλο, και έτσι η trie

192
00:08:37,500 --> 00:08:40,470
η ίδια, συνολικά, μπορεί να
να πάρει πραγματικά μεγάλο, πάρα πολύ.

193
00:08:40,470 --> 00:08:42,630
Έτσι, αν το διάστημα είναι σε υψηλό
premium στο σύστημά σας,

194
00:08:42,630 --> 00:08:45,830
α trie μπορεί να μην είναι ο σωστός τρόπος για να
πάει, ακόμα κι αν άλλα οφέλη

195
00:08:45,830 --> 00:08:47,780
μπαίνουν στο παιχνίδι.

196
00:08:47,780 --> 00:08:48,710
Είμαι ο Νταγκ Lloyd.

197
00:08:48,710 --> 00:08:50,740
Αυτό είναι CS50.

198
00:08:50,740 --> 00:08:52,316