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

2
00:00:05,259 --> 00:00:08,300
דאג 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
מערכים, רשימות מקושרות,
שולחנות חשיש, ומנסה.

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
כל מה שאנחנו הולכים לדבר
על זה בכיתה במונחים של ג

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
ובדיקה של איירי אם אתה באמת
לא אכפת לי ההכנסה ומחיקה

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
מיון הכנסה, מיון בועות, למזג
סוג, אנחנו תמיד השתמשנו מערכים לעשות את זה,

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
אתה לא רק tacking
דברים על החזית.

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
>> שולחנות חשיש.

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
ואז אנחנו מכניסים את האלמנט ל
טבלת חשיש שבמיקום קוד חשיש.

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
כל מה שאתה צריך לעשות הוא חשיש
הנתונים, ולאחר מכן ללכת למיקום זה.

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
שוב, אם מיון הוא שלך
מטרה כאן, שולחן של החשיש

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
קשה לומר אם
שולחן חשיש קטן או גדול,

136
00:06:01,640 --> 00:06:04,110
כי זה באמת תלוי ב
כמה גדול שלך הוא שולחן החשיש.

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
אבל שולחן החשיש שלך הקטן יותר מקבל,
כל אחד מרשימות המקושרות אלה כבר

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
קטן יותר, אך יותר מאיירי.

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
ההכנסה לאיירי היא מורכבת.

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
לאחר להיתקל מצביע null, 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
לדוגמא, אתה אחסון חמישה
מחרוזות תווים באיירי,

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
>> דבר נוסף הוא שאיירי שלך היא
בעצם סוג של כבר מסודרים, נכון?

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
בדרך כלל, את איירי בסופו להיות
סוג של מסודרים כמו שאתה בונה אותו.

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
אבל במובן מסוים,
איירי ממוינת כמו שאתה הולך.

178
00:07:54,780 --> 00:07:58,630
>> החסרון, כמובן, הוא ש
איירי במהירות הופכת להיות ענק.

179
00:07:58,630 --> 00:08:02,970
מכל נקודת צומת, אתה עלול
נו-- אם המפתח שלך מורכב מספרות,

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
אשר, על IDE CS50, הוא 80 בתים.

184
00:08:14,430 --> 00:08:17,220
אז זה לפחות 80 בתים ל
כל צומת שאתה יוצר,

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
בתים, או משהו כזה.

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
צמתים שלך יכולים לקבל באמת
הגדולה וכל כך איירי,

192
00:08:37,500 --> 00:08:40,470
עצמו, הכולל, יכול
להגיע ממש גדול, יותר מדי.

193
00:08:40,470 --> 00:08:42,630
אז אם יש מקום בבית גבוה
פרמיה על המערכת שלך,

194
00:08:42,630 --> 00:08:45,830
איירי לא יכולה להיות הדרך הנכונה
ללכת, למרות שהיתרונות האחרים שלה

195
00:08:45,830 --> 00:08:47,780
נכנס לשחק.

196
00:08:47,780 --> 00:08:48,710
אני דאג לויד.

197
00:08:48,710 --> 00:08:50,740
זה CS50.

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