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
Вы не проста лавіраваць
рэчы на ​​фронт.

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 або 1000

123
00:05:18,390 --> 00:05:25,380
або п элементаў у вашай хэш-табліцы, вы
звязаныя спісы ўсё адно п-памеру.

124
00:05:25,380 --> 00:05:27,650
Яны ўсё значна менш.

125
00:05:27,650 --> 00:05:32,080
Вы н звязаныя спісы замест
аднаго звязанага спісу памеру п.

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
і ў вас ёсць хэш-табліцу
10000 элементаў у ім,

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
Маючы сутыкнуцца нулявы паказальнік, Таноса
прастору, туды, магчыма, Таноса прастору

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
>> Іншая справа, што ваш 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 сартуецца, як вы ідзяце.

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 байт.

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
Вашы вузлы могуць атрымаць сапраўды
вялікі, і таму Trie

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
Trie не можа быць правільным спосабам
ісці, нават калі іншыя яго перавагі

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