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
на самай справе не чатыры байта.

36
00:01:33,700 --> 00:01:36,090
Гэта вельмі часта гэтыя
дзён восем байт, якія

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
Цяпер у той жа час, мы
яшчэ гаворым байт, праўда?

41
00:01:46,700 --> 00:01:49,140
Мы не гаворым абавязкова
мегабайтах або гігабайтах,

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
Але давайце паспрабуем кананізаваць
Першыя аперацыі

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
>> Так што гэта толькі некаторыя З-код,
нават не поўная праграма

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
кропка кропка кропка, ёсць нешта
там, кропка кропка кропка, што-то там.

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, што мы назавем N,
але мы маглі б назваць гэта што-небудзь,

65
00:02:48,790 --> 00:02:51,920
а затым структура вузла зорка называецца побач.

66
00:02:51,920 --> 00:02:55,520
І толькі, каб быць ясным, што ў другім
лінія, на шостым радку, што гэта такое?

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
і вось чаму мы сказалі структура
вузел зорка, зорка, які пазначае

77
00:03:20,810 --> 00:03:22,370
паказальнік або адрас.

78
00:03:22,370 --> 00:03:26,390
ОК, так што зараз калі выказаць здагадку, што мы маем
гэта N даступныя для нас, і давайце

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
Як першыя, хто я думаю, Дэвід
быў наш валанцёр у панядзелак,

88
00:03:52,992 --> 00:03:54,700
ён, паказваючы на
ўся звязаны спіс,

89
00:03:54,700 --> 00:03:57,820
Гэта як калі б мы перадаем
Дэвід, як наш аргумент тут.

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

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-- хутчэй, калі паказальнік кропка N роўны

107
00:04:57,410 --> 00:05:02,290
роўная пераменная N, то
Аргумент, які быў прыняты ў,

108
00:05:02,290 --> 00:05:05,370
то я хачу, каб ісці наперад
і сказаць, вярнуцца праўда.

109
00:05:05,370 --> 00:05:11,020
Я знайшоў нумар N ўнутры
адзін з вузлоў майго звязанага спісу.

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
а таму, што паказальнік не з'яўляецца паказальнікам
і сам па сабе не фактычны структура,

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
ня N, тое, што я хачу зрабіць?

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
І, нарэшце, я ўдарыў пусты, не маючы
знайшоў яшчэ N, я проста вярнуцца ілжывым.

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
Калі няма, то я абнавіць маю руку,
АКА паказальнік, каб паказаць

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
гэта ўвесці абстрактны дадзеныя, паколькі гэта
не з'яўляецца З, што, гэта не 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
даць мне вызначэнне тыпу ў
на структуру ўнутры чаркі,

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
Цяпер поп, па пагадненні,
не прымаць аргумент.

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
І на самай справе З не маюць гэтую функцыю.

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
Я магу выкарыстоўваць Таноса.

276
00:13:03,580 --> 00:13:06,710
І я магу сказаць, любую колькасць
байт я хачу вярнуцца на гэтыя Nths.

277
00:13:06,710 --> 00:13:10,910
І ўсё, што трэба захоўваць у лічбах
Пераменная тут ўнутры гэтай структуры

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
Так, гэта паказальнік на першы
байт гэтага кавалка памяці,

281
00:13:21,300 --> 00:13:24,940
або, больш канкрэтна, адрас
з першых з гэтых байт.

282
00:13:24,940 --> 00:13:27,300
Не мае значэння, калі гэта адзін
байт або байт, млрд

283
00:13:27,300 --> 00:13:28,890
Мне проста трэба, каб клапаціцца аб першай.

284
00:13:28,890 --> 00:13:31,530
Таму што тое, што Таноса гарантыі і
мае аперацыйнай сістэмы гарантый,

285
00:13:31,530 --> 00:13:34,170
з'яўляецца тое, што кавалак памяці I
атрымаць, ён збіраецца быць сумежнымі.

286
00:13:34,170 --> 00:13:35,378
Там не будзе прабелаў.

287
00:13:35,378 --> 00:13:38,576
Так што, калі я папрасіў 50
байт або 1000 байт,

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
Дык вось, каб кампраміс.

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
Таму Таноса дасць нам
бесперапынны кавалак памяці.

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
Ставіць ці з чаргі, як дадаць або выдаліць,
гэта проста аматар спосаб сказаць гэта,

311
00:14:35,660 --> 00:14:38,100
Ставіць ці з чаргі, як след.

312
00:14:38,100 --> 00:14:41,170
Я магу толькі даць сабе-структуру
што зноў ёсць масіў шэрагу, у

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
Я не ведаю, трэба
пярэдняя майго стэка.

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-- я ў чаргу, або штурхнуў.

324
00:15:14,220 --> 00:15:20,150
Цяпер я ў чаргу 50, а затым
51, а затым 61, і кропка кропка кропка.

325
00:15:20,150 --> 00:15:21,070
Дык вось паставіць у чаргу.

326
00:15:21,070 --> 00:15:23,176
Я ў чарзе 50, то 51, то 61.

327
00:15:23,176 --> 00:15:25,050
І, што выглядае ідэнтычна
у Стэк да гэтага часу,

328
00:15:25,050 --> 00:15:27,190
акрамя мне трэба зрабіць адно змяненне.

329
00:15:27,190 --> 00:15:33,680
Мне трэба, каб абнавіць гэты памер, так што я іду
ад нуля да адзінкі да двух-трох Цяпер.

330
00:15:33,680 --> 00:15:35,760
Як з чаргі?

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, якія
быў там у 05: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
N-й фронт, чый першапачатковы
Значэнне павінна быць што?

354
00:16:33,729 --> 00:16:35,270
Нуль, толькі пачатак спісу.

355
00:16:35,270 --> 00:16:40,876
Але цяпер у дадатак да памяншаючы
памер, мы проста павялічваем фронт.

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
І на самай справе, тое, што аператар
у З, верагодна, дазваляе

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
але мы па-ранейшаму губляюць размер-- хутчэй,
Магчымасць змяняць памер, калі мы не зробім гэта.

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
Маллок, або іншыя падобныя
Функцыя, дакладна.

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
Што б вы модулю выкарыстоўваць тут.

397
00:18:35,830 --> 00:18:38,520
Так як правіла, пры выкарыстанні
мод, вы маглі б зрабіць гэта

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
Але толькі рабіць па модулю пяць
верагодна, не з'яўляецца дастатковым,

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
>> ФІЛЬМ: Даўным-даўно,
быў хлопец па імені Джэк.

412
00:19:21,890 --> 00:19:25,330
Калі справа дайшла да прыняцця сябрамі,
Джэк не маюць спрыту.

413
00:19:25,330 --> 00:19:28,220
Так Джэк пайшоў пагаварыць з
Найбольш папулярны хлопец ведаў.

414
00:19:28,220 --> 00:19:30,920
Ён пайшоў да Лу і спытала, што мне рабіць?

415
00:19:30,920 --> 00:19:33,400
Лу ўбачыў, што яго сябар
быў сапраўды засмучаны.

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
Такім чынам, яны адправіліся ў Джэка.

422
00:19:44,550 --> 00:19:47,520
І Джэк паказаў Лу акно
дзе ён захоўваў усе свае кашулі,

423
00:19:47,520 --> 00:19:49,260
і штаны, і шкарпэткі.

424
00:19:49,260 --> 00:19:52,290
Лу сказаў, я бачу, у вас ёсць
усе вашыя адзення ў кучу.

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
Затым наступае наступны
раніцай, і да я скачу.

429
00:20:03,210 --> 00:20:06,380
Я іду ў поле і атрымаць
мая адзенне з верхняй.

430
00:20:06,380 --> 00:20:09,070
Лу хутка зразумеў,
праблема з Джэкам.

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
Лу ўзяў вопратку Джэка і
павесіў у шафу.

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
Хіба вы не бачыце? сказаў Лу.

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
Усё дзякуючы Лу і
яго выдатны чарзе.

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
Што мы маем паказальнікі,
што ў нас ёсць Таноса,

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, мае гігабайт аператыўнай памяці або памяці

462
00:21:31,850 --> 00:21:33,050
ці два гігабайта ці чатыры.

463
00:21:33,050 --> 00:21:34,450
Гэта сапраўды не мае значэння.

464
00:21:34,450 --> 00:21:37,240
Ваша аперацыйная сістэма
Вокны ці 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
Так што, калі ў вас ёсць два гігабайтамі аператыўнай памяці, гэта
як кампутар можа думаць пра гэта.

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

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
Гэта як нулявым байт,
байт адным, байт 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
отводка новы кавалачак памяці.

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
У рэчаіснасці, яна па-ранейшаму
ёсць крыміналістычнага.

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
бібліятэка, або калі вы, хлопцы,
патэлефанаваць і спытаць Таноса

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
Гэта тое ж самае АЗП.

511
00:23:44,285 --> 00:23:45,160
Гэта ж памяць.

512
00:23:45,160 --> 00:23:49,080
Гэта проста АЗП гэта да
там замест тут.

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
Іншымі словамі, кожны
выкліку Таноса,

518
00:24:01,140 --> 00:24:03,430
Вы надаецца кавалачак
памяці зверху,

519
00:24:03,430 --> 00:24:06,630
то, магчыма, трохі ніжэй, то трохі
ніжэй, кожны раз, калі вы тэлефануеце Таноса,

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
Гэтыя два стрэлы на
Інтэнсіўны курс для аднаго.

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
Такім чынам, гэта з'яўляецца прыкладам вы можаце прачытаць
пра больш падрабязна ў Вікіпедыі.

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 сімвал зоркі 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
АКА паўкокс зорка, ж
рэч, як радок.

549
00:25:22,100 --> 00:25:24,920
І гэта называецца як заўгодна
бар у гэтым прыкладзе.

550
00:25:24,920 --> 00:25:27,710
І тады сімвал з 12
толькі з пункту гледжання непрафесіяналы,

551
00:25:27,710 --> 00:25:31,750
што сімвал з дужка 12 робіць для нас?

552
00:25:31,750 --> 00:25:33,440
Што ён робіць?

553
00:25:33,440 --> 00:25:36,490
Вылучэнне памяці, спецыяльна
12 байта для 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
але толькі да
Пэўную колькасць байтаў.

559
00:25:51,190 --> 00:25:53,860
Такім чынам, трэці аргумент кажа,
колькі байт неабходна скапіяваць?

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
скапіяваныя ў памяць паказаў на кропцы С.

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
у адрас паказаў на С. Але З
толькі прэвентыўна даецца як 12 байт.

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

587
00:27:06,270 --> 00:27:10,690
Верхні левы адзін кранштэйн З нуля і
ніжні правы адзін кранштэйн З 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 або З 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 байт,
Вы збіраецеся пачаць перазапіс бар.

598
00:27:44,460 --> 00:27:47,280
Зараз гэта памылка, але гэта
на самай справе не мае вялікага значэння.

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 байт, і мы супер бяспечна.

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
>> З мовай вельмі нізкі ўзровень.

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
не толькі змяняе лакальныя зменныя,
або яго аргументы, таксама таемна штурхнуў

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
такім чынам, што ўвод карыстальніка перавызначаем
або перапісвае, што чырвоны раздзел,

621
00:28:57,030 --> 00:28:59,820
лагічна, калі кампутара
проста хачу, каб слепа выказаць здагадку,

622
00:28:59,820 --> 00:29:03,830
што байт у гэтай чырвонай лустачку з'яўляюцца
адрас, па якім ён павінен вярнуць,

623
00:29:03,830 --> 00:29:09,020
што, калі праціўнік досыць разумны, або
пашанцавала паставіць паслядоўнасць байт

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
Або напішыце свой пароль мне?

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
заўважыць, што паслядоўнасць байт.

641
00:30:01,580 --> 00:30:05,020
Аб 835 З нуля восем нулёў.

642
00:30:05,020 --> 00:30:08,960
А цяпер, як артыкул Вікіпедыі тут
прапанаваў, калі вы зараз на самай справе пачаць

643
00:30:08,960 --> 00:30:12,460
маркіроўка байты ў кампутары гадоў
памяці, што артыкул Вікіпедыі

644
00:30:12,460 --> 00:30:19,060
прапаную, што, тое, што, калі адрас
гэтай верхнім левым байта 80 З 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
І так перапаўненне буфера
атака па сваёй сутнасці

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
у З, што мы сапраўды павінны
доступ у любую кропку ў памяці.

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
Я не хачу, каб проста слепа сказаць
што вы павінны скапіяваць столькі байт,

663
00:31:14,110 --> 00:31:16,140
а даўжыня панэлі.

664
00:31:16,140 --> 00:31:18,910
Я хачу сказаць, скапіруйце ў
колькасць байт у радку

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
Мы літаральна павінны выкарыстоўваць той час як цыкл
як адзін я напісаў некаторы час таму.

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
і разьбы рэчы наш уласны?

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
Мы можам абсалютна пераматаць тыдня
два, кінуць іх у масіў,

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
што адзін, мы можам рэалізаваць яго
з структуры, як гэта.

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
Дык вось, як мы маглі б
ажыццявіць, што ў структуры.

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
і гэта прымае два аргументу,
цэлы лік N і паказальнік

757
00:35:36,980 --> 00:35:41,400
да вузла, так што паказальнік на дрэва
або паказальнік на корань дрэва,

758
00:35:41,400 --> 00:35:43,482
як я магу ісці аб пошуку N?

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
Калі дрэва роўна роўная нуля, з'яўляецца N
ў гэтым дрэве ці не ў гэтым дрэве?

762
00:35:54,279 --> 00:35:55,070
Гэта не можа быць, ці не так?

763
00:35:55,070 --> 00:35:56,870
Калі я міма нуль,
няма нічога.

764
00:35:56,870 --> 00:35:59,230
Я мог бы таксама проста
слепа сказаць вярнуцца ілжывым.

765
00:35:59,230 --> 00:36:04,050
Калі вы не даюць мне нічога, я, вядома, не магу
знайсці лік N. Так што яшчэ я мог бы

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
што я быў перададзены значэнне N.

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
Так што, калі N менш, чым дрэва стрэлкі
N, я хачу, каб канцэптуальна ідзіце налева.

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
і я быў прыняты, што верхні
стрэлка, які накіраваны ўніз.

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
или-- я не магу 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
Я шукаю N ў дрэве злева стрэлкі
астатняе, калі п больш, чым значэнне

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
прайсці N гэта і рэкурсіўны пошук
суб-дрэва і проста вяртанне

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, або растравы, або пінг,

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
Гэта, здаецца, не варта захоўваць
чорны піксель, чорны піксель, чорны піксель,

840
00:39:41,550 --> 00:39:44,790
кропка, кропка, кропка, цэлая куча
чорныя пікселі для першага радка разгорткі,

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
чырвоны пікселяў, чырвоныя пікселі, то ў цэлым
Букет з жоўтых кропак, жоўты, праўда?

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
каб паменшыць нашу памер файла з, як
мегабайт у кілабайт, то

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

856
00:40:24,550 --> 00:40:28,200
гэтак жа, як вы робіце ў PSET4
з Фармат графічнага файла,

857
00:40:28,200 --> 00:40:32,060
чаму б вам проста не ўяўляюць
левая калонка пікселяў, напрыклад

858
00:40:32,060 --> 00:40:35,370
куча чорных пікселяў, куча
чырвоны, і куча жоўты,

859
00:40:35,370 --> 00:40:39,210
а потым проста нейкім чынам кадзіраваць
Ідэя паўтарыць гэты 100 разоў

860
00:40:39,210 --> 00:40:41,020
або паўтарыць гэта ў 1000 раз?

861
00:40:41,020 --> 00:40:43,430
Дзе 100 або 1000 з'яўляецца
проста цэлы лік, так што вы

862
00:40:43,430 --> 00:40:47,290
можа сысці з рук толькі адзін нумар
замест сотняў або тысяч

863
00:40:47,290 --> 00:40:48,270
дадатковых пікселяў.

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 адзін байт, ці восем біт.

906
00:42:45,410 --> 00:42:47,360
І гэта свайго роду нямы, ці не так?

907
00:42:47,360 --> 00:42:51,160
Таму што вы, верагодна, увядзіце A
і Е, я і вываду і U шмат

908
00:42:51,160 --> 00:42:55,270
часцей, чым, як W або Q або Z,
у залежнасці ад мовы, на якім

909
00:42:55,270 --> 00:42:56,610
Вы пішаце, вядома ,.

910
00:42:56,610 --> 00:42:59,600
І так, чаму мы з дапамогай
восем бітаў для кожнага лісты,

911
00:42:59,600 --> 00:43:02,040
у тым ліку не менш
папулярныя літары, праўда?

912
00:43:02,040 --> 00:43:05,300
Чаму б не выкарыстоўваць меншая колькасць біт для
супер папулярныя літары,

913
00:43:05,300 --> 00:43:07,760
як Е, то, думаю, вы
першы ў Кола Фартуны,

914
00:43:07,760 --> 00:43:10,450
і выкарыстоўваць больш бітаў для
менш папулярныя літары?

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
Так што гэтая праблема
з декодируемости з Морзэ

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
можа быць, гэта два E-небудзь ці, можа быць, гэта адзін І.

939
00:44:11,254 --> 00:44:13,670
Так што мы павінны сістэму, што гэта
трохі разумнейшыя, чым гэта.

940
00:44:13,670 --> 00:44:16,851
Такім чынам, чалавек па імі Хафман гадоў
таму прыдумаў менавіта гэта.

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
складаецца толькі з A, B, C у 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's, і E-х, вось

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
з'яўляюцца E, і тры іншыя частоты.

952
00:44:39,660 --> 00:44:41,960
Мы налічылі там ўручную
і проста зрабіў матэматыку.

953
00:44:41,960 --> 00:44:44,579
>> Так што атрымліваецца, што
Хафман, некаторы час таму,

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
>> І так, што Хофман прапанаваў ёсць,
калі вы хочаце, каб прадстаўляць B,

985
00:46:05,070 --> 00:46:10,080
а не ўяўляюць сабой колькасць, як 66
ASCII, які восем цэлыя біт,

986
00:46:10,080 --> 00:46:13,360
вы ведаеце, што толькі крама
ўзор нуль, нуль, нуль,

987
00:46:13,360 --> 00:46:17,030
нуля, таму што гэта шлях
ад майго дрэва, дрэва Хафман г,

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
адправіць восем біт, якія ўяўляюць Е.
Замест гэтага, адправіць які набор бітаў?

991
00:46:26,290 --> 00:46:26,890
Адзін.

992
00:46:26,890 --> 00:46:30,410
І, што прыемна пра гэта з'яўляецца
што Е з'яўляецца самым папулярным ліст,

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
быў А. І так, колькі біт
ён прапануецца выкарыстоўваць для гэтага?

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
Вось калода карт, і тут
клуб, рыдлёўка, клуб, алмазы, клуб,

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
рэчы з па-за [? Анненберга?], Так што

1027
00:47:57,950 --> 00:48:00,289
вось пяць, якія ўяўляюць
А да Z. І калі я

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
Так што я атрымаў А і В і С. А
Цяпер вось яшчэ студэнт.

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
>> Так адзін спосаб я магу вырашыць гэта, усё
права, заняты, заняты У, З заняты.

1036
00:48:24,380 --> 00:48:28,880
Я збіраюся паставіць яго ў D. Такім чынам, у
Спачатку я ёсць выпадковае імгненны доступ

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
Але калі гэта не А
студэнт Я шукаю,

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 або Z, ці нешта накшталт
што, па меншай меры, вы карыстаецеся прастору.

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
Чаму я не магу проста пайсці
па-за [? Анненберга?],

1054
00:49:14,810 --> 00:49:19,960
як Таноса, іншы вузел, паставіць яго
тут, а затым пакласці, што студэнт тут.

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
Так што вы атрымаеце супер хуткі доступ
вырашыць, дзе ў Хэш вашу каштоўнасць для.

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

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
>> Так што гэта свайго роду дурныя,
выклікалым жарты гадоў таму.

1073
00:50:16,880 --> 00:50:19,590
У CS50 секчы-а-марафон,
калі студэнты праверыць у,

1074
00:50:19,590 --> 00:50:22,040
некаторыя TF або Каліфорнія кожны год
думае, што гэта смешна, мірыцца

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
Т-Р-І-Е, які чамусьці не хапае
для пошуку, але гэта называецца 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
Гэта дрэва з любым колькасцю дзяцей,
але кожны з дзяцей у сінтаксічнага дрэва

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
які затым A, X, W, E, L, L. Гэта
проста структура дадзеных, якая адвольна

1096
00:51:17,665 --> 00:51:19,120
з'яўляецца захаванне імёнаў людзей.

1097
00:51:19,120 --> 00:51:25,720
І Максвел захоўваецца толькі пасля
гэта шлях масіва масіва на масіў.

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
У гэтым структуры дадзеных сінтаксічнага дрэва, калі
мой структура дадзеных мае адзін імя ў ім

1102
00:51:40,530 --> 00:51:43,720
і Я шукаю Максвелла, я
збіраюся знайсці яго даволі хутка.

1103
00:51:43,720 --> 00:51:47,910
Я проста гляджу на М-А-Х-W-E-L-L. Калі
Гэтая структура дадзеных, насупраць,

1104
00:51:47,910 --> 00:51:51,830
Калі N з'яўляецца млн, калі ёсць
мільён імёны ў гэтай структуры дадзеных,

1105
00:51:51,830 --> 00:51:57,100
Максвел яшчэ будзе
выявіць ўжо праз М-А-Х-Ш-Е-Л-Ь

1106
00:51:57,100 --> 00:51:58,090
крокі.

1107
00:51:58,090 --> 00:52:01,276
І David-- Д-А-У-Я-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
Я магу пачаць гледзячы народных
назваць, выкарыстоўваючы колькасць часу, што'S

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
Колькасць часу, якое патрабуецца, каб знайсці мяне
М-А-Х-Ш-Е-Л-Л ў гэтай структуры дадзеных з'яўляецца

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
што сталая часу погляд ўверх.

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
выснову Максвелла збіраецца ўзяць
сапраўды такі ж колькасць сем крокаў

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
Віктарына нуль прыдумляць.

1133
00:53:11,850 --> 00:53:14,600
Больш падрабязна пра тое, што на вэб-сайце Курсу
на працягу бліжэйшых некалькіх дзён.

1134
00:53:14,600 --> 00:53:17,120
Панядзелак lecture-- Гэта свята
тут у Гарвардзе ў панядзелак.

1135
00:53:17,120 --> 00:53:18,850
Гэта не ў Нью-Хейвене,
такім чынам, мы бярэм клас

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 Фарным, які

1140
00:53:26,910 --> 00:53:30,850
быў натхнёны ў мінулым годзе ў суботу
"Думкі" Deep Night Live ў

1141
00:53:30,850 --> 00:53:35,700
Джэк хэнд, які
Зараз варта разабрацца.

1142
00:53:35,700 --> 00:53:38,810
>> ФІЛЬМ: А зараз, "Глыбокая
Думкі "па Daven Фарным.

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
>> Даг: Для таго каб убачыць яго ў дзеянні.

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
>> УПА: Дуг, вы можаце ісці наперад і перазапуск
гэта ўсяго толькі за адну секунду, калі ласка.

1153
00:54:04,860 --> 00:54:08,562
Добра, камеры працуюць, так што
дзеянні кожны раз, калі вы будзеце гатовыя, Дуг, ОК?

1154
00:54:08,562 --> 00:54:11,020
Даг: Добра, так што мы
ёсць тут малокомплектных масіў.

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
І я-так, я-так, я-так,
мы іх зліваюцца.

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
>> УПА: Гэй, гэй, гэй,
выразаць, выразаць, выразаць, выразаць.

1163
00:54:27,109 --> 00:54:30,130
Дуг, ты не можаш проста я-так, я-так,
я-так, ваш шлях праз сартавання зліццём.

1164
00:54:30,130 --> 00:54:31,970
>> Даг: Я толькі што зрабіў.

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
>> УПА: Вы павінны растлумачыць
гэта больш поўна, чым гэта.

1170
00:54:37,800 --> 00:54:39,999
Вось толькі не хапае.

1171
00:54:39,999 --> 00:54:41,790
Даг: Ян, мы не
трэба вярнуцца да аднаго.

1172
00:54:41,790 --> 00:54:42,350
Гэта выдатна.

1173
00:54:42,350 --> 00:54:45,690
Так ці інакш, калі мы будзем працягваць з merge--
Ян, мы знаходзімся ў сярэдзіне здымак.

1174
00:54:45,690 --> 00:54:46,612
>> УПА: Я ведаю.

1175
00:54:46,612 --> 00:54:49,320
І мы не можам проста я-так, я-так,
я-так, праз увесь працэс.

1176
00:54:49,320 --> 00:54:52,200
Вы павінны растлумачыць, як
Боку зліваюцца разам.

1177
00:54:52,200 --> 00:54:53,570
>> Даг: Але мы ўжо
патлумачыў, як два sides--

1178
00:54:53,570 --> 00:54:55,321
>> УПА: Вы толькі што паказалі
іх масіў зліцця.

1179
00:54:55,321 --> 00:54:56,486
Даг: Яны ведаюць працэс.

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
>> УПА: Вы толькі што прапусціў прама над ёй.

1183
00:55:00,330 --> 00:55:03,360
Мы вяртаемся да аднаго, вы
вы не можаце я-так, я-так над ім.

1184
00:55:03,360 --> 00:55:05,480
Добра, да аднаго.

1185
00:55:05,480 --> 00:55:07,833
>> Даг: Я павінен вярнуцца
праз усе слайды?

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
>> УПА: Добра.

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
Дзеянне.