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

2
00:00:10,900 --> 00:00:15,860
>> SIARADWR 1: pob hawl, felly mae hyn yn
CS50 Dyma ddiwedd yr wythnos pump.

3
00:00:15,860 --> 00:00:19,220
Ac yn dwyn i gof bod tro diwethaf i ni
dechrau edrych ar y data fancier

4
00:00:19,220 --> 00:00:22,310
strwythurau a ddechreuodd i ddatrys
problemau, a ddechreuodd i gyflwyno

5
00:00:22,310 --> 00:00:25,640
problemau newydd, ond yr allwedd i hyn
Roedd y math o edafu yr ydym

6
00:00:25,640 --> 00:00:27,940
dechrau gwneud o nod i nod.

7
00:00:27,940 --> 00:00:30,085
Felly, mae hyn wrth gwrs yw
rhestr cysylltiedig yn unigol.

8
00:00:30,085 --> 00:00:31,960
Ac erbyn cysylltiedig yn unigol,
Yr wyf yn golygu nid dim ond un

9
00:00:31,960 --> 00:00:33,380
edau rhwng pob un o'r nodau hynny.

10
00:00:33,380 --> 00:00:35,890
Troi allan y gallwch ei wneud ffansi
pethau fel rhestrau cysylltiedig ddwbl

11
00:00:35,890 --> 00:00:38,470
lle mae gennych saeth
mynd i'r ddau gyfeiriad, a oedd yn

12
00:00:38,470 --> 00:00:40,320
Gall helpu gyda rhai arbedion effeithlonrwydd.

13
00:00:40,320 --> 00:00:42,000
Ond mae hyn yn datrys y broblem?

14
00:00:42,000 --> 00:00:43,500
Pa broblem oedd hyn yn datrys?

15
00:00:43,500 --> 00:00:46,620
Pam oeddem yn gofalu ar ddydd Llun?

16
00:00:46,620 --> 00:00:49,820
Pam, mewn theori, oedd yr ydym yn gofalu ar ddydd Llun?

17
00:00:49,820 --> 00:00:50,630
Beth mae'n ei wneud?

18
00:00:50,630 --> 00:00:51,950
>> GYNULLEIDFA: Gallwn ddynamig newid maint iddo.

19
00:00:51,950 --> 00:00:53,740
>> SIARADWR 1: Iawn, felly y gallwn
ddeinamig newid maint iddo.

20
00:00:53,740 --> 00:00:54,710
Da iawn y ddau ohonoch.

21
00:00:54,710 --> 00:00:57,560
Felly gallwch ddeinamig newid maint hwn
strwythur data, tra amrywiaeth,

22
00:00:57,560 --> 00:01:00,760
galw i gof, rhaid i chi wybod a
priori faint o le yr ydych am

23
00:01:00,760 --> 00:01:03,870
ac os oes angen ychydig o mwy
gofod, rydych yn fath o allan o lwc.

24
00:01:03,870 --> 00:01:05,560
Mae'n rhaid i chi greu casgliad newydd cyfan.

25
00:01:05,560 --> 00:01:07,893
Rhaid i chi symud eich holl
data o un i'r llall,

26
00:01:07,893 --> 00:01:10,600
yn y pen draw rhad ac am ddim yr hen array
os gallwch, ac yna symud ymlaen.

27
00:01:10,600 --> 00:01:13,891
A dim ond yn teimlo'n gostus iawn ac yn iawn
aneffeithlon, ac yn wir y gall fod.

28
00:01:13,891 --> 00:01:14,890
Ond nid yw hyn i gyd yn dda.

29
00:01:14,890 --> 00:01:18,180
Rydym yn talu pris, beth oedd un
o'r prisiau yn fwy amlwg i ni

30
00:01:18,180 --> 00:01:20,550
dalu drwy ddefnyddio rhestr cysylltiedig?

31
00:01:20,550 --> 00:01:22,825
>> GYNULLEIDFA: Mae'n rhaid i ni ddefnyddio
gofod dwbl ar gyfer pob un.

32
00:01:22,825 --> 00:01:25,200
SIARADWR 1: Yeah, felly mae angen
o leiaf ddwywaith cymaint o le.

33
00:01:25,200 --> 00:01:27,700
A dweud y gwir, yr wyf yn sylweddoli y llun hwn
hyd yn oed ychydig yn gamarweiniol,

34
00:01:27,700 --> 00:01:32,200
oherwydd ar IDE CS50 mewn llawer o modern
cyfrifiaduron, pwyntydd neu gyfeiriad

35
00:01:32,200 --> 00:01:33,700
nad yw mewn gwirionedd pedwar bytes.

36
00:01:33,700 --> 00:01:36,090
Yn aml iawn mae'r rhain
wyth niwrnod bytes, a oedd yn

37
00:01:36,090 --> 00:01:38,530
yn golygu y gwaelod fwyaf
petryal yno mewn gwirionedd

38
00:01:38,530 --> 00:01:40,900
yn fath o ddwywaith yn
fawr fel hyn yr wyf wedi tynnu,

39
00:01:40,900 --> 00:01:44,409
sy'n golygu eich bod yn defnyddio tair gwaith yn fwy
llawer o le ag y gallai fod yn rhaid fel arall.

40
00:01:44,409 --> 00:01:46,700
Nawr ar yr un pryd, rydym yn
dal i siarad bytes, dde?

41
00:01:46,700 --> 00:01:49,140
Nid ydym yn o angenrheidrwydd yn siarad
megabeit neu gigabeit,

42
00:01:49,140 --> 00:01:51,000
oni bai bod y data hyn yn cael strwythurau mawr.

43
00:01:51,000 --> 00:01:54,510
>> Ac felly heddiw rydym yn dechrau ystyried
sut y gallem edrych ar ddata

44
00:01:54,510 --> 00:01:57,310
yn fwy effeithlon os yn
ffaith y data fynd yn fwy.

45
00:01:57,310 --> 00:02:00,360
Ond gadewch i ni geisio canonicalize
y gweithrediadau yn gyntaf

46
00:02:00,360 --> 00:02:02,460
y gallwch ei wneud ar y rhain
mathau o strwythurau data.

47
00:02:02,460 --> 00:02:04,790
Felly rhywbeth fel cysylltiedig
rhestr yn gyffredinol yn cefnogi

48
00:02:04,790 --> 00:02:07,514
gweithrediadau yn hoffi dileu,
mewnosod, a chwilio.

49
00:02:07,514 --> 00:02:08,639
A beth ydw i'n ei olygu wrth hynny?

50
00:02:08,639 --> 00:02:11,222
Mae hynny'n ei olygu yw bod fel arfer,
os yw pobl yn defnyddio rhestr gysylltiedig,

51
00:02:11,222 --> 00:02:14,287
eu bod nhw neu rywun arall wedi gweithredu
swyddogaethau fel dileu, mewnosod,

52
00:02:14,287 --> 00:02:16,120
a chwilio, fel y gallwch
mewn gwirionedd yn gwneud rhywbeth

53
00:02:16,120 --> 00:02:18,030
ddefnyddiol gyda'r strwythur data.

54
00:02:18,030 --> 00:02:20,760
Felly, gadewch i ni edrych cyflym
ar sut y gallem gweithredu

55
00:02:20,760 --> 00:02:24,530
rhyw cod ar gyfer restr cysylltiedig fel a ganlyn.

56
00:02:24,530 --> 00:02:27,885
>> Felly, mae hyn yn unig yw ychydig cod C,
Nid yw hyd yn oed yn rhaglen gyflawn

57
00:02:27,885 --> 00:02:29,260
bod Fi 'n sylweddol yn gyflym chwipio i fyny.

58
00:02:29,260 --> 00:02:32,300
Dyw hi ddim yn ar-lein yn y dosbarthiad
cod, oherwydd ni fydd yn rhedeg mewn gwirionedd.

59
00:02:32,300 --> 00:02:33,790
Ond yn sylwi Rwyf newydd
gyda dywedodd sylw,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, mae rhywbeth
yno, dot dot dot, rhywbeth yno.

61
00:02:36,130 --> 00:02:38,410
A gadewch i ni dim ond yn edrych ar
beth yw'r rhannau llawn sudd yn cael eu.

62
00:02:38,410 --> 00:02:40,790
Felly, ar-lein tri,
dwyn i gof bod hwn bellach

63
00:02:40,790 --> 00:02:45,960
cynigiwyd datgan nod diwethaf
amser, un o wrthrychau hirsgwar hynny.

64
00:02:45,960 --> 00:02:48,790
Mae ganddo int y byddwn yn galw N,
ond y gellid ei alw unrhyw beth,

65
00:02:48,790 --> 00:02:51,920
ac yna yn seren nôd struct elwir nesaf.

66
00:02:51,920 --> 00:02:55,520
A dim ond i fod yn glir, bod ail
llinell, ar-lein chwech, beth yw hynny?

67
00:02:55,520 --> 00:02:57,930
Beth mae'n ei wneud i ni?

68
00:02:57,930 --> 00:03:01,044
Oherwydd ei fod yn sicr yn edrych yn fwy
cryptic na'n newidynnau arferol.

69
00:03:01,044 --> 00:03:02,740
>> GYNULLEIDFA: Mae'n ei gwneud yn symud dros un.

70
00:03:02,740 --> 00:03:04,650
>> SIARADWR 1: Mae'n ei gwneud yn symud dros un.

71
00:03:04,650 --> 00:03:08,580
Ac i fod yn fwy manwl gywir,
bydd yn storio y cyfeiriad

72
00:03:08,580 --> 00:03:11,582
y nôd sydd wedi golygu i fod
semantig nesaf iddo, dde?

73
00:03:11,582 --> 00:03:13,540
Felly, nid yw'n mynd i
o reidrwydd yn symud unrhyw beth.

74
00:03:13,540 --> 00:03:15,290
Dim ond ei fod yn mynd i
storio gwerth, sy'n cael ei

75
00:03:15,290 --> 00:03:17,170
mynd i fod yn y cyfeiriad
o ryw nod arall,

76
00:03:17,170 --> 00:03:20,810
a dyna pam yr ydym wedi dweud struct
seren nôd, y seren sy'n dynodi

77
00:03:20,810 --> 00:03:22,370
pwyntydd neu gyfeiriad.

78
00:03:22,370 --> 00:03:26,390
Iawn, felly nawr os ydych yn cymryd yn ganiataol bod gennym
N hon ar gael i ni, a gadewch i ni

79
00:03:26,390 --> 00:03:29,490
gymryd yn ganiataol bod rhywun arall wedi
mewnosod criw cyfan o gyfanrifau

80
00:03:29,490 --> 00:03:30,400
i mewn i restr cysylltiedig.

81
00:03:30,400 --> 00:03:35,640
A dyna rhestr cysylltiedig yn
yn tynnu sylw at gan ryw adeg

82
00:03:35,640 --> 00:03:39,040
a elwir yn rhestr newidyn sy'n
pasio i mewn yma fel paramedr,

83
00:03:39,040 --> 00:03:43,120
sut ydw i'n mynd ati lein
14 gweithredu chwilio?

84
00:03:43,120 --> 00:03:45,990
Mewn geiriau eraill, os wyf yn gweithredu
swyddogaeth y mae ei bwrpas mewn bywyd

85
00:03:45,990 --> 00:03:48,889
yw i gymryd int ac yna'r
gan ddechrau o restr cysylltiedig,

86
00:03:48,889 --> 00:03:50,430
hynny yw pwyntydd at y rhestr cysylltiedig.

87
00:03:50,430 --> 00:03:52,992
Fel y tro cyntaf, pwy yr wyf yn meddwl David
oedd ein gwirfoddolwyr ar ddydd Llun,

88
00:03:52,992 --> 00:03:54,700
yr oedd yn pwyntio at
y cyfan cysylltiedig rhestr,

89
00:03:54,700 --> 00:03:57,820
'i' fel pe rydym yn pasio
David mewn fel ein dadl yma.

90
00:03:57,820 --> 00:03:59,990
Sut ydym yn mynd ati i croesi y rhestr hon?

91
00:03:59,990 --> 00:04:04,640
Wel, mae'n ymddangos fod hyd yn oed er
awgrymiadau yn gymharol newydd yn awr i ni,

92
00:04:04,640 --> 00:04:07,010
y gallwn wneud hyn yn gymharol
yn ddirwystr.

93
00:04:07,010 --> 00:04:09,500
>> Rydw i'n mynd i fynd yn ei flaen a
ddatgan newidyn dros dro sy'n

94
00:04:09,500 --> 00:04:12,364
drwy gonfensiwn yn unig yn mynd
i gael ei alw pwyntydd, neu PTR,

95
00:04:12,364 --> 00:04:14,030
ond gallech ei alw'n unrhyw beth yr hoffech.

96
00:04:14,030 --> 00:04:16,470
Ac yr wyf i'n mynd i ymgychwyn
i gychwyn y rhestr.

97
00:04:16,470 --> 00:04:20,050
Felly, gallwch chi fath o feddwl am hyn
â mi yr athro y diwrnod o'r blaen,

98
00:04:20,050 --> 00:04:23,580
math o pwyntio at rywun
ymhlith ein pobl fel gwirfoddolwyr.

99
00:04:23,580 --> 00:04:26,470
Felly, rwy'n newidyn dros dro sy'n
dim ond pwyntio at yr un peth

100
00:04:26,470 --> 00:04:31,390
bod ein enwir gyd-ddigwyddiad
Roedd gwirfoddolwr David hefyd yn tynnu sylw at.

101
00:04:31,390 --> 00:04:35,440
Tra pwyntydd yn
Nid null, gan fod galw yn ôl

102
00:04:35,440 --> 00:04:40,350
hynny null rhywfaint o werth sentinel arbennig
y llinell rhwng diwedd y rhestr,

103
00:04:40,350 --> 00:04:44,280
felly er nad i ddim yn pwyntio at y
tir fel ein gwirfoddolwr diwethaf

104
00:04:44,280 --> 00:04:47,190
oedd, gadewch i ni fynd yn ei flaen
ac yn gwneud y canlynol.

105
00:04:47,190 --> 00:04:51,820
Os pointer-- ac yn awr yr wyf yn fath o eisiau
i wneud yr hyn a wnaethom gyda'r myfyriwr

106
00:04:51,820 --> 00:04:57,410
structure-- os pwyntydd dot nesaf
equals-- hytrach, os pwyntydd dot N hafal

107
00:04:57,410 --> 00:05:02,290
hafal newidyn N, mae'r
ddadl bod wedi ei basio i mewn,

108
00:05:02,290 --> 00:05:05,370
yna rwyf eisiau mynd yn ei flaen
a dweud yn dychwelyd yn wir.

109
00:05:05,370 --> 00:05:11,020
Rwyf wedi dod o hyd i'r rhif N tu mewn
un o'r nodau o fy rhestr cysylltiedig.

110
00:05:11,020 --> 00:05:13,500
Ond mae'r dot mwyach
gweithio yn y cyd-destun hwn,

111
00:05:13,500 --> 00:05:17,260
gan fod pwyntydd, PTR, yw
yn wir pwyntydd, cyfeiriad,

112
00:05:17,260 --> 00:05:20,632
o fewn ein gallu rhyfeddol mewn gwirionedd
defnyddio yn olaf ddarn o gystrawen

113
00:05:20,632 --> 00:05:22,590
y math hwnnw o wneuthuriadau
synnwyr greddfol ac mewn gwirionedd

114
00:05:22,590 --> 00:05:27,870
Defnyddiwch saeth yma, sy'n golygu mynd o
y cyfeiriad hwnnw i'r cyfanrif yno yn.

115
00:05:27,870 --> 00:05:30,160
Felly mae'n debyg iawn mewn
ysbryd i weithredwr y dot,

116
00:05:30,160 --> 00:05:33,860
ond gan nad pwyntydd yn pwyntydd
ac nid yn struct ei hun,

117
00:05:33,860 --> 00:05:35,380
rydym yn unig yn defnyddio'r saeth.

118
00:05:35,380 --> 00:05:40,620
>> Felly, os yw'r nôd presennol fy mod i, mae'r
newidyn dros dro, mae'n pwyntio at

119
00:05:40,620 --> 00:05:43,060
nid N, beth ydw i am ei wneud?

120
00:05:43,060 --> 00:05:45,910
Wel, gyda fy gwirfoddolwyr dynol
bod gennym yma y diwrnod o'r blaen,

121
00:05:45,910 --> 00:05:49,710
os nad yw fy dynol cyntaf yw'r un yr wyf yn
eisiau, ac efallai nad yw'r ail dynol yn

122
00:05:49,710 --> 00:05:52,660
yr un yr wyf am, a'r trydydd, yr wyf yn
Mae angen i gadw yn gorfforol i symud.

123
00:05:52,660 --> 00:05:54,690
Fel sut ydw i'n camu trwy restr?

124
00:05:54,690 --> 00:05:57,470
Pan gawsom amrywiaeth, yr ydych
yn unig oedd fel fy mod yn ogystal a mwy.

125
00:05:57,470 --> 00:06:03,660
Ond yn yr achos hwn, mae'n suffices i
gwneud pwyntydd, yn cael, pwyntydd, nesaf.

126
00:06:03,660 --> 00:06:07,580
Mewn geiriau eraill, mae'r cae nesaf
Mae fel yr holl ddwylo chwith

127
00:06:07,580 --> 00:06:10,880
bod ein gwirfoddolwyr dynol ar ddydd Llun
Roedd defnyddio i bwynt ar ryw nod arall.

128
00:06:10,880 --> 00:06:12,890
Y rhai oedd eu cymdogion nesaf.

129
00:06:12,890 --> 00:06:17,060
>> Felly, os wyf am i gamu drwy'r rhestr hon,
Ni allaf ond yn gwneud i mi yn ogystal yn ogystal anymore,

130
00:06:17,060 --> 00:06:20,120
Yn lle hynny rhaid i mi ddweud
I, pwyntydd, yn mynd

131
00:06:20,120 --> 00:06:24,650
i cyfartal beth bynnag y cae nesaf yw,
y cae nesaf yw, y cae nesaf yw,

132
00:06:24,650 --> 00:06:28,350
yn dilyn pob un o'r rhai a adawodd dwylo
a gawsom ar pwyntio llwyfan

133
00:06:28,350 --> 00:06:30,000
i rai gwerthoedd dilynol.

134
00:06:30,000 --> 00:06:32,590
Ac os caf drwy
hynny iteriad cyfan,

135
00:06:32,590 --> 00:06:39,330
ac yn olaf, yr wyf yn taro null peidio â chael
dod o hyd N eto, Fi jyst yn dychwelyd ffug.

136
00:06:39,330 --> 00:06:44,100
Felly unwaith eto, i gyd yr ydym yn ei wneud yma,
yn unol â'r darlun funud yn ôl,

137
00:06:44,100 --> 00:06:47,840
yn dechrau drwy bwyntio ar y
gan ddechrau o'r rhestr yn ôl pob tebyg.

138
00:06:47,840 --> 00:06:50,970
Ac yna yr wyf yn gwirio, yw gwerth
Dwi'n chwilio am gyfartal i naw?

139
00:06:50,970 --> 00:06:52,650
Os felly, yr wyf yn dychwelyd yn wir ac rwy'n ei wneud.

140
00:06:52,650 --> 00:06:56,450
Os nad yw, diweddaru fy llaw,
AKA pwyntydd, i bwynt

141
00:06:56,450 --> 00:06:59,540
yn y lleoliad y saeth nesaf, ac
Yna, lleoliad y saeth nesaf,

142
00:06:59,540 --> 00:07:00,480
a'r nesaf.

143
00:07:00,480 --> 00:07:03,770
Im 'yn syml cerdded trwy amrywiaeth hwn.

144
00:07:03,770 --> 00:07:06,010
>> Felly unwaith eto, sy'n gofalu?

145
00:07:06,010 --> 00:07:07,861
Fel beth yw hyn cynhwysyn amdano?

146
00:07:07,861 --> 00:07:10,360
Wel, yn cofio inni gyflwyno
y syniad o stac, a oedd yn

147
00:07:10,360 --> 00:07:15,400
yn ddata haniaethol teipiwch i'r graddau y mae'n
Nid yw yn beth C, nid ei fod yn beth CS50,

148
00:07:15,400 --> 00:07:19,430
ei fod yn syniad haniaethol, y syniad hwn o
stacio pethau ar ben ei gilydd

149
00:07:19,430 --> 00:07:21,820
y gellir eu rhoi ar waith yn
tusw o wahanol ffyrdd.

150
00:07:21,820 --> 00:07:25,600
Ac un ffordd yr ydym arfaethedig gyda
amrywiaeth, neu gyda rhestr cysylltiedig.

151
00:07:25,600 --> 00:07:29,570
Ac mae'n ymddangos bod canonically, mae
stac yn cefnogi o leiaf ddau gweithrediadau.

152
00:07:29,570 --> 00:07:32,320
A'r geiriau wefr yn gwthio, i
gwthio rhywbeth ar y pentwr,

153
00:07:32,320 --> 00:07:34,770
fel hambwrdd newydd yn y
neuadd fwyta, neu pop,

154
00:07:34,770 --> 00:07:39,000
sy'n golygu cael gwared ar y topmost
hambwrdd o'r pentwr yn yr ystafell fwyta

155
00:07:39,000 --> 00:07:41,500
neuadd, ac yna efallai rhai
gweithrediadau eraill yn ogystal.

156
00:07:41,500 --> 00:07:45,770
Felly, sut y gallem diffinio strwythur
ein bod yn awr yn galw stac?

157
00:07:45,770 --> 00:07:50,020
>> Wel, mae gennym yr holl angenrheidiol
cystrawen ar gael i ni yn C. wyf yn dweud,

158
00:07:50,020 --> 00:07:53,830
roi diffiniad math o fi
mae struct tu mewn pentwr,

159
00:07:53,830 --> 00:07:58,030
Dw i'n mynd i ddweud yn array, o
criw cyfan o rifau ac yna maint.

160
00:07:58,030 --> 00:08:00,930
Felly, mewn geiriau eraill, os ydw i eisiau
gweithredu hyn mewn cod,

161
00:08:00,930 --> 00:08:03,830
gadewch i mi fynd a dim ond math o
tynnu beth mae hyn yn ei ddweud.

162
00:08:03,830 --> 00:08:06,317
Felly, mae hyn yn ei ddweud, yn rhoi i mi
strwythur sy'n got amrywiaeth,

163
00:08:06,317 --> 00:08:09,400
ac nid wyf yn gwybod beth yw capasiti,
mae'n debyg mae rhai gyson fy mod i wedi

164
00:08:09,400 --> 00:08:10,858
ddiffinnir mewn mannau eraill, ac mae hynny'n iawn.

165
00:08:10,858 --> 00:08:15,260
Ond mae'n debyg mai dim ond un,
dau, tri, pedwar, pump.

166
00:08:15,260 --> 00:08:16,700
Felly gallu yn 5.

167
00:08:16,700 --> 00:08:21,730
Mae'r elfen hon tu mewn fy
Bydd y strwythur yn cael eu galw rhifau.

168
00:08:21,730 --> 00:08:24,020
Ac yna angen un i mi
newidyn arall yn ôl pob golwg

169
00:08:24,020 --> 00:08:27,814
Gelwir maint y lle cyntaf i ddim yn mynd
i bennu ei initialized i sero.

170
00:08:27,814 --> 00:08:29,730
Os does dim byd yn
y pentwr, maint yn sero,

171
00:08:29,730 --> 00:08:31,420
ac mae'n gwerthoedd garbage mewn niferoedd.

172
00:08:31,420 --> 00:08:33,450
Nid oes gennyf unrhyw syniad beth sydd yno eto.

173
00:08:33,450 --> 00:08:36,059
>> Felly, os ydw i eisiau i wthio
rhywbeth ar y pentwr,

174
00:08:36,059 --> 00:08:40,780
Mae'n debyg imi alw ar y gwthio swyddogaeth, ac
Rwy'n dweud gwthio 50, fel y rhif 50,

175
00:08:40,780 --> 00:08:44,090
lle y byddech yn cynnig
Tynnaf mewn amrywiaeth hon?

176
00:08:44,090 --> 00:08:47,124
Mae pum atebion gwahanol posibl.

177
00:08:47,124 --> 00:08:48,790
Ble ydych chi eisiau gwthio'r rhif 50?

178
00:08:48,790 --> 00:08:51,899
Os bydd y nod yma, unwaith eto, ffoniwch y
gwthio swyddogaeth, pasio mewn dadl

179
00:08:51,899 --> 00:08:52,940
50, lle ydw i'n ei roi?

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

181
00:08:55,680 --> 00:08:59,052
Pum possible-- 20% siawns
o ddyfalu'n gywir.

182
00:08:59,052 --> 00:08:59,896
Do?

183
00:08:59,896 --> 00:09:00,740
>> GYNULLEIDFA: Dde pellaf.

184
00:09:00,740 --> 00:09:01,990
>> SIARADWR 1: Dde pellaf.

185
00:09:01,990 --> 00:09:08,359
Erbyn hyn 25% o siawns
o ddyfalu'n gywir.

186
00:09:08,359 --> 00:09:09,650
Felly byddai mewn gwirionedd yn iawn.

187
00:09:09,650 --> 00:09:12,770
Trwy gonfensiwn, byddaf yn dweud gydag amrywiaeth,
byddem yn gyffredinol yn dechrau ar y chwith,

188
00:09:12,770 --> 00:09:14,519
ond gallem yn sicr
yn dechrau ar y dde.

189
00:09:14,519 --> 00:09:17,478
Felly byddai'r spoiler yma fod rwy'n
yn ôl pob tebyg yn mynd i dynnu ei ar y chwith,

190
00:09:17,478 --> 00:09:20,060
yn union fel mewn amrywiaeth arferol lle
Yr wyf yn dechrau mynd i'r chwith i'r dde.

191
00:09:20,060 --> 00:09:21,780
Ond os gallwch troi
y rhifyddeg, dirwy.

192
00:09:21,780 --> 00:09:23,060
Nid dim ond confensiynol.

193
00:09:23,060 --> 00:09:24,880
OK, mae angen i mi wneud un
mwy o newid er.

194
00:09:24,880 --> 00:09:27,710
Nawr fy mod i wedi gwthio rhywbeth
ar y pentwr, beth nesaf?

195
00:09:27,710 --> 00:09:29,400
>> Mae pob hawl, rhaid i mi gynyddiad y maint.

196
00:09:29,400 --> 00:09:32,600
Felly gadewch i mi fynd yn ei flaen a dim ond
diweddaru'r hwn, a oedd sero.

197
00:09:32,600 --> 00:09:35,950
Ac yn lle nawr, dw i'n mynd
i'w roi yn y gwerth un.

198
00:09:35,950 --> 00:09:39,460
Ac yn awr yr wyf yn debyg gwthio arall
rhif ar y simnai, fel 51.

199
00:09:39,460 --> 00:09:42,680
Wel, rhaid i mi wneud un yn fwy
newid, sef hyd at faint dau.

200
00:09:42,680 --> 00:09:46,100
Ac yna mae'n debyg fy mod yn gwthio un yn fwy
rhif ar y stac fel 61,

201
00:09:46,100 --> 00:09:52,530
yn awr mae angen i mi ddiweddaru'r maint un yn fwy
amser, a chael y gwerth 3 gan fod maint.

202
00:09:52,530 --> 00:09:54,690
Ac yn awr mae'n debyg wyf yn galw pop.

203
00:09:54,690 --> 00:09:57,250
Nawr pop, gan gonfensiwn,
nid yw'n cymryd dadl.

204
00:09:57,250 --> 00:10:00,430
Gyda pentwr, y cyfan
bwynt y trosiad hambwrdd

205
00:10:00,430 --> 00:10:03,450
yw nad oes gennych hawl
i fynd gael y hambwrdd, gall pob chi ei wneud

206
00:10:03,450 --> 00:10:06,330
yn pop y un topmost o
y pentwr, dim ond oherwydd.

207
00:10:06,330 --> 00:10:08,010
Dyna beth mae hyn yn strwythur data yn ei wneud.

208
00:10:08,010 --> 00:10:12,250
>> Felly, gan y rhesymeg os byddaf
dweud pop, beth sy'n dod i ffwrdd?

209
00:10:12,250 --> 00:10:13,080
Felly 61.

210
00:10:13,080 --> 00:10:15,402
Felly beth mewn gwirionedd yw y cyfrifiadur
mynd i'w wneud yn y cof?

211
00:10:15,402 --> 00:10:16,610
Beth sydd gan fy cod i wneud?

212
00:10:16,610 --> 00:10:20,330
Beth fyddech chi'n ei gynnig
rydym yn newid ar y sgrin?

213
00:10:20,330 --> 00:10:23,410
Beth ddylai newid?

214
00:10:23,410 --> 00:10:24,960
Mae'n ddrwg gennym?

215
00:10:24,960 --> 00:10:26,334
Felly, rydym yn cael gwared o 61.

216
00:10:26,334 --> 00:10:27,500
Fel y gallaf bendant yn gwneud hynny.

217
00:10:27,500 --> 00:10:28,640
A allaf gael gwared ar 61.

218
00:10:28,640 --> 00:10:30,980
Ac yna beth arall
Mae angen newid i ddigwydd?

219
00:10:30,980 --> 00:10:33,160
Yn ôl pob tebyg gan faint i fynd yn ôl i ddau.

220
00:10:33,160 --> 00:10:34,210
Ac felly mae hynny'n iawn.

221
00:10:34,210 --> 00:10:36,690
Ond arhoswch funud, maint
funud yn ôl yn dair.

222
00:10:36,690 --> 00:10:38,240
Gadewch i 'jyst gwneud gwiriad bwyll cyflym.

223
00:10:38,240 --> 00:10:41,810
Sut oedd rydym yn gwybod ein bod yn
Yn eisiau i gael gwared o 61?

224
00:10:41,810 --> 00:10:42,760
Oherwydd ein bod yn popping.

225
00:10:42,760 --> 00:10:46,450
Ac felly mae gen i ail maint eiddo.

226
00:10:46,450 --> 00:10:48,470
>> Arhoswch funud, rwy'n
meddwl yn ôl i'r wythnos dau

227
00:10:48,470 --> 00:10:51,660
pan fyddwn yn dechrau siarad am
araeau, lle'r oedd y lleoliad sero,

228
00:10:51,660 --> 00:10:55,920
roedd hyn yn lleoliad un, roedd hyn yn lleoliad
dau, mae hyn yn lleoliad tri, pedwar,

229
00:10:55,920 --> 00:10:58,460
mae'n edrych yn debyg y
berthynas rhwng maint

230
00:10:58,460 --> 00:11:02,780
a'r elfen yr wyf am ei dynnu
o'r amrywiaeth yn ymddangos i ddim ond fod yn beth?

231
00:11:02,780 --> 00:11:05,120
Maint minws un.

232
00:11:05,120 --> 00:11:07,786
Ac felly dyna sut fel bodau dynol
rydym yn gwybod 61 sy'n dod gyntaf.

233
00:11:07,786 --> 00:11:09,160
Sut mae cyfrifiadur yn mynd i wybod?

234
00:11:09,160 --> 00:11:11,701
Pan fydd eich cod, lle rydych yn ôl pob tebyg
am wneud un maint minws,

235
00:11:11,701 --> 00:11:14,950
felly tair llai un yw dau, a bod
yn golygu ein bod yn awyddus i gael gwared o 61.

236
00:11:14,950 --> 00:11:18,000
Ac yna gallwn yn wir diweddaru
maint fel maint hwnnw yn awr

237
00:11:18,000 --> 00:11:20,300
mynd o dri i ddim ond dau.

238
00:11:20,300 --> 00:11:24,520
A dim ond i fod yn bedantig, dw i'n mynd
i gynnig fy mod i'n gwneud hyn, dde?

239
00:11:24,520 --> 00:11:27,660
Rydych yn cynnig reddfol
yn gywir dylwn i gael gwared o 61.

240
00:11:27,660 --> 00:11:30,700
Ond wedi nid wyf yn fath o
fath o gotten gwared o 61?

241
00:11:30,700 --> 00:11:33,790
Rwyf wedi anghofio effeithiol
ei fod mewn gwirionedd yno.

242
00:11:33,790 --> 00:11:37,680
Ac yn meddwl yn ôl i PSET4, os ydych wedi darllen
mae'r erthygl am fforensig, y PDF

243
00:11:37,680 --> 00:11:40,780
ein bod wedi cael chi guys yn darllen, neu os ydych yn
Bydd darllen yr wythnos hon ar gyfer PSET4.

244
00:11:40,780 --> 00:11:44,300
Dwyn i gof bod hyn mewn gwirionedd germane i
yr holl syniad o fforensig cyfrifiadurol.

245
00:11:44,300 --> 00:11:47,820
Beth cyfrifiadur yn gyffredinol yn ei wneud yw
'i jyst yn anghofio lle mae rhywbeth yn,

246
00:11:47,820 --> 00:11:51,300
ond nid yw'n mynd i mewn ac yn hoffi
ceisiwch grafu allan neu gwrthwneud

247
00:11:51,300 --> 00:11:54,560
darnau rhai sydd â seroau a rhai
neu ryw batrwm eraill ar hap

248
00:11:54,560 --> 00:11:56,690
oni bai eich bod chi eich hun yn gwneud hynny yn fwriadol.

249
00:11:56,690 --> 00:11:58,930
Felly eich greddf yn
hawl, gadewch i ni gael gwared o 61.

250
00:11:58,930 --> 00:12:00,650
Ond mewn gwirionedd, nid oes raid i ni trafferthu.

251
00:12:00,650 --> 00:12:04,040
Jyst angen i ni anghofio bod
ei fod yno trwy newid ein maint.

252
00:12:04,040 --> 00:12:05,662
>> Nawr bod yna broblem gyda phentwr hwn.

253
00:12:05,662 --> 00:12:07,620
Os byddaf yn cadw gwthio pethau
ar y pentwr, beth

254
00:12:07,620 --> 00:12:11,167
yn amlwg yn mynd i ddigwydd
mewn dim ond amser eiliadau ychydig?

255
00:12:11,167 --> 00:12:12,500
Rydym yn mynd i redeg allan o le.

256
00:12:12,500 --> 00:12:13,580
A beth ydym yn ei wneud?

257
00:12:13,580 --> 00:12:14,680
Rydym yn fath o sgriwio.

258
00:12:14,680 --> 00:12:19,000
Nid yw hon ar waith yn gadael
ni newid maint y rhesi, gan fod defnyddio

259
00:12:19,000 --> 00:12:21,240
cystrawen hwn, os ydych yn
meddwl yn ôl i'r wythnos dau,

260
00:12:21,240 --> 00:12:23,520
unwaith y byddwch wedi datgan
maint amrywiaeth,

261
00:12:23,520 --> 00:12:26,780
nid ydym wedi gweld eto mecanwaith lle
gallwch newid maint y rhesi.

262
00:12:26,780 --> 00:12:29,020
Ac yn wir nid oes gan y nodwedd C.

263
00:12:29,020 --> 00:12:32,524
Os ydych yn dweud yn rhoi pump i mi
Nths, yn eu galw rhifau,

264
00:12:32,524 --> 00:12:33,940
dyna i gyd ydych chi'n mynd i gael.

265
00:12:33,940 --> 00:12:38,790
Felly, rydym yn ei wneud yn awr fel Lun, gael
y gallu i fynegi ateb

266
00:12:38,790 --> 00:12:42,480
fodd bynnag, mae'n rhaid i ni tweak
y diffiniad o ein pentwr

267
00:12:42,480 --> 00:12:46,840
i beidio â bod rhywfaint o amrywiaeth hard-coded,
ond dim ond i storio cyfeiriad.

268
00:12:46,840 --> 00:12:47,890
>> Yn awr pam?

269
00:12:47,890 --> 00:12:51,690
Nawr rydym yn unig rhaid i ni fod yn gyfforddus gyda
y ffaith bod pan oedd fy rhaglen yn rhedeg,

270
00:12:51,690 --> 00:12:53,730
Yn ôl pob tebyg dwi'n mynd i
rhaid gofyn i'r bobl,

271
00:12:53,730 --> 00:12:55,110
faint o rifau ydych chi am i storio?

272
00:12:55,110 --> 00:12:56,776
Felly mae'r mewnbwn yn gorfod dod o rywle.

273
00:12:56,776 --> 00:12:59,140
Ond ar ôl i mi yn gwybod bod
rhif, yna gallaf jyst

274
00:12:59,140 --> 00:13:02,470
defnyddio'r hyn swyddogaeth i roi
mi darn o gof?

275
00:13:02,470 --> 00:13:03,580
Gallaf ddefnyddio malloc.

276
00:13:03,580 --> 00:13:06,710
A gallaf ddweud unrhyw nifer o
bytes Rwyf am yn ôl ar gyfer Nths hyn.

277
00:13:06,710 --> 00:13:10,910
A'r holl rhaid i mi gadw yn y niferoedd
newidyn yma tu mewn struct hwn

278
00:13:10,910 --> 00:13:13,480
Dylai fod yn beth?

279
00:13:13,480 --> 00:13:18,440
Yr hyn mewn gwirionedd yn mynd i mewn i'r
rhifau yn y senario hwn?

280
00:13:18,440 --> 00:13:21,300
Yeah, pwyntydd i'r cyntaf
beit o fod darn o gof,

281
00:13:21,300 --> 00:13:24,940
neu yn fwy penodol, y cyfeiriad
o'r cyntaf bytes hynny.

282
00:13:24,940 --> 00:13:27,300
Nid yw'n ots os yw'n un
beit neu biliwn bytes,

283
00:13:27,300 --> 00:13:28,890
Fi jyst angen i ofalu am y cyntaf.

284
00:13:28,890 --> 00:13:31,530
Oherwydd hyn y gwarantau malloc a
fy gwarantau system weithredu,

285
00:13:31,530 --> 00:13:34,170
yw bod y darn o gof i mi
ei gael, mae'n mynd i fod yn gyffiniol.

286
00:13:34,170 --> 00:13:35,378
Nid oes yn mynd i fod bylchau.

287
00:13:35,378 --> 00:13:38,576
Felly os dwi wedi gofyn am 50
bytes neu 1,000 o bytes,

288
00:13:38,576 --> 00:13:40,450
maen nhw i gyd yn mynd i fod
gefn wrth gefn wrth gefn.

289
00:13:40,450 --> 00:13:44,500
Ac ar yr amod fy mod yn cofio pa mor fawr, sut
cymaint yr wyf yn gofyn amdano, y cyfan sydd angen i mi ei wybod

290
00:13:44,500 --> 00:13:46,230
yw cyfeiriad cyntaf o'r fath.

291
00:13:46,230 --> 00:13:48,660
>> Felly, yn awr mae gennym y gallu yn y cod.

292
00:13:48,660 --> 00:13:51,280
Er, mae'n mynd i fynd â ni
mwy o amser i ysgrifennu hyn i fyny,

293
00:13:51,280 --> 00:13:55,900
gallem yn awr yn ailddyrannu y cof gan
dim ond storio cyfeiriad gwahanol yno

294
00:13:55,900 --> 00:13:59,060
os ydym am gael mwy neu hyd yn oed
cyfran lai o gof.

295
00:13:59,060 --> 00:14:00,170
Felly dyma i ffwrdd masnach.

296
00:14:00,170 --> 00:14:01,360
Nawr rydym yn cael egni.

297
00:14:01,360 --> 00:14:03,350
Rydym yn dal i gael
contiguousness Rydw i'n hawlio.

298
00:14:03,350 --> 00:14:05,881
Gan y bydd malloc yn rhoi i ni
darn cydgyffwrdd o gof.

299
00:14:05,881 --> 00:14:08,630
Ond mae hyn yn mynd i fod yn boen yn
y gwddf i ni, y rhaglennydd,

300
00:14:08,630 --> 00:14:09,770
i mewn gwirionedd godio i fyny.

301
00:14:09,770 --> 00:14:10,730
'I' jyst mwy o waith.

302
00:14:10,730 --> 00:14:13,930
Mae arnom angen cod debyg i hyn yr wyf yn
curo allan ychydig funudau'n ôl.

303
00:14:13,930 --> 00:14:16,120
Doable iawn, ond mae'n ychwanegu cymhlethdod.

304
00:14:16,120 --> 00:14:19,520
Ac felly amser datblygwr, rhaglennydd
mae amser yn adnodd arall eto

305
00:14:19,520 --> 00:14:22,520
y gallai fod angen i ni ei wario
peth amser i gael nodweddion newydd.

306
00:14:22,520 --> 00:14:24,020
Ac yna, wrth gwrs, mae ciw.

307
00:14:24,020 --> 00:14:26,227
Ni fyddwn yn mynd i mewn i hyn
un mewn cymaint o fanylion.

308
00:14:26,227 --> 00:14:27,560
Ond mae'n debyg iawn o ran ysbryd.

309
00:14:27,560 --> 00:14:31,220
Gallwn i weithredu ciw, ac
ei weithrediadau cyfatebol,

310
00:14:31,220 --> 00:14:35,660
enqueue neu dequeue, fel ychwanegu neu ddileu,
'i' jyst yn ffordd ffansi o ddweud ei fod,

311
00:14:35,660 --> 00:14:38,100
enqueue neu dequeue, fel a ganlyn.

312
00:14:38,100 --> 00:14:41,170
Gallaf roi struct fy hun
hynny eto mae amrywiaeth nifer o,

313
00:14:41,170 --> 00:14:44,000
hynny eto mae gan faint,
ond pam ydw i'n awr mae angen

314
00:14:44,000 --> 00:14:46,940
i gadw golwg ar flaen ciw?

315
00:14:46,940 --> 00:14:50,630
Nid oedd angen i mi ei wybod
flaen fy pentwr.

316
00:14:50,630 --> 00:14:53,570
Wel, os wyf eto am
queue-- gadewch i jyst galed

317
00:14:53,570 --> 00:14:57,870
cod ei fel rhai sydd fel phum
gyfanrifau mewn yma o bosibl.

318
00:14:57,870 --> 00:15:00,940
Felly, mae hyn yn sero, un, dau, tri, pedwar.

319
00:15:00,940 --> 00:15:03,430
Mae hyn yn mynd i fod
Gelwir rhifau eto.

320
00:15:03,430 --> 00:15:06,940
A bydd hyn yn cael eu galw maint.

321
00:15:06,940 --> 00:15:10,056
>> Pam ei fod nid yn ddigonol
i gael faint yn unig?

322
00:15:10,056 --> 00:15:11,680
Wel, gadewch i wthio un niferoedd hynny ar.

323
00:15:11,680 --> 00:15:14,220
Felly, yr wyf pushed-- fy mod enqueued, neu eu gwthio.

324
00:15:14,220 --> 00:15:20,150
Nawr byddaf yn enqueue 50, ac yna
51, ac yna 61, a dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Felly dyna enqueue.

326
00:15:21,070 --> 00:15:23,176
Yr wyf yn enqueued 50, yna 51, yna 61.

327
00:15:23,176 --> 00:15:25,050
Ac mae hynny'n edrych yn union yr un fath
i stac hyd yn hyn,

328
00:15:25,050 --> 00:15:27,190
ac eithrio mae angen i mi wneud un newid.

329
00:15:27,190 --> 00:15:33,680
Mae angen i mi ddiweddaru maint hwn, felly yr wyf yn mynd
o sero i un to 02:58 awr.

330
00:15:33,680 --> 00:15:35,760
Sut mae dequeue?

331
00:15:35,760 --> 00:15:36,890
Beth fydd yn digwydd gyda dequeue?

332
00:15:36,890 --> 00:15:41,950
Pwy ddylai ddod oddi ar y rhestr hon yn gyntaf
os mai dyma'r lein yn y Storfa Apple?

333
00:15:41,950 --> 00:15:42,780
Felly 50.

334
00:15:42,780 --> 00:15:44,700
Felly mae'n fath o anoddach y tro hwn.

335
00:15:44,700 --> 00:15:47,880
Tra tro diwethaf yr oedd yn super
hawdd i ychydig wneud un maint minws,

336
00:15:47,880 --> 00:15:51,440
Rwy'n cael i ddiwedd fy array yn effeithiol
lle mae'r niferoedd yn, mae'n cael gwared 61.

337
00:15:51,440 --> 00:15:52,920
Ond dwi ddim am gael gwared 61.

338
00:15:52,920 --> 00:15:55,030
Rwyf am gymryd 50, sy'n
oedd yno ar 05:00

339
00:15:55,030 --> 00:15:56,790
i linell i fyny ar gyfer y
iPhone neu whatnot newydd.

340
00:15:56,790 --> 00:16:01,200
Ac felly i gael gwared o 50, yr wyf yn
Ni all dim ond gwneud hyn, dde?

341
00:16:01,200 --> 00:16:02,547
Gallaf groesi allan 50.

342
00:16:02,547 --> 00:16:04,380
Ond rydym newydd ei ddweud ein bod
Nid oes rhaid i fod mor rhefrol

343
00:16:04,380 --> 00:16:06,330
ag i grafu allan neu'n cuddio y data.

344
00:16:06,330 --> 00:16:08,090
Allwn anghofio lle y mae.

345
00:16:08,090 --> 00:16:12,330
>> Ond os byddaf yn newid fy maint yn awr i
dau, a yw hyn yn ddigon o wybodaeth

346
00:16:12,330 --> 00:16:15,711
i wybod beth sy'n digwydd yn fy ciw?

347
00:16:15,711 --> 00:16:16,680
Ddim mewn gwirionedd.

348
00:16:16,680 --> 00:16:19,830
Fel fy maint yw dau, ond
lle mae'r ciw yn dechrau,

349
00:16:19,830 --> 00:16:22,980
yn enwedig os wyf yn dal i gael
yr un niferoedd hynny yn y cof.

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

351
00:16:24,260 --> 00:16:27,090
Felly mae angen i mi gofio
Erbyn hyn lle y tu blaen yn.

352
00:16:27,090 --> 00:16:29,630
Ac felly gan fy mod yn cynnig i fyny
yno, byddwn yn newydd o'r enw

353
00:16:29,630 --> 00:16:33,729
Blaen nfed, y mae eu cychwynnol
Dylai gwerth wedi bod yn beth?

354
00:16:33,729 --> 00:16:35,270
Zero, dim ond y dechrau y rhestr.

355
00:16:35,270 --> 00:16:40,876
Ond yn awr yn ychwanegol at decrementing
maint, rydym yn unig cynyddiad y tu blaen.

356
00:16:40,876 --> 00:16:42,000
Nawr dyma broblem arall.

357
00:16:42,000 --> 00:16:43,030
Felly, unwaith Rwy'n cadw i fynd.

358
00:16:43,030 --> 00:16:47,520
Gadewch i ni dybio hyn yw nifer y
fel 121, 124, ac yna, dammit,

359
00:16:47,520 --> 00:16:48,610
Rwy'n allan o le.

360
00:16:48,610 --> 00:16:50,390
Ond arhoswch funud, dydw i ddim.

361
00:16:50,390 --> 00:16:55,630
Felly, yn y fan hon yn y stori,
Mae'n debyg bod maint yn un, dau,

362
00:16:55,630 --> 00:17:00,370
tri, pedwar, felly mae'n debyg bod y
faint yw pedwar, y tu blaen yn un,

363
00:17:00,370 --> 00:17:01,621
felly 51 yw yn y tu blaen.

364
00:17:01,621 --> 00:17:04,329
Rwyf eisiau rhoi rhif arall yma,
ond, dammit, rwy'n allan o le.

365
00:17:04,329 --> 00:17:06,710
Ond dydw i ddim mewn gwirionedd, dde?

366
00:17:06,710 --> 00:17:11,192
Ble gallwn i roi rhai
gwerth ychwanegol, fel 171?

367
00:17:11,192 --> 00:17:13,400
Yeah, gallwn unig fath o
mynd yn ôl dros yno, dde?

368
00:17:13,400 --> 00:17:18,161
Ac yna linell drwy'r 50, neu
jyst ysgrifennu drosti gyda 171.

369
00:17:18,161 --> 00:17:20,410
Ac os ydych yn meddwl pam
ein niferoedd got mor hap,

370
00:17:20,410 --> 00:17:24,150
mae'r rhain yn cael eu cymryd gan gyfrifiadur yn gyffredin
cyrsiau gwyddoniaeth yn Harvard ar ôl CS50.

371
00:17:24,150 --> 00:17:27,510
Ond yr oedd hynny'n Optimization da,
oherwydd erbyn hyn dydw i ddim yn gwastraffu gofod.

372
00:17:27,510 --> 00:17:30,750
Rhaid i mi gofio
pa mor fawr beth mae hyn yn gyfanswm.

373
00:17:30,750 --> 00:17:31,500
Mae'n bum cyfanswm.

374
00:17:31,500 --> 00:17:33,375
Oherwydd nad wyf am
dechrau trosysgrifo 51.

375
00:17:33,375 --> 00:17:36,260
Felly, yn awr yr wyf yn dal allan o le,
felly yr un broblem ag o'r blaen.

376
00:17:36,260 --> 00:17:39,140
Ond gallwch weld pa mor nawr
yn eich cod, mae'n debyg

377
00:17:39,140 --> 00:17:41,910
rhaid i ysgrifennu ychydig mwy
cymhlethdod i wneud i hynny ddigwydd.

378
00:17:41,910 --> 00:17:44,510
Ac yn wir, pa weithredwr
yn ôl pob tebyg yn gadael i C

379
00:17:44,510 --> 00:17:48,110
rydych hudol yn gwneud hyn mae'r cylchogrwydd?

380
00:17:48,110 --> 00:17:50,160
Yeah gweithredwr modulo,
yr arwydd y cant.

381
00:17:50,160 --> 00:17:53,160
Felly, beth sydd fath o cŵl am ciw,
er ein bod yn cadw tynnu araeau

382
00:17:53,160 --> 00:17:56,520
gan fod y rhain llinellau tebyg syth, os ydych yn
math o feddwl am hyn fel crwm

383
00:17:56,520 --> 00:18:00,341
o gwmpas fel cylch, yna dim ond
reddfol mae'n fath o yn gweithio'n feddyliol

384
00:18:00,341 --> 00:18:01,590
Yr wyf yn meddwl ychydig yn fwy lân.

385
00:18:01,590 --> 00:18:05,190
Byddai'n rhaid i chi dal i weithredu
model hwnnw meddwl mewn cod.

386
00:18:05,190 --> 00:18:07,550
Fel nad yw yn galed,
yn y pen draw, i weithredu,

387
00:18:07,550 --> 00:18:12,430
ond yr ydym yn dal i golli yr size-- hytrach, mae'r
y gallu i newid maint, oni bai ein bod yn gwneud hyn.

388
00:18:12,430 --> 00:18:15,310
>> Mae'n rhaid i ni gael gwared ar y array, rydym yn
ddisodli gydag pwyntydd sengl,

389
00:18:15,310 --> 00:18:20,010
ac yna rhywle yn fy cod gen
a galw yr hyn swyddogaeth i greu mewn gwirionedd

390
00:18:20,010 --> 00:18:23,720
yr amrywiaeth o'r enw rhifau?

391
00:18:23,720 --> 00:18:26,190
Malloc, neu ryw tebyg
swyddogaeth, yn union.

392
00:18:26,190 --> 00:18:30,481
Unrhyw gwestiynau am staciau neu ciwiau.

393
00:18:30,481 --> 00:18:30,980
Yeah?

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

395
00:18:33,657 --> 00:18:34,240
Cwestiwn da.

396
00:18:34,240 --> 00:18:35,830
Pa modulo fyddech chi'n ei ddefnyddio yma.

397
00:18:35,830 --> 00:18:38,520
Felly ar y cyfan, wrth ddefnyddio
mod, byddech yn ei wneud

398
00:18:38,520 --> 00:18:40,620
gyda maint y
strwythur data cyfan.

399
00:18:40,620 --> 00:18:44,120
Felly rhywbeth fel pump neu alluedd, os
mae'n gyson, yn ôl pob tebyg yn cymryd rhan.

400
00:18:44,120 --> 00:18:47,100
Ond dim ond gwneud modulo pump
yn ôl pob tebyg yn ddigonol,

401
00:18:47,100 --> 00:18:51,380
oherwydd mae angen i ni wybod a ydym
cofleidiol yma neu yma neu yma.

402
00:18:51,380 --> 00:18:54,160
Felly, mae'n debyg eich bod hefyd
mynd i eisiau cynnwys

403
00:18:54,160 --> 00:18:57,220
maint y peth, neu
y newidyn blaen hefyd.

404
00:18:57,220 --> 00:19:00,140
Felly dim ond mae hyn yn gymharol
mynegiant rhifyddeg syml,

405
00:19:00,140 --> 00:19:02,000
ond byddai modulo yn y cynhwysyn allweddol.

406
00:19:02,000 --> 00:19:03,330
>> Ffilm mor fyr os mynnwch.

407
00:19:03,330 --> 00:19:05,780
Animeiddiad bod rhai
Folks mewn prifysgol arall

408
00:19:05,780 --> 00:19:08,060
rhoi at ei gilydd yr ydym wedi
haddasu ar gyfer y drafodaeth hon.

409
00:19:08,060 --> 00:19:12,630
Mae'n cynnwys Jack dysgu'r
ffeithiau am giwiau ac ystadegau.

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

411
00:19:19,010 --> 00:19:21,890
>> FFILM: Un tro,
roedd dyn o'r enw Jack.

412
00:19:21,890 --> 00:19:25,330
Pan ddaeth i wneud ffrindiau,
Nid oedd gan Jack ddawn.

413
00:19:25,330 --> 00:19:28,220
Felly aeth Jack i siarad â'r
mwyaf poblogaidd guy ei fod yn gwybod.

414
00:19:28,220 --> 00:19:30,920
Aeth i Lou a gofyn, Beth ddylwn i ei wneud?

415
00:19:30,920 --> 00:19:33,400
Gwelodd Lou fod ei gyfaill
Roedd yn ofidus.

416
00:19:33,400 --> 00:19:36,050
Wel, dechreuodd, dim ond
edrych sut yr ydych yn gwisgo.

417
00:19:36,050 --> 00:19:38,680
Peidiwch â gennych unrhyw ddillad
gyda golwg wahanol?

418
00:19:38,680 --> 00:19:39,660
Ie, meddai Jack.

419
00:19:39,660 --> 00:19:40,840
Yr wyf yn siŵr yn ei wneud.

420
00:19:40,840 --> 00:19:43,320
Dewch i fy nhŷ a
'N annhymerus' yn eu dangos i chi.

421
00:19:43,320 --> 00:19:44,550
Felly hwy a aethant i ffwrdd i Jac.

422
00:19:44,550 --> 00:19:47,520
A Jack Dangosodd Lou y blwch
lle y cadwai ei holl crysau,

423
00:19:47,520 --> 00:19:49,260
ac mae ei pants, a'i sanau.

424
00:19:49,260 --> 00:19:52,290
Dywedodd Lou, yr wyf yn gweld eich bod wedi
eich holl ddillad mewn pentwr.

425
00:19:52,290 --> 00:19:54,870
Pam na wnewch chi wisgo rhai
eraill unwaith mewn dro?

426
00:19:54,870 --> 00:19:58,020
>> Meddai Jack, yn dda, pan oeddwn
cael gwared ar ddillad a sanau,

427
00:19:58,020 --> 00:20:00,780
Yr wyf yn eu golchi ac yn rhoi
nhw i ffwrdd yn y blwch.

428
00:20:00,780 --> 00:20:03,210
Yna daw'r nesaf
bore, ac i fyny yr wyf yn hop.

429
00:20:03,210 --> 00:20:06,380
Rwy'n mynd i'r blwch a chael
fy nillad oddi ar y top.

430
00:20:06,380 --> 00:20:09,070
Lou gwireddu yn gyflym
y broblem gyda Jack.

431
00:20:09,070 --> 00:20:12,080
Cadwodd dillad, cryno ddisgiau,
a llyfrau yn y pentwr.

432
00:20:12,080 --> 00:20:14,420
Pan fydd yn cyrraedd ar gyfer
rhywbeth i'w ddarllen neu i'w wisgo,

433
00:20:14,420 --> 00:20:17,100
byddai'n dewis y llyfr uchaf neu isaf.

434
00:20:17,100 --> 00:20:19,500
Yna, pan gafodd ei wneud, efe a
Byddai ei gywiro yn ôl.

435
00:20:19,500 --> 00:20:21,970
Yn ôl y byddai'n mynd, ar ben y pentwr.

436
00:20:21,970 --> 00:20:24,460
Yr wyf yn gwybod yr ateb,
dywedodd Loud buddugoliaethus.

437
00:20:24,460 --> 00:20:27,090
Mae angen i chi ddysgu sut i
dechrau defnyddio ciw.

438
00:20:27,090 --> 00:20:29,870
Cymerodd Lou dillad Jac a
eu hongian yn y cwpwrdd.

439
00:20:29,870 --> 00:20:32,710
Ac wedi iddo wagio
y bocs, e jyst taflu ef.

440
00:20:32,710 --> 00:20:36,500
>> Yna dywedodd, yn awr Jack, ar ddiwedd y
y dydd, rhowch eich dillad ar y chwith

441
00:20:36,500 --> 00:20:37,990
pan fyddwch yn eu rhoi i ffwrdd.

442
00:20:37,990 --> 00:20:41,300
Yna, bore fory pan fyddwch yn
gweld yr haul, yn cael eich dillad

443
00:20:41,300 --> 00:20:43,440
ar y dde, o ddiwedd y llinell.

444
00:20:43,440 --> 00:20:44,880
Peidiwch â chi'n ei weld? Dywedodd Lou.

445
00:20:44,880 --> 00:20:46,370
Bydd yn mor braf.

446
00:20:46,370 --> 00:20:49,770
Byddwch yn gwisgo popeth unwaith
cyn i chi wisgo rhywbeth ddwywaith.

447
00:20:49,770 --> 00:20:52,670
A gyda phopeth mewn ciwiau
yn ei closet a silff,

448
00:20:52,670 --> 00:20:55,160
Dechreuodd Jack i deimlo'n
hollol sicr o ei hun.

449
00:20:55,160 --> 00:20:59,720
Pob diolch i Lou a
ei ciw gwych.

450
00:20:59,720 --> 00:21:01,220
SIARADWR 1: pob hawl, mae'n annwyl.

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

452
00:21:05,920 --> 00:21:10,080
Felly, beth sydd wedi bod yn mynd yn wirioneddol
ar dan y cwfl yn awr?

453
00:21:10,080 --> 00:21:12,370
Bod gennym awgrymiadau,
bod gennym malloc,

454
00:21:12,370 --> 00:21:15,680
bod gennym y gallu i greu
darnau o gof i ni ein hunain

455
00:21:15,680 --> 00:21:16,344
ddynamig.

456
00:21:16,344 --> 00:21:18,510
Felly, mae hwn yn ddarlun i ni
cipolwg dim ond y diwrnod o'r blaen.

457
00:21:18,510 --> 00:21:21,180
Doedden ni ddim yn trigo
arno, ond y llun yma

458
00:21:21,180 --> 00:21:24,180
Mae bod yn mynd ymlaen o dan
y cwfl am wythnosau nawr.

459
00:21:24,180 --> 00:21:27,050
Ac felly mae hyn yn cynrychioli, dim ond
petryal yr ydym wedi tynnu,

460
00:21:27,050 --> 00:21:28,180
cof eich cyfrifiadur.

461
00:21:28,180 --> 00:21:31,850
Ac efallai eich cyfrifiadur, neu CS50
ID, mae gan gigabyte o gof neu RAM

462
00:21:31,850 --> 00:21:33,050
neu ddau gigabeit neu bedwar.

463
00:21:33,050 --> 00:21:34,450
Nid oes llawer o bwys.

464
00:21:34,450 --> 00:21:37,240
Eich system weithredu
Windows neu Mac OS neu Linux,

465
00:21:37,240 --> 00:21:41,120
ei hanfod yn caniatáu eich rhaglen
i feddwl bod ganddi fynediad

466
00:21:41,120 --> 00:21:42,982
at holl
cof eich cyfrifiadur,

467
00:21:42,982 --> 00:21:45,440
hyd yn oed er efallai y byddwch yn rhedeg
lluosog raglenni ar unwaith.

468
00:21:45,440 --> 00:21:46,990
Felly, mewn gwirionedd, nid yw hynny'n wir yn gweithio.

469
00:21:46,990 --> 00:21:49,448
Ond mae'n fath o rhith
a roddir i bob un o'ch rhaglenni.

470
00:21:49,448 --> 00:21:53,110
Felly, os ydych wedi cael dau gigs o RAM, mae hyn yn
yw sut y gallai'r cyfrifiadur yn meddwl amdano.

471
00:21:53,110 --> 00:21:57,110
>> Nawr gyd-ddigwyddiad, un o'r rhain
pethau, un o'r segmentau hyn o gof,

472
00:21:57,110 --> 00:21:58,350
yn cael ei alw'n pentwr.

473
00:21:58,350 --> 00:22:01,680
Ac yn wir unrhyw adeg
hyd yn hyn mewn cod ysgrifen

474
00:22:01,680 --> 00:22:05,900
eich bod wedi galw yn
swyddogaeth, er enghraifft brif.

475
00:22:05,900 --> 00:22:08,410
Dwyn i gof bod unrhyw bryd rwyf wedi
cof cyfrifiadurol a dynnwyd yn,

476
00:22:08,410 --> 00:22:10,640
Rwyf bob amser yn tynnu fath o
hanner petryal yma

477
00:22:10,640 --> 00:22:12,520
ac nid ydynt yn trafferthu siarad
ynglŷn â'r hyn sydd uchod.

478
00:22:12,520 --> 00:22:15,980
Oherwydd pan fydd prif gelwir, i hawlio
eich bod yn cael sliver hwn o gof

479
00:22:15,980 --> 00:22:16,970
sy'n mynd i lawr fan hyn.

480
00:22:16,970 --> 00:22:20,650
Ac os brif elwir yn swyddogaeth
fel cyfnewid, yn dda cyfnewid yn mynd yma.

481
00:22:20,650 --> 00:22:23,720
Ac mae'n troi allan, dyna
ble mae'n dod i ben i fyny.

482
00:22:23,720 --> 00:22:26,277
Ar rywbeth a elwir pentwr
tu mewn cof eich cyfrifiadur.

483
00:22:26,277 --> 00:22:28,360
Nawr ar ddiwedd y dydd,
mae hyn yn unig yn mynd i'r afael.

484
00:22:28,360 --> 00:22:30,680
Mae fel beit sero,
beit un, beit 2000000000.

485
00:22:30,680 --> 00:22:33,130
Ond os ydych yn meddwl am y peth
gan fod hyn yn gwrthrych petryal,

486
00:22:33,130 --> 00:22:35,130
cyfan yr ydym yn ei wneud pob
amser yr ydym yn galw swyddogaeth yw

487
00:22:35,130 --> 00:22:37,180
haenu tafell newydd o gof.

488
00:22:37,180 --> 00:22:41,700
Rydym yn rhoi cyfran swyddogaeth honno
o'i gof ei hun i weithio gyda nhw.

489
00:22:41,700 --> 00:22:44,490
>> A dwyn i gof yn awr bod hyn yn bwysig.

490
00:22:44,490 --> 00:22:46,400
Oherwydd os ydym yn cael
rhywbeth fel cyfnewid

491
00:22:46,400 --> 00:22:51,610
a dau newidyn lleol fel A a B a
ni newid gwerthoedd hynny o un a dau

492
00:22:51,610 --> 00:22:55,130
i ddau ac un, galw i gof
pan cyfnewid yn dychwelyd,

493
00:22:55,130 --> 00:22:58,330
'i' fel pe bai sleisen hwn
o gof wedi mynd yn unig.

494
00:22:58,330 --> 00:23:00,080
Mewn gwirionedd, mae'n dal i fod
yno fforensig.

495
00:23:00,080 --> 00:23:01,940
A rhywbeth o hyd mewn gwirionedd yno.

496
00:23:01,940 --> 00:23:05,410
Ond yn gysyniadol, mae fel
er ei fod wedi mynd yn llwyr.

497
00:23:05,410 --> 00:23:10,910
Ac felly nid prif yn gwybod unrhyw ran o'r gwaith
a gafodd ei wneud yn y swyddogaeth cyfnewid,

498
00:23:10,910 --> 00:23:14,890
oni bai ei fod yn mynd heibio mewn gwirionedd yn y rhai
dadleuon drwy pwyntydd neu drwy gyfeirio.

499
00:23:14,890 --> 00:23:17,790
Yn awr, yr ateb sylfaenol
i'r broblem honno gyda cyfnewid

500
00:23:17,790 --> 00:23:19,970
yn mynd heibio pethau yn ôl cyfeiriad.

501
00:23:19,970 --> 00:23:23,250
Ond mae'n troi allan, hefyd, beth sydd
bod yn mynd ymlaen uwchben y rhan honno

502
00:23:23,250 --> 00:23:26,330
y petryal i gyd y tro hwn yw
ond eto mae mwy o gof i fyny yno.

503
00:23:26,330 --> 00:23:28,790
A phan fyddwch yn ddynamig
dyrannu cof,

504
00:23:28,790 --> 00:23:32,020
boed y tu mewn o GetString, a oedd yn
rydym wedi bod yn ei wneud ar eich cyfer yn y CS50

505
00:23:32,020 --> 00:23:34,710
llyfrgell, neu os ydych guys
ffoniwch malloc a gofyn

506
00:23:34,710 --> 00:23:37,950
y system weithredu ar gyfer darn o
cof, nid yw'n dod o'r simnai.

507
00:23:37,950 --> 00:23:40,960
Mae'n dod o le arall
er cof am eich cyfrifiadur

508
00:23:40,960 --> 00:23:42,220
sy'n cael ei alw y domen.

509
00:23:42,220 --> 00:23:43,430
Ac nid dyna'r unrhyw wahanol.

510
00:23:43,430 --> 00:23:44,285
Mae yr un RAM.

511
00:23:44,285 --> 00:23:45,160
Mae yr un cof.

512
00:23:45,160 --> 00:23:49,080
Dim ond y RAM sydd ar i fyny
yna yn lle i lawr yma.

513
00:23:49,080 --> 00:23:50,750
>> Ac felly beth yw ystyr hynny?

514
00:23:50,750 --> 00:23:53,650
Wel, os oes gan eich cyfrifiadur
swm cyfyngedig o gof

515
00:23:53,650 --> 00:23:57,450
ac y das yn tyfu i fyny, felly
i siarad, ac mae'r domen, yn ôl

516
00:23:57,450 --> 00:23:59,349
i saeth hwn, yn tyfu i lawr.

517
00:23:59,349 --> 00:24:01,140
Mewn geiriau eraill, mae pob
tro y byddwch yn galw malloc,

518
00:24:01,140 --> 00:24:03,430
eich bod yn cael ei rhoi sleisen
o gof oddi uchod,

519
00:24:03,430 --> 00:24:06,630
yna efallai ychydig yn is, yna ychydig yn
is, bob tro y byddwch yn galw malloc,

520
00:24:06,630 --> 00:24:10,100
y domen, 'i' defnydd,
yn fath o dyfu,

521
00:24:10,100 --> 00:24:11,950
tyfu yn nes ac yn nes at yr hyn?

522
00:24:11,950 --> 00:24:13,382
Mae'r stac.

523
00:24:13,382 --> 00:24:14,840
Felly, mae hyn yn ymddangos yn syniad da?

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

525
00:24:18,420 --> 00:24:22,140
Yr wyf yn golygu, lle nad yw'n wir glir
beth arall y gallwch ei wneud os ydych yn unig

526
00:24:22,140 --> 00:24:23,910
fod â swm cyfyngedig o gof.

527
00:24:23,910 --> 00:24:25,200
Ond mae hyn yn sicr yn ddrwg.

528
00:24:25,200 --> 00:24:27,920
Mae'r ddau saethau bod ar
damwain cwrs am ei gilydd.

529
00:24:27,920 --> 00:24:31,930
>> Ac mae'n troi allan y dyn drwg, Folks sy'n
yn arbennig o dda gyda rhaglennu,

530
00:24:31,930 --> 00:24:36,140
ac yn ceisio hacio i mewn cyfrifiaduron,
Gall fanteisio realiti hwn.

531
00:24:36,140 --> 00:24:38,290
Yn wir, gadewch i ni ystyried
ychydig o snippet.

532
00:24:38,290 --> 00:24:41,350
Felly, mae hyn yn enghraifft gallwch ddarllen
am yn fanylach ar Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Byddwn yn eich cyfeirio at y
erthygl os chwilfrydig.

534
00:24:43,100 --> 00:24:45,650
Ond mae ymosodiad yn gyffredinol
a elwir yn gorlif byffer sy'n

535
00:24:45,650 --> 00:24:49,570
wedi bodoli cyhyd ag y bodau dynol
wedi cael y gallu i drin

536
00:24:49,570 --> 00:24:53,120
gof cyfrifiadur, yn enwedig yn C.
Felly, mae hon yn rhaglen mympwyol iawn,

537
00:24:53,120 --> 00:24:55,130
ond gadewch i ni ei ddarllen o'r gwaelod i fyny.

538
00:24:55,130 --> 00:24:57,650
Main mewn i seren argC torgoch argV.

539
00:24:57,650 --> 00:24:59,830
Felly mae'n rhaglen sy'n cymryd
dadleuon llinell orchymyn.

540
00:24:59,830 --> 00:25:03,620
A'r holl brif yn ôl pob golwg yn galw
swyddogaeth, ei alw'n F am symlrwydd.

541
00:25:03,620 --> 00:25:04,610
Ac mae'n mynd yn yr hyn?

542
00:25:04,610 --> 00:25:05,490
ArgV o un.

543
00:25:05,490 --> 00:25:09,320
Felly mae'n mynd i mewn beth bynnag F
y gair yw bod y defnyddiwr yn teipio

544
00:25:09,320 --> 00:25:11,500
wrth yr anogwr ar ôl y
Enw'r rhaglen o gwbl.

545
00:25:11,500 --> 00:25:15,730
Mae cymaint fel Cesar neu Vigenere, a oedd yn
efallai y byddwch yn cofio ei wneud gyda argV.

546
00:25:15,730 --> 00:25:16,680
>> Felly beth yw F?

547
00:25:16,680 --> 00:25:19,760
F yn cymryd mewn llinyn
fel ei unig ddadl,

548
00:25:19,760 --> 00:25:22,100
AKA yn seren torgoch, yr un
beth, fel llinyn.

549
00:25:22,100 --> 00:25:24,920
Ac fe'i gelwir fympwyol
bar yn yr enghraifft hon.

550
00:25:24,920 --> 00:25:27,710
Ac yna torgoch c 12,
dim ond mewn termau lleyg,

551
00:25:27,710 --> 00:25:31,750
beth yw torgoch c braced 12 wneud i ni?

552
00:25:31,750 --> 00:25:33,440
Beth sy'n ei wneud?

553
00:25:33,440 --> 00:25:36,490
Dyrannu cof, yn benodol
12 bytes am 12 chars.

554
00:25:36,490 --> 00:25:36,990
Yn union.

555
00:25:36,990 --> 00:25:40,000
Ac yna y llinell olaf, droi a
copi, nad ydych yn ôl pob tebyg wedi ei weld.

556
00:25:40,000 --> 00:25:43,360
Dyma gopi llinyn
swyddogaeth y mae ei bwrpas mewn bywyd

557
00:25:43,360 --> 00:25:48,160
yw i gopïo ei ail ddadl
yn ei ddadl gyntaf,

558
00:25:48,160 --> 00:25:51,190
ond dim ond hyd at
nifer penodol o bytes.

559
00:25:51,190 --> 00:25:53,860
Felly mae'r drydedd ddadl yn dweud,
faint o bytes ddylech chi gopïo?

560
00:25:53,860 --> 00:25:56,720
Mae hyd y bar,
beth bynnag y defnyddiwr deipio i mewn.

561
00:25:56,720 --> 00:25:59,320
A chynnwys
bar, hynny llinyn, yn

562
00:25:59,320 --> 00:26:02,330
copïo i mewn i'r cof sylw at ym C.

563
00:26:02,330 --> 00:26:04,060
>> Felly, mae hyn yn ymddangos yn fath o dwp, ac y mae.

564
00:26:04,060 --> 00:26:06,300
Mae'n enghraifft contrived,
ond mae'n gynrychioliadol

565
00:26:06,300 --> 00:26:10,100
o ddosbarth fectorau ymosodiad,
ffordd o ymosod rhaglen.

566
00:26:10,100 --> 00:26:15,050
Mae pob yn iawn ac yn dda os bydd y defnyddiwr
mathau mewn gair dyna 11 o gymeriadau

567
00:26:15,050 --> 00:26:18,040
neu lai, yn ogystal â'r slaes sero.

568
00:26:18,040 --> 00:26:22,830
Beth os bydd y mathau defnyddwyr mewn mwy na
11 neu 12 neu 20 neu 50 cymeriadau?

569
00:26:22,830 --> 00:26:25,090
Beth yw rhaglen hon yn mynd i wneud?

570
00:26:25,090 --> 00:26:29,360
Fai a allai fod yn SEG. Mae'n mynd
i blindly gopïo popeth ym mar fyny

571
00:26:29,360 --> 00:26:31,750
at ei hyd, sydd yn
llythrennol popeth yn bar,

572
00:26:31,750 --> 00:26:36,307
i mewn i'r cyfeiriad bwyntio at C. Ond C
dim ond preemptively roi fel 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Ond does dim gwiriad ychwanegol.

574
00:26:37,640 --> 00:26:38,700
Does dim os bydd amodau.

575
00:26:38,700 --> 00:26:40,580
Does dim gwall gwirio yma.

576
00:26:40,580 --> 00:26:43,270
>> Ac felly yr hyn y mae'r rhaglen hon yn
mynd i'w wneud yn unig blindly

577
00:26:43,270 --> 00:26:45,750
copïo un peth i'r llall.

578
00:26:45,750 --> 00:26:47,880
Ac felly os ydym yn tynnu hyn
fel llun, dyma

579
00:26:47,880 --> 00:26:49,860
dim ond sliver o'r lle cof.

580
00:26:49,860 --> 00:26:53,470
Felly, yn sylwi ar y gwaelod, rydym yn
yn cael y bar newidyn lleol.

581
00:26:53,470 --> 00:26:57,330
Er mwyn i pwyntydd hynny'n mynd i store--
yn hytrach y ddadl lleol sy'n

582
00:26:57,330 --> 00:26:58,672
mynd i storio'r bar llinyn.

583
00:26:58,672 --> 00:27:00,380
Ac yna yn sylwi yn unig
uwch ei ben mewn pentwr,

584
00:27:00,380 --> 00:27:02,505
oherwydd bob tro y byddwch yn gofyn
ar gyfer cof ar y corn,

585
00:27:02,505 --> 00:27:04,310
mae'n mynd ychydig bach
uwch ei ben ar ffurf lluniau,

586
00:27:04,310 --> 00:27:06,270
rhybudd bod gennym 12 o bytes yno.

587
00:27:06,270 --> 00:27:10,690
Yr un chwith uchaf yw C braced sero a
yr un cywir waelod yw C braced 11.

588
00:27:10,690 --> 00:27:12,870
Dyna sut y cyfrifiaduron
mynd i osod allan.

589
00:27:12,870 --> 00:27:18,300
Felly dim ond reddfol, os oes bar wedi mwy
na 12 cymeriadau i gyd, gan gynnwys

590
00:27:18,300 --> 00:27:25,790
y slaes sero, ble mae'r
12 neu y braced C 12 mynd i fynd?

591
00:27:25,790 --> 00:27:28,440
Neu yn hytrach ble mae'r 12fed
cymeriad neu gymeriad 13eg,

592
00:27:28,440 --> 00:27:30,900
cymeriad canfed mynd
i roi diwedd ar i fyny yn y llun?

593
00:27:30,900 --> 00:27:33,400
Yn uwch neu'n is?

594
00:27:33,400 --> 00:27:36,300
>> Iawn, oherwydd hyd yn oed er
y pentwr ei hun yn tyfu i fyny,

595
00:27:36,300 --> 00:27:39,590
unwaith y byddwch wedi rhoi pethau yn
y peth, am resymau dylunio,

596
00:27:39,590 --> 00:27:41,294
rhoi'r cof o'r top i'r gwaelod.

597
00:27:41,294 --> 00:27:44,460
Felly, os oes gennych fwy na 12 bytes,
ydych yn mynd i ddechrau ysgrifennu dros y bar.

598
00:27:44,460 --> 00:27:47,280
Nawr bod 'na nam, ond mae'n
ddim wir yn beth mawr.

599
00:27:47,280 --> 00:27:51,130
Ond mae'n beth mawr, oherwydd mae
mwy o bethau yn mynd ymlaen yn y cof.

600
00:27:51,130 --> 00:27:53,074
Felly dyma sut gallem
rhoi helo, i fod yn glir.

601
00:27:53,074 --> 00:27:54,490
Os byddaf yn teipio yn helo wrth yr anogwr.

602
00:27:54,490 --> 00:27:59,330
Slaes sero H-E-L-L-O, yn dod i ben i fyny o fewn
y rhai 12 bytes, ac rydym yn super ddiogel.

603
00:27:59,330 --> 00:28:00,330
Popeth yn iawn.

604
00:28:00,330 --> 00:28:03,020
Ond os wyf yn teipio rhywbeth
yn hwy, o bosibl ei fod yn

605
00:28:03,020 --> 00:28:05,860
mynd i ymlusgo i'r gofod bar.

606
00:28:05,860 --> 00:28:08,405
Ond yn waeth hyd yn hyn, mae'n troi
allan yr holl amser hwn,

607
00:28:08,405 --> 00:28:11,530
hyd yn oed er nad ydym wedi siarad am
iddo, y das yn cael ei ddefnyddio ar gyfer pethau eraill.

608
00:28:11,530 --> 00:28:13,560
Nid dim ond newidynnau lleol.

609
00:28:13,560 --> 00:28:15,100
>> C yn iaith lefel isel iawn.

610
00:28:15,100 --> 00:28:17,810
Ac mae'n fath o gyfrinachol
defnyddio'r corn hefyd

611
00:28:17,810 --> 00:28:21,260
i'w cofio pan fydd
Gelwir swyddogaeth yn cael, beth

612
00:28:21,260 --> 00:28:26,040
y cyfeiriad yn y swyddogaeth blaenorol,
fel y gall neidio yn ôl at y swyddogaeth honno.

613
00:28:26,040 --> 00:28:29,980
Felly, pan fydd prif alwadau cyfnewid, ymhlith
y pethau gwthio ar y pentwr

614
00:28:29,980 --> 00:28:34,380
nid yn unig yn cyfnewid newidynnau lleol,
neu ei ddadleuon, hefyd gwthio yn gyfrinachol

615
00:28:34,380 --> 00:28:37,510
ar y pentwr a gynrychiolir
gan y dafell coch yma,

616
00:28:37,510 --> 00:28:40,520
yw cyfeiriad brif gorfforol
er cof am eich cyfrifiadur,

617
00:28:40,520 --> 00:28:44,180
felly pan cyfnewid yn cael ei wneud, y cyfrifiadur
yn gwybod yn rhaid i mi fynd yn ôl at brif

618
00:28:44,180 --> 00:28:46,760
a gorffen gweithredu'r prif swyddogaeth.

619
00:28:46,760 --> 00:28:51,960
Felly, mae hyn yn beryglus yn awr, oherwydd os
y mathau defnyddiwr yn dda yn fwy na helo,

620
00:28:51,960 --> 00:28:57,030
fel bod mewnbwn y defnyddiwr yn clobbers
neu overwrites adran honno coch,

621
00:28:57,030 --> 00:28:59,820
rhesymegol os bydd y cyfrifiadur
jyst yn mynd i gymryd yn ganiataol 'n ddall

622
00:28:59,820 --> 00:29:03,830
bod y bytes yn y sleisen coch yn
y cyfeiriad y dylid ei ddychwelyd,

623
00:29:03,830 --> 00:29:09,020
beth os yw'r gwrthwynebwr yn ddigon smart neu
ddigon ffodus i roi dilyniant o bytes

624
00:29:09,020 --> 00:29:13,450
yna sy'n edrych fel cyfeiriad,
ond mae'n y cyfeiriad cod

625
00:29:13,450 --> 00:29:18,730
ei fod ef neu hi am y cyfrifiadur
i weithredu yn lle prif?

626
00:29:18,730 --> 00:29:21,670
>> Mewn geiriau eraill, os yw'r hyn y
defnyddiwr yn teipio wrth yr anogwr,

627
00:29:21,670 --> 00:29:23,850
Nid yn unig yw rhywbeth
fel diniwed helo,

628
00:29:23,850 --> 00:29:28,210
ond mewn gwirionedd cod sy'n cyfateb
i ddileu'r holl ffeiliau defnyddwyr hwn?

629
00:29:28,210 --> 00:29:30,060
Neu e-bostio eu cyfrinair i mi?

630
00:29:30,060 --> 00:29:31,940
Neu ddechrau cofnodi eu
keystrokes, dde?

631
00:29:31,940 --> 00:29:34,920
Mae ffordd, gadewch i ni nodi heddiw,
y gallent deipio i mewn nid yn unig helo

632
00:29:34,920 --> 00:29:36,711
byd neu eu henw,
gallent ei hanfod

633
00:29:36,711 --> 00:29:39,570
pasio mewn cod, zeros a
rhai, bod y cyfrifiadur

634
00:29:39,570 --> 00:29:43,450
camgymeriadau ar gyfer y ddau cod a chyfeiriad.

635
00:29:43,450 --> 00:29:48,950
Felly, er bod hynny braidd yn haniaethol, os bydd y
mathau o ddefnyddwyr yn ddigon cod gwrthwynebus

636
00:29:48,950 --> 00:29:52,330
y byddwn yn cyffredinoli yma fel
A. A yn ymosodiad neu gwrthwynebwyr.

637
00:29:52,330 --> 00:29:53,140
Pethau felly dim ond drwg.

638
00:29:53,140 --> 00:29:55,306
Nid ydym yn poeni am y
rhifau neu y sero neu rai

639
00:29:55,306 --> 00:29:59,470
heddiw, fel y byddwch yn
trosysgrifo yr adran honno coch,

640
00:29:59,470 --> 00:30:01,580
sylwi bod dilyniant o bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C sero wyth sero.

642
00:30:05,020 --> 00:30:08,960
Ac yn awr fel erthygl Wicipedia yma
wedi cynnig, os ydych yn awr mewn gwirionedd yn dechrau

643
00:30:08,960 --> 00:30:12,460
labelu'r bytes yn eich cyfrifiadur
cof, yr hyn y mae'r erthygl Wicipedia yw

644
00:30:12,460 --> 00:30:19,060
cynnig yw bod, beth os y cyfeiriad
o hynny top chwith beit yw 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Mewn geiriau eraill, os bydd y dyn drwg yn
ddigon craff â'i cod

646
00:30:22,200 --> 00:30:26,650
i mewn gwirionedd yn rhoi nifer yma y
yn cyfateb i gyfeiriad y cod

647
00:30:26,650 --> 00:30:29,180
ef neu hi chwistrellu
i mewn i'r cyfrifiadur, byddwch yn

648
00:30:29,180 --> 00:30:31,050
Gall castia y cyfrifiadur
i wneud unrhyw beth.

649
00:30:31,050 --> 00:30:34,140
Cael gwared ffeiliau, e-bostio
pethau, ffroeni eich traffig,

650
00:30:34,140 --> 00:30:36,710
yn llythrennol Gallai unrhyw beth fod yn
chwistrellu i mewn i'r cyfrifiadur.

651
00:30:36,710 --> 00:30:39,220
Ac felly gorlif byffer
ymosodiad yn greiddiol

652
00:30:39,220 --> 00:30:43,530
yn unig yw dwp, dwp
gor-redol amrywiaeth sy'n

653
00:30:43,530 --> 00:30:45,840
Nid oedd gan wirio ei ffiniau.

654
00:30:45,840 --> 00:30:48,850
Ac mae hyn yn beth yw super beryglus
ac ar yr un pryd super pwerus

655
00:30:48,850 --> 00:30:52,560
yn C yw ein bod yn wir oes gennym
mynediad i unrhyw le yn y cof.

656
00:30:52,560 --> 00:30:55,320
Mae i fyny i ni, y rhaglenwyr,
sy'n ysgrifennu y cod gwreiddiol

657
00:30:55,320 --> 00:30:59,330
i wirio hyd darn o unrhyw
araeau yr ydym yn trin.

658
00:30:59,330 --> 00:31:00,750
Felly, er mwyn bod yn glir, beth yw'r atgyweiria?

659
00:31:00,750 --> 00:31:03,190
Os byddwn gofrestr yn ôl at hyn
cod, nid wyf ddylai unig

660
00:31:03,190 --> 00:31:08,000
newid hyd bar, beth
arall ddylwn i fod yn gwirio?

661
00:31:08,000 --> 00:31:10,620
Beth arall ddylwn i fod yn ei wneud i
atal yr ymosodiad hwn yn gyfan gwbl?

662
00:31:10,620 --> 00:31:14,110
Nid wyf am i ddim ond blindly dweud
y dylech gopïo cynifer o bytes

663
00:31:14,110 --> 00:31:16,140
fel y mae hyd y bar.

664
00:31:16,140 --> 00:31:18,910
Rwyf am ei ddweud, copïo fel
mae llawer o bytes fel y mae ym mar

665
00:31:18,910 --> 00:31:24,090
i fyny at y ddyrannwyd
cof, neu 12 maximally.

666
00:31:24,090 --> 00:31:27,450
Felly, mae angen i mi rhyw fath o os yw cyflwr
sy'n gwneud gwiriwch hyd y bar,

667
00:31:27,450 --> 00:31:32,800
ond os yw'n fwy na 12, yr ydym cod unig caled
12 gan fod y pellter mwyaf posibl.

668
00:31:32,800 --> 00:31:35,910
Fel arall y byffer hyn a elwir yn
Gall trawiad ar y gorlif ddigwydd.

669
00:31:35,910 --> 00:31:38,451
Ar waelod y sleidiau hynny,
os ydych yn chwilfrydig i ddarllen mwy

670
00:31:38,451 --> 00:31:41,200
yw'r erthygl gwreiddiol gwirioneddol
os hoffech i gymryd golwg.

671
00:31:41,200 --> 00:31:44,550
>> Ond yn awr, ymhlith y prisiau
dalu yma oedd aneffeithlonrwydd.

672
00:31:44,550 --> 00:31:46,680
Felly yr oedd hynny'n gyflym
edrych lefel isel ar yr hyn

673
00:31:46,680 --> 00:31:49,709
gall problemau godi yn awr ein bod yn
yn cael mynediad i gof cyfrifiadur.

674
00:31:49,709 --> 00:31:51,750
Ond broblem arall yr ydym yn
eisoes yn stumbled ar ddydd Llun

675
00:31:51,750 --> 00:31:53,800
yn unig oedd yr aneffeithlonrwydd
o restr cysylltiedig.

676
00:31:53,800 --> 00:31:56,019
Rydym yn ôl i amser llinol.

677
00:31:56,019 --> 00:31:57,560
Nid ydym bellach yn cael amrywiaeth cyffiniol.

678
00:31:57,560 --> 00:31:58,980
Nid oes gennym fynediad hap.

679
00:31:58,980 --> 00:32:00,710
Ni allwn ddefnyddio nodiant braced sgwâr.

680
00:32:00,710 --> 00:32:04,590
Mae'n rhaid i ni llythrennol i ddefnyddio dolen tra
fel yr un ysgrifennais eiliad yn ôl.

681
00:32:04,590 --> 00:32:09,740
Ond ar ddydd Llun, yr ydym yn honni y gallwn
ymlusgo yn ôl i mewn i'r deyrnas o effeithlonrwydd

682
00:32:09,740 --> 00:32:13,040
cyflawni rhywbeth sy'n
logarithmig efallai, neu gorau hyd yn hyn,

683
00:32:13,040 --> 00:32:16,120
efallai hyd yn oed rhywbeth sy'n
hyn a elwir yn amser cyson.

684
00:32:16,120 --> 00:32:19,840
Felly, sut y gallwn wneud hynny drwy ddefnyddio'r rhain newydd
offer, cyfeiriadau hyn, awgrymiadau hyn,

685
00:32:19,840 --> 00:32:22,210
ac edafu pethau ein hunain?

686
00:32:22,210 --> 00:32:23,960
Wel, mae'n debyg bod
yma, mae'r rhain yn griw

687
00:32:23,960 --> 00:32:27,170
o rifau yr ydym am i storio mewn
strwythur data a chwilio yn effeithlon.

688
00:32:27,170 --> 00:32:30,960
Gallwn gwbl ailddirwyn i wythnos
dau, taflu rhain i amrywiaeth,

689
00:32:30,960 --> 00:32:33,150
a chwilio eu defnyddio chwiliad deuaidd.

690
00:32:33,150 --> 00:32:34,040
Rhannwch a gorchfygu.

691
00:32:34,040 --> 00:32:37,720
Ac yn wir i chi ysgrifennu
chwilio deuaidd yn PSET3,

692
00:32:37,720 --> 00:32:40,100
lle rydych yn rhoi ar waith y rhaglen darganfyddiad.

693
00:32:40,100 --> 00:32:40,890
Ond eich bod yn gwybod beth.

694
00:32:40,890 --> 00:32:45,060
Mae fath o mwy
ffordd glyfar o wneud hyn.

695
00:32:45,060 --> 00:32:47,390
Mae'n ychydig yn fwy
soffistigedig ac mae'n bosibl

696
00:32:47,390 --> 00:32:50,830
yn ein galluogi i weld pam deuaidd
chwilio mor llawer cyflymach.

697
00:32:50,830 --> 00:32:52,980
Yn gyntaf, gadewch i ni gyflwyno
y syniad o goeden.

698
00:32:52,980 --> 00:32:54,730
Pa er bod yn
coed realiti fath o

699
00:32:54,730 --> 00:32:57,730
tyfu fel hyn, ym myd y cyfrifiadur
gwyddoniaeth maent yn fath o yn tyfu i lawr

700
00:32:57,730 --> 00:33:00,830
fel coeden deulu, lle mae gennych
eich teidiau a neiniau neu deidiau a neiniau mawr

701
00:33:00,830 --> 00:33:04,580
neu whatnot ar y brig, y patriarch a
y matriarch y teulu, un yn unig

702
00:33:04,580 --> 00:33:07,930
hyn a elwir yn gwraidd, nod, isod
sydd yn ei blant,

703
00:33:07,930 --> 00:33:11,442
isod sy'n yw ei blant, neu
ei ddisgynyddion yn fwy cyffredinol.

704
00:33:11,442 --> 00:33:13,400
Ac unrhyw un yn hongian oddi ar
waelod y teulu

705
00:33:13,400 --> 00:33:16,070
coed, yn ogystal â bod y
ieuengaf yn y teulu,

706
00:33:16,070 --> 00:33:19,520
Gall hefyd jyst yn gyffredinol
Gelwir ddail y goeden.

707
00:33:19,520 --> 00:33:21,800
>> Felly, mae hyn yn unig yw criw
o eiriau a diffiniadau

708
00:33:21,800 --> 00:33:25,790
am rywbeth o'r enw coeden mewn cyfrifiadur
gwyddoniaeth, yn debyg iawn i coeden deulu.

709
00:33:25,790 --> 00:33:28,770
Ond mae ymgnawdoliadau ffansi
o goed, un ohonynt

710
00:33:28,770 --> 00:33:30,780
gelwir coeden chwiliad deuaidd.

711
00:33:30,780 --> 00:33:34,380
Ac gallwch fath o hudo
ar wahân yr hyn y peth hyn yn ei wneud.

712
00:33:34,380 --> 00:33:37,180
Wel, mae'n deuaidd yn mha ystyr?

713
00:33:37,180 --> 00:33:41,455
O ble mae'r deuaidd yn dod o fan hyn?

714
00:33:41,455 --> 00:33:41,955
Mae'n ddrwg gennym?

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

716
00:33:45,961 --> 00:33:47,210
Nid yw'n gymaint yn naill neu'r llall neu'r.

717
00:33:47,210 --> 00:33:52,000
Mae'n fwy bod pob un o'r nodau Nid oes
mwy na dau o blant, wrth i ni weld yma.

718
00:33:52,000 --> 00:33:54,990
Yn gyffredinol, mae tree-- a
eich rhieni a neiniau a theidiau

719
00:33:54,990 --> 00:33:57,640
gall gael cymaint o blant neu
grandkids fel y maent mewn gwirionedd yn eisiau,

720
00:33:57,640 --> 00:34:00,820
ac felly, er enghraifft, mae gennym dri
plant oddi ar y nod llaw dde,

721
00:34:00,820 --> 00:34:05,480
ond mewn coeden binary, mae nod wedi
sero, un, neu ddau o blant maximally.

722
00:34:05,480 --> 00:34:08,496
A dyna eiddo 'n glws,
oherwydd os caiff ei gapio gan ddau,

723
00:34:08,496 --> 00:34:10,620
rydym yn mynd i fod yn gallu
cael sylfaen log bach dau

724
00:34:10,620 --> 00:34:11,975
camau gweithredu yn digwydd yma yn y pen draw.

725
00:34:11,975 --> 00:34:13,350
Felly mae gennym rywbeth logarithmig.

726
00:34:13,350 --> 00:34:14,558
Ond yn fwy am hynny yn y man.

727
00:34:14,558 --> 00:34:19,810
Chwilio coed yn golygu bod y niferoedd yn
trefnu fel bod y plentyn chwith yn

728
00:34:19,810 --> 00:34:22,429
gwerth yn fwy na'r gwraidd.

729
00:34:22,429 --> 00:34:26,010
Ac mae ei plentyn cywir yn
fwy na'r gwraidd.

730
00:34:26,010 --> 00:34:29,290
Mewn geiriau eraill, os ydych yn cymryd unrhyw un o'r
nodau, y cylchoedd yn y llun,

731
00:34:29,290 --> 00:34:31,840
ac yn edrych ar ei ochr chwith
plentyn a'i phlentyn yn iawn,

732
00:34:31,840 --> 00:34:34,739
dylai'r cyntaf fod yn llai na,
dylai'r ail fod yn fwy na.

733
00:34:34,739 --> 00:34:36,159
Felly sanity yn gwirio 55.

734
00:34:36,159 --> 00:34:37,780
Mae wedi gadael plentyn yn 33.

735
00:34:37,780 --> 00:34:38,620
Mae'n llai na.

736
00:34:38,620 --> 00:34:40,929
55, ei blentyn iawn yn 77.

737
00:34:40,929 --> 00:34:41,783
Mae'n fwy na.

738
00:34:41,783 --> 00:34:43,199
A dyna diffiniad ailadroddus.

739
00:34:43,199 --> 00:34:46,480
Gallem wirio pob un o'r rhai a
nodau ac mae'r un patrwm a fyddai'n dal.

740
00:34:46,480 --> 00:34:49,389
>> Felly beth braf mewn
coeden chwilio deuaidd, yn

741
00:34:49,389 --> 00:34:52,204
bod un, gallwn roi ar waith
gyda struct, yn union fel hyn.

742
00:34:52,204 --> 00:34:54,620
A hyd yn oed er ein bod ni'n taflu
llawer o strwythurau yn eich,

743
00:34:54,620 --> 00:34:56,560
eu bod braidd yn
sythweledol yn awr, gobeithio.

744
00:34:56,560 --> 00:35:00,570
Mae'r gystrawen yn dal i fod yn ddirgel yn sicr,
ond mae'r cynnwys y nod yn hyn

745
00:35:00,570 --> 00:35:02,786
context-- ac rydym yn cadw
defnyddio'r gair nôd,

746
00:35:02,786 --> 00:35:04,910
boed yn petryal
ar y sgrin neu gylch,

747
00:35:04,910 --> 00:35:08,970
'i' dim ond rhai cynhwysydd generig,
yn yr achos hwn o goeden, fel yr un

748
00:35:08,970 --> 00:35:11,780
welsom, mae angen yn gyfanrif
ym mhob un o'r nodau

749
00:35:11,780 --> 00:35:15,460
ac yna mae angen pwyntio dau awgrymiadau yr wyf yn
i'r plentyn chwith a'r plentyn cywir,

750
00:35:15,460 --> 00:35:16,590
yn y drefn honno.

751
00:35:16,590 --> 00:35:20,730
Felly dyna sut gallem
gweithredu hynny mewn struct.

752
00:35:20,730 --> 00:35:22,315
A sut y gallwn roi ar waith yn y cod?

753
00:35:22,315 --> 00:35:26,730
Wel, gadewch i ni yn gyflym
yn edrych ar enghraifft bach hwn.

754
00:35:26,730 --> 00:35:29,820
Dyw hi ddim yn ymarferol, ond rwyf wedi
copïo a gludo y strwythur hwnnw.

755
00:35:29,820 --> 00:35:33,510
Ac os yw fy swyddogaeth i gael deuaidd
Gelwir coeden chwiliad yn chwilio,

756
00:35:33,510 --> 00:35:36,980
ac mae hyn yn cymryd dwy ddadl,
yn gyfanrif N ac pwyntydd

757
00:35:36,980 --> 00:35:41,400
i nod, felly pwyntydd i'r goeden
neu pwyntydd i wraidd coeden,

758
00:35:41,400 --> 00:35:43,482
sut mae mynd ati i chwilio am N?

759
00:35:43,482 --> 00:35:45,440
Wel, yn gyntaf, oherwydd fy mod i'n
delio â chyfeiriadau,

760
00:35:45,440 --> 00:35:46,750
Rydw i'n mynd i wneud gwiriad bwyll.

761
00:35:46,750 --> 00:35:54,279
Os hafal coed hafal null, yn N
yn y goeden hon ai peidio yn y goeden hon?

762
00:35:54,279 --> 00:35:55,070
Ni all fod yn, dde?

763
00:35:55,070 --> 00:35:56,870
Os wyf heibio null,
does dim byd yno.

764
00:35:56,870 --> 00:35:59,230
Wyf yn gallai yn ogystal yn unig
blindly dweud dychwelyd ffug.

765
00:35:59,230 --> 00:36:04,050
Os byddwch yn rhoi dim byd i mi, yr wyf nid yn sicr yn gallu
dod o hyd i unrhyw rif N. Felly beth arall gallai wyf yn

766
00:36:04,050 --> 00:36:04,750
gwiriwch yn awr?

767
00:36:04,750 --> 00:36:12,830
Rydw i'n mynd i ddweud dda arall os N yn
llai na beth bynnag sydd ar y nôd coed

768
00:36:12,830 --> 00:36:16,300
fy mod i wedi bod yn rhoi gwerth N.

769
00:36:16,300 --> 00:36:20,270
Mewn geiriau eraill, os yw'r rhif dwi'n
chwilio am, N, yn llai na 'r nôd

770
00:36:20,270 --> 00:36:21,340
mod i'n edrych ar.

771
00:36:21,340 --> 00:36:23,190
Ac y nôd dwi'n edrych
yn cael ei alw'n coed,

772
00:36:23,190 --> 00:36:26,370
ac yn cofio o'r enghraifft flaenorol
i fynd ar werth mewn pwyntydd,

773
00:36:26,370 --> 00:36:28,310
Rwy'n defnyddio'r nodiant saeth.

774
00:36:28,310 --> 00:36:35,960
Felly os N yn llai na saeth coed
E, yr wyf eisiau mynd chwith gysyniadol.

775
00:36:35,960 --> 00:36:38,590
Sut ydw i'n mynegi chwilio ar ôl?

776
00:36:38,590 --> 00:36:41,560
I fod yn glir, os yw hyn yn
y darlun o dan sylw,

777
00:36:41,560 --> 00:36:44,612
ac rwyf wedi bod yn pasio bod topmost
arrow sy'n pwyntio i lawr.

778
00:36:44,612 --> 00:36:45,570
Dyna fy pwyntydd coed.

779
00:36:45,570 --> 00:36:48,060
Im 'yn pwyntio at wraidd y goeden.

780
00:36:48,060 --> 00:36:52,100
A dwi'n chwilio dyweder, am
rhif 44, fympwyol.

781
00:36:52,100 --> 00:36:55,300
A yw 44 yn llai na neu'n
fwy na 55 amlwg?

782
00:36:55,300 --> 00:36:56,360
Felly mae'n llai na.

783
00:36:56,360 --> 00:36:58,760
Ac felly mae hyn os yw cyflwr yn berthnasol.

784
00:36:58,760 --> 00:37:03,981
Felly gysyniadol, beth ddylwn i ei eisiau
chwilio nesaf os dwi'n chwilio am 44?

785
00:37:03,981 --> 00:37:04,480
Yeah?

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

787
00:37:08,310 --> 00:37:11,100
>> Yn union, yr wyf am
chwilio'r plentyn chwith,

788
00:37:11,100 --> 00:37:12,789
neu'r is-goed chwith y llun.

789
00:37:12,789 --> 00:37:14,830
Ac yn wir, gadewch i mi drwy
y darlun lawr yma

790
00:37:14,830 --> 00:37:17,770
am ddim ond eiliad, gan fod
Ni allaf crafu hyn allan.

791
00:37:17,770 --> 00:37:21,150
Os byddaf yn dechrau yma yn 55, a
Gwn fod y gwerth 44

792
00:37:21,150 --> 00:37:23,180
Rwy'n chwilio am yw
y chwith, mae'n fath

793
00:37:23,180 --> 00:37:26,010
o fel rhwygo y llyfr ffôn yn
hanner neu rhwygo y goeden yn ei hanner.

794
00:37:26,010 --> 00:37:29,660
Mae gennyf i ofalu am mwyach
yr hanner cyfan y goeden.

795
00:37:29,660 --> 00:37:33,270
Ac eto, yn rhyfedd ddigon o ran y
strwythur, y peth hyn dros yma bod

796
00:37:33,270 --> 00:37:36,682
yn dechrau gyda 33, fod ei hun
yn goeden chwiliad deuaidd.

797
00:37:36,682 --> 00:37:39,890
Dywedais y gair ailadroddus blaen oherwydd
yn wir mae hyn yn strwythur data y

798
00:37:39,890 --> 00:37:41,707
trwy ddiffiniad yn ailadroddus.

799
00:37:41,707 --> 00:37:44,540
Efallai y bydd gennych goeden dyna hwn
mawr, ond mae pob un o'i blant

800
00:37:44,540 --> 00:37:46,870
yn cynrychioli coeden dim ond ychydig yn llai.

801
00:37:46,870 --> 00:37:50,910
Yn hytrach na ei fod grandpa
neu nain, erbyn hyn dim ond mom

802
00:37:50,910 --> 00:37:54,300
or-- ni allaf beidio say-- mom
neu dad, byddai hynny'n rhyfedd.

803
00:37:54,300 --> 00:37:59,000
Yn lle hynny mae'r ddau blentyn yno
Byddai bod fel brawd a chwaer.

804
00:37:59,000 --> 00:38:01,120
Mae cenhedlaeth newydd o goeden deulu.

805
00:38:01,120 --> 00:38:02,900
Ond yn strwythurol, mae'n yr un syniad.

806
00:38:02,900 --> 00:38:06,790
Ac mae'n troi allan gen i swyddogaeth
Gallaf chwilio chwiliad deuaidd â hwy

807
00:38:06,790 --> 00:38:07,290
coeden.

808
00:38:07,290 --> 00:38:08,680
Fe'i gelwir chwilio.

809
00:38:08,680 --> 00:38:17,870
Rwy'n chwilio am N yng saeth coed y chwith
arall os N yn fwy na'r gwerth

810
00:38:17,870 --> 00:38:18,870
fy mod ar hyn o bryd.

811
00:38:18,870 --> 00:38:20,800
55 yn y stori funud yn ôl.

812
00:38:20,800 --> 00:38:23,780
Mae gen i swyddogaeth o'r enw
chwilio sy'n gallaf jyst

813
00:38:23,780 --> 00:38:29,660
pasio N hyn a chwilio recursively
yr is-goed a dychwelyd yn unig

814
00:38:29,660 --> 00:38:30,620
beth bynnag yr ateb hwnnw.

815
00:38:30,620 --> 00:38:33,530
Arall gen i achos sylfaenol terfynol yma.

816
00:38:33,530 --> 00:38:35,310
>> Beth yw'r achos terfynol?

817
00:38:35,310 --> 00:38:36,570
Tree naill ai'n null.

818
00:38:36,570 --> 00:38:39,980
Mae gwerth Im 'naill ai yn chwilio amdano yw
yn llai nag yr neu'n fwy na hynny

819
00:38:39,980 --> 00:38:42,610
neu'n hafal iddo.

820
00:38:42,610 --> 00:38:44,750
A gallwn ddweud gyfartal
cyfartal, ond yn rhesymegol mae'n

821
00:38:44,750 --> 00:38:46,500
sy'n cyfateb i ddim ond dweud arall yma.

822
00:38:46,500 --> 00:38:49,150
Felly yn wir yw sut yr wyf yn dod o hyd i rywbeth.

823
00:38:49,150 --> 00:38:51,710
Felly gobeithio y mae hyn yn
hyd yn oed yn enghraifft fwy cymhellol

824
00:38:51,710 --> 00:38:54,900
na'r swyddogaeth sigma dwp
gwnaethom ychydig o ddarlithoedd yn ôl,

825
00:38:54,900 --> 00:38:58,360
lle'r oedd yr un mor hawdd i'w ddefnyddio dolen
i gyfrif hyd holl rifau o un

826
00:38:58,360 --> 00:39:02,390
i N. Yma gyda strwythur data
fod ei hun yn recursively

827
00:39:02,390 --> 00:39:07,050
diffiniedig a thynnu recursively, yn awr rydym
y gallu i fynegi ein hunain

828
00:39:07,050 --> 00:39:09,780
mewn cod sy'n ei hun yn ailadroddus.

829
00:39:09,780 --> 00:39:12,580
Felly, mae hyn yn yr un cod union fan hyn.

830
00:39:12,580 --> 00:39:14,400
>> Felly, pa broblemau eraill y gallwn ddatrys?

831
00:39:14,400 --> 00:39:18,160
Felly cam cyflym i ffwrdd oddi wrth
coed am ddim ond ennyd.

832
00:39:18,160 --> 00:39:20,130
Yma yw, yn dweud, mae'r faner yr Almaen.

833
00:39:20,130 --> 00:39:22,020
Ac mae yn amlwg yn
patrwm i dynnu sylw hwn.

834
00:39:22,020 --> 00:39:23,811
Ac mae llawer o
baneri yn y byd sydd

835
00:39:23,811 --> 00:39:27,560
mor syml â hyn o ran
o'u lliwiau a phatrymau.

836
00:39:27,560 --> 00:39:31,930
Ond mae'n debyg bod hyn yn cael ei storio fel
Gif, neu JPEG, neu bitmap, neu ping,

837
00:39:31,930 --> 00:39:34,240
unrhyw fformat ffeil graffigol
eich bod yn gyfarwydd â hi,

838
00:39:34,240 --> 00:39:36,460
rhai ohonynt rydym yn
chwarae gyda mewn PSET4.

839
00:39:36,460 --> 00:39:41,550
Nid yw hyn yn ymddangos yn werth chweil i storio
picsel du, du picsel, picsel du,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, criw cyfan o
pixels du ar gyfer y scanline cyntaf,

841
00:39:44,790 --> 00:39:47,430
neu res, yna criw cyfan o
yr un fath, yna criw cyfan

842
00:39:47,430 --> 00:39:49,530
o'r un peth, ac yna
criw cyfan o picsel coch,

843
00:39:49,530 --> 00:39:53,020
picsel coch, picsel coch, yna yn ei gyfanrwydd
criw o picsel melyn, melyn, dde?

844
00:39:53,020 --> 00:39:55,050
>> Mae aneffeithlonrwydd o'r fath yma.

845
00:39:55,050 --> 00:39:59,040
Sut byddech chi yn reddfol
cywasgu'r faner yr Almaen

846
00:39:59,040 --> 00:40:01,320
os weithredu fel ffeil?

847
00:40:01,320 --> 00:40:04,940
Fel pa wybodaeth na allwn ni
trafferthu storio ar ddisg er mwyn

848
00:40:04,940 --> 00:40:08,040
i leihau ein maint y ffeil o hoffi
yn megabeit i cilobeit, rhywbeth

849
00:40:08,040 --> 00:40:09,430
llai o faint?

850
00:40:09,430 --> 00:40:13,130
Yr hon yn gorwedd y diswyddo
yma i fod yn glir?

851
00:40:13,130 --> 00:40:13,880
Beth allech chi ei wneud?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Yn union.

855
00:40:21,970 --> 00:40:24,550
Pam na wnewch chi yn hytrach na chofio
y lliw pob picsel darn

856
00:40:24,550 --> 00:40:28,200
yn union fel chi yn ei wneud yn PSET4
gyda'r fformat ffeil didfap,

857
00:40:28,200 --> 00:40:32,060
pam na wnewch chi jyst yn cynrychioli'r
colofn leftmost o picsel, er enghraifft

858
00:40:32,060 --> 00:40:35,370
criw o picsel du, criw
o goch, a bagad o melyn,

859
00:40:35,370 --> 00:40:39,210
ac yna dim ond rhywsut amgodio y
syniad o ailadrodd hwn 100 gwaith

860
00:40:39,210 --> 00:40:41,020
neu ailadrodd hyn 1,000 o weithiau?

861
00:40:41,020 --> 00:40:43,430
Lle 100 neu 1,000 yn
dim ond yn gyfanrif, er mwyn i chi

862
00:40:43,430 --> 00:40:47,290
Gall gael i ffwrdd gyda dim ond un rhif
yn hytrach na gannoedd neu filoedd

863
00:40:47,290 --> 00:40:48,270
picseli o ychwanegol.

864
00:40:48,270 --> 00:40:50,990
Ac yn wir, dyna sut yr ydym
Gallai cywasgu y faner yr Almaen.

865
00:40:50,990 --> 00:40:51,490
A

866
00:40:51,490 --> 00:40:53,470
Nawr beth am y faner Ffrengig?

867
00:40:53,470 --> 00:40:58,930
Ac ychydig rhyw fath o
ymarfer meddyliol, a oedd baner

868
00:40:58,930 --> 00:41:01,040
Gellir cywasgu mwy ar ddisg?

869
00:41:01,040 --> 00:41:05,720
Mae'r faner Almaeneg neu Ffrangeg
baner, os byddwn yn cymryd y dull?

870
00:41:05,720 --> 00:41:08,490
Mae'r faner Almaeneg, oherwydd mae
mwy diswyddo llorweddol.

871
00:41:08,490 --> 00:41:12,190
A thrwy dylunio, mae llawer o ffeiliau graffigol
fformatau ddim wir yn gweithio llinellau fel sgan

872
00:41:12,190 --> 00:41:12,830
yn llorweddol.

873
00:41:12,830 --> 00:41:14,674
Gallent weithio
fertigol, dim ond dynoliaeth

874
00:41:14,674 --> 00:41:17,090
flynyddoedd yn ôl, penderfynodd yr ydym chi helpu
Yn gyffredinol, yn meddwl am bethau rhes

875
00:41:17,090 --> 00:41:18,880
trwy res yn lle golofn drwy golofn.

876
00:41:18,880 --> 00:41:20,820
Felly yn wir, os oeddech yn
i edrych ar y ffeil

877
00:41:20,820 --> 00:41:24,670
maint y faner Almaeneg a Ffrangeg
baner, ar yr amod bod y penderfyniad yn

878
00:41:24,670 --> 00:41:27,530
yr un fath, yr un lled
ac uchder, yr un yma

879
00:41:27,530 --> 00:41:31,580
yma yn mynd i fod yn fwy, oherwydd eich bod
rhaid ailadrodd eich hun dair gwaith.

880
00:41:31,580 --> 00:41:35,570
Rhaid i chi nodi glas, dro ar ôl tro
chi eich hun, gwyn, ailadrodd eich hun, coch,

881
00:41:35,570 --> 00:41:36,740
ailadrodd eich hun.

882
00:41:36,740 --> 00:41:39,000
Ni allwch jyst yn mynd i gyd
y ffordd i'r dde.

883
00:41:39,000 --> 00:41:41,200
Ac wrth fynd heibio, er mwyn gwneud
clirio'r cywasgu

884
00:41:41,200 --> 00:41:43,910
ym mhobman, os yw'r rhain yn
pedwar fframiau o video-- chi

885
00:41:43,910 --> 00:41:45,890
Efallai cofio i ffilm
neu fideo yn gyffredinol

886
00:41:45,890 --> 00:41:47,286
fel 29 neu 30 fframiau yr eiliad.

887
00:41:47,286 --> 00:41:50,410
Mae fel llyfr fflip bach lle rydych yn
ond yn gweld llun, delwedd, delwedd, delwedd,

888
00:41:50,410 --> 00:41:54,410
image dim ond super gyflym felly mae'n edrych yn debyg
mae'r actorion ar y sgrin yn symud.

889
00:41:54,410 --> 00:41:57,130
Dyma wenynen ar
ben tusw o flodau.

890
00:41:57,130 --> 00:41:59,790
Ac er y gallai fod yn fath o
anodd gweld ar yr olwg gyntaf,

891
00:41:59,790 --> 00:42:04,020
yr unig beth sy'n symud yn
y ffilm hon yw'r gwenyn.

892
00:42:04,020 --> 00:42:06,880
>> Yr hyn sy'n fud am storio
'n fideo heb ei gywasgu?

893
00:42:06,880 --> 00:42:11,420
Mae'n fath o wastraff i storio fideo
â phedwar delweddau bron yn union yr un fath a

894
00:42:11,420 --> 00:42:13,670
yn wahanol dim ond i'r graddau lle mae'r gwenyn yn.

895
00:42:13,670 --> 00:42:16,280
Gallwch daflu y rhan fwyaf o
o'r wybodaeth honno

896
00:42:16,280 --> 00:42:20,190
a chofiwch yn unig, er enghraifft,
y ffrâm cyntaf a'r ffrâm olaf,

897
00:42:20,190 --> 00:42:22,180
fframiau allweddol os ydych chi wedi
erioed wedi clywed y gair,

898
00:42:22,180 --> 00:42:24,337
a dim ond storio yn y
canol lle mae'r gwenyn yn.

899
00:42:24,337 --> 00:42:26,170
A does dim rhaid i chi
storio'r holl pinc,

900
00:42:26,170 --> 00:42:28,330
a'r glas, a'r
gwerthoedd gwyrdd hefyd.

901
00:42:28,330 --> 00:42:31,200
Felly, mae hyn yw dim ond dweud bod
cywasgu ym mhobman.

902
00:42:31,200 --> 00:42:34,900
Mae'n dechneg rydym yn aml yn defnyddio
neu eu cymryd yn ganiataol y dyddiau hyn.

903
00:42:34,900 --> 00:42:38,750
>> Ond sut ydych chi'n cywasgu testun?

904
00:42:38,750 --> 00:42:40,450
Sut ydych chi'n mynd ati i gywasgu testun?

905
00:42:40,450 --> 00:42:45,410
Wel, pob un o'r cymeriadau yn
ASCII yn un beit, neu wyth did.

906
00:42:45,410 --> 00:42:47,360
A dyna fath o fud, dde?

907
00:42:47,360 --> 00:42:51,160
Oherwydd eich bod yn ôl pob tebyg deipio A
ac E ac I ac O ac U llawer

908
00:42:51,160 --> 00:42:55,270
yn amlach na fel W neu Q neu Z,
yn dibynnu ar yr iaith y

909
00:42:55,270 --> 00:42:56,610
eich bod yn ysgrifennu yn sicr.

910
00:42:56,610 --> 00:42:59,600
Ac felly pam yr ydym yn defnyddio
wyth did ar gyfer pob llythyren,

911
00:42:59,600 --> 00:43:02,040
gan gynnwys y lleiaf
llythyrau poblogaidd, dde?

912
00:43:02,040 --> 00:43:05,300
Beth am ddefnyddio llai o ddarnau ar gyfer
y llythrennau super poblogaidd,

913
00:43:05,300 --> 00:43:07,760
fel E, y pethau yr ydych yn dyfalu
gyntaf yng Olwyn Ffawd,

914
00:43:07,760 --> 00:43:10,450
ac yn defnyddio mwy o ddarnau ar gyfer
y llythrennau llai poblogaidd?

915
00:43:10,450 --> 00:43:10,950
Pam?

916
00:43:10,950 --> 00:43:13,130
Oherwydd ein bod yn jyst yn mynd i
yn eu defnyddio yn llai aml.

917
00:43:13,130 --> 00:43:15,838
>> Wel, mae'n troi allan bod wedi
ymdrechion i wneud hyn wedi bod.

918
00:43:15,838 --> 00:43:18,630
Ac os ydych yn cofio o radd
ysgol neu ysgol uwchradd, cod Morse.

919
00:43:18,630 --> 00:43:20,400
Mae Cod Morse dotiau
a llinellau toriad a all fod yn

920
00:43:20,400 --> 00:43:24,270
drosglwyddir ar hyd gwifren fel
synau neu signalau o ryw fath.

921
00:43:24,270 --> 00:43:25,930
Ond cod Morse yn super glân.

922
00:43:25,930 --> 00:43:29,010
Mae'n fath o system deuaidd mewn
bod gennych dotiau neu llinellau toriad.

923
00:43:29,010 --> 00:43:30,977
Ond os ydych yn gweld, er enghraifft, dau dotiau.

924
00:43:30,977 --> 00:43:33,810
Neu os ydych yn meddwl yn ôl at y gweithredwr
sy'n mynd fel Canu, Canu, Canu,

925
00:43:33,810 --> 00:43:36,760
Canu, taro ychydig o sbardun
sy'n trawsyrru signal,

926
00:43:36,760 --> 00:43:40,360
os ydych chi, y derbynnydd, yn derbyn dau
dotiau, pa neges yr ydych wedi eu derbyn?

927
00:43:40,360 --> 00:43:43,490
Hollol mympwyol.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Neu beth about-- neu i?

931
00:43:47,500 --> 00:43:49,570
Efallai ei fod yn dim ond dwy hawl E?

932
00:43:49,570 --> 00:43:52,480
Felly mae 'na broblem hon
o decodability gyda Morse

933
00:43:52,480 --> 00:43:54,890
cod, lle oni bai bod y
sawl sy'n anfon y neges yr ydych

934
00:43:54,890 --> 00:43:59,510
mewn gwirionedd yn seibiau er mwyn i chi drefnu o
gweld neu'n clywed y bylchau rhwng llythrennau,

935
00:43:59,510 --> 00:44:02,990
nid yw'n ddigon dim ond i
anfon ffrwd o zeros a rhai,

936
00:44:02,990 --> 00:44:05,610
neu ddotiau a llinellau toriad,
oherwydd mae amwysedd.

937
00:44:05,610 --> 00:44:08,640
E yn un dot, felly os ydych yn
gweld dau dotiau neu glywed dau ddotiau,

938
00:44:08,640 --> 00:44:11,254
efallai ei bod yn ddwy E neu efallai ei fod yn un I.

939
00:44:11,254 --> 00:44:13,670
Felly mae angen system sy'n 'na
ychydig yn fwy clyfar na hynny.

940
00:44:13,670 --> 00:44:16,851
Felly dyn o'r enw Huffman flynyddoedd
yn ôl feddyliodd am yr union hyn.

941
00:44:16,851 --> 00:44:18,600
Felly rydym yn jyst yn mynd
i gymryd cipolwg cyflym

942
00:44:18,600 --> 00:44:20,114
ar sut y coed yn germane i hyn.

943
00:44:20,114 --> 00:44:22,530
Gadewch i ni dybio bod hyn yn rhai
Neges dwp ydych chi am anfon,

944
00:44:22,530 --> 00:44:26,342
cynnwys dim ond A, B, C D's ac E,
ond mae llawer o gael eu diswyddo yma.

945
00:44:26,342 --> 00:44:27,550
Dyw hi ddim yn golygu i fod yn Saesneg.

946
00:44:27,550 --> 00:44:28,341
Dyw hi ddim yn amgryptio.

947
00:44:28,341 --> 00:44:30,540
'I' jyst neges dwp
gyda llawer o ailadrodd.

948
00:44:30,540 --> 00:44:34,010
Felly, os ydych mewn gwirionedd yn cyfrif yr holl
A, B, C, D, ac E, dyma

949
00:44:34,010 --> 00:44:34,890
pa mor aml.

950
00:44:34,890 --> 00:44:37,800
20% o'r llythyrau yn
A, 45% o'r llythyrau

951
00:44:37,800 --> 00:44:39,660
yn E, a thri amleddau eraill.

952
00:44:39,660 --> 00:44:41,960
Rydym yn cyfrif i fyny yno â llaw
a dim ond gwnaeth y mathemateg.

953
00:44:41,960 --> 00:44:44,579
>> Felly, mae'n ymddangos bod
Huffman, beth amser yn ôl,

954
00:44:44,579 --> 00:44:46,620
sylweddoli eich bod, yn gwybod
beth, os byddaf yn dechrau adeiladu

955
00:44:46,620 --> 00:44:51,172
coeden, neu goedwig o goed, os gwnewch,
fel a ganlyn, gallaf wneud y canlynol.

956
00:44:51,172 --> 00:44:53,880
Rydw i'n mynd i roi nod i bob
o'r llythyrau yr wyf yn poeni am

957
00:44:53,880 --> 00:44:55,530
ac yr wyf i'n mynd i storio
tu mewn y nôd

958
00:44:55,530 --> 00:44:58,610
yr amleddau fel pwynt arnawf
gwerth, neu gallech ei ddefnyddio yn N, hefyd,

959
00:44:58,610 --> 00:45:00,210
ond byddwn yn jyst yn defnyddio fflôt yma.

960
00:45:00,210 --> 00:45:03,100
Ac mae'r algorithm sy'n
cynigiodd yw eich bod

961
00:45:03,100 --> 00:45:07,210
cymryd y goedwig hon o nod sengl
coed, coed mor super byr,

962
00:45:07,210 --> 00:45:11,920
a'ch bod yn dechrau eu cysylltu â
grwpiau newydd, rhieni newydd, os mynnwch.

963
00:45:11,920 --> 00:45:16,150
A ydych yn gwneud hyn trwy ddewis y
dau amleddau lleiaf ar y tro.

964
00:45:16,150 --> 00:45:18,110
Felly yr wyf yn cymryd 10% a 10%.

965
00:45:18,110 --> 00:45:19,090
Yr wyf yn creu nod newydd.

966
00:45:19,090 --> 00:45:20,910
Ac yr wyf yn galw y nôd newydd o 20%.

967
00:45:20,910 --> 00:45:22,750
>> Pa ddau nodau wyf yn cyfuno nesaf?

968
00:45:22,750 --> 00:45:23,810
Mae'n ychydig yn amwys.

969
00:45:23,810 --> 00:45:26,643
Felly mae yna rhai achosion cornel i
ystyried, ond i gadw pethau 'n bert,

970
00:45:26,643 --> 00:45:29,300
Rydw i'n mynd i ddewis 20% -
Yr wyf yn awr yn anwybyddu'r plant.

971
00:45:29,300 --> 00:45:33,640
Rydw i'n mynd i ddewis 20% a
15% a thynnu dau ymylon newydd.

972
00:45:33,640 --> 00:45:35,624
Ac yn awr mae dwy nodau
ydw i'n cyfuno rhesymegol?

973
00:45:35,624 --> 00:45:38,540
Anwybyddwch y plant i gyd, yr holl
wyrion, dim ond yn edrych ar y gwreiddiau

974
00:45:38,540 --> 00:45:39,070
yn awr.

975
00:45:39,070 --> 00:45:42,220
Pa ddau nodau ydw i'n clymu at ei gilydd?

976
00:45:42,220 --> 00:45:44,530
Pwynt dau a 0.35.

977
00:45:44,530 --> 00:45:45,890
Felly gadewch i mi dynnu dau ymylon newydd.

978
00:45:45,890 --> 00:45:47,570
Ac yna yr wyf wedi dim ond got un chwith.

979
00:45:47,570 --> 00:45:48,650
Felly dyma coeden.

980
00:45:48,650 --> 00:45:51,160
Ac mae wedi cael ei dynnu yn fwriadol
i edrych yn fath o 'n bert,

981
00:45:51,160 --> 00:45:55,870
ond yn sylwi bod yr ymylon yn cael
hefyd wedi cael eu labelu sero ac un.

982
00:45:55,870 --> 00:45:59,510
Felly pob un o'r ymylon chwith yn sero
fympwyol, ond yn gyson.

983
00:45:59,510 --> 00:46:01,170
Mae pob un o'r ymylon cywir yn rhai.

984
00:46:01,170 --> 00:46:05,070
>> Ac felly yr hyn a gynigir Hoffman yw,
os ydych am i gynrychioli B,

985
00:46:05,070 --> 00:46:10,080
yn hytrach na cynrychioli nifer 66 fel
mae ASCII sydd yn wyth did cyfan,

986
00:46:10,080 --> 00:46:13,360
eich bod yn gwybod beth, storio yn unig
patrwm sero, sero, sero,

987
00:46:13,360 --> 00:46:17,030
sero, oherwydd dyna y llwybr
gan fy goeden, coeden Mr. Huffman yn,

988
00:46:17,030 --> 00:46:18,600
i'r ddeilen oddi wrth y gwraidd.

989
00:46:18,600 --> 00:46:20,970
Os ydych am storio
E, mewn cyferbyniad, peidiwch

990
00:46:20,970 --> 00:46:26,290
anfon wyth did sy'n cynrychioli E.
Yn lle hynny, anfonwch pa batrwm o ddarnau?

991
00:46:26,290 --> 00:46:26,890
Un.

992
00:46:26,890 --> 00:46:30,410
A beth sy'n neis am hyn yw
bod E yw'r llythyr mwyaf poblogaidd,

993
00:46:30,410 --> 00:46:32,340
ac eich bod yn defnyddio'r
Cod byrraf ar ei gyfer.

994
00:46:32,340 --> 00:46:34,090
Y nesaf mwyaf poblogaidd
llythyr edrych fel ei fod

995
00:46:34,090 --> 00:46:37,380
Roedd A. Ac felly faint o ddarnau
oedd yn cynnig defnyddio ar gyfer hynny?

996
00:46:37,380 --> 00:46:38,270
Zero, un.

997
00:46:38,270 --> 00:46:41,060
>> Ac oherwydd ei fod yn rhoi ar waith
fel goeden hon, am y tro

998
00:46:41,060 --> 00:46:43,350
gadewch i mi nodi mae
dim amwysedd fel yn Morse

999
00:46:43,350 --> 00:46:46,090
cod, gan fod pob un o'r
llythyrau ydych yn gofalu am

1000
00:46:46,090 --> 00:46:48,780
ar ddiwedd y ymylon hyn.

1001
00:46:48,780 --> 00:46:50,580
Felly dyna dim ond un
cymhwyso goeden.

1002
00:46:50,580 --> 00:46:52,538
Mae hyn yn yw-- a byddaf yn chwifio
fy llaw ar hyn o sut yr ydych yn

1003
00:46:52,538 --> 00:46:55,570
Gallai gweithredu hyn fel strwythur C.

1004
00:46:55,570 --> 00:46:58,260
Jyst angen i ni gyfuno
symbol, fel torgoch,

1005
00:46:58,260 --> 00:46:59,910
ac amlder yn chwith ac i'r dde.

1006
00:46:59,910 --> 00:47:02,510
Ond gadewch i ni edrych ar ddau
enghreifftiau terfynol eich bod chi helpu

1007
00:47:02,510 --> 00:47:06,070
gael yn eithaf gyfarwydd â ar ôl
cwis sero yn broblem a osodwyd pump.

1008
00:47:06,070 --> 00:47:09,210
>> Felly mae strwythur y data
a elwir yn tabl hash.

1009
00:47:09,210 --> 00:47:12,247
A thabl hash yn fath o
oeri mewn bod ganddo bwcedi.

1010
00:47:12,247 --> 00:47:14,830
Ac Tybiwch mae pedwar bwcedi
yma, dim ond pedwar lle gwag.

1011
00:47:14,830 --> 00:47:20,830
Dyma dec o gardiau, ac yma yn
clwb, rhaw, clwb, diamonds, clybiau,

1012
00:47:20,830 --> 00:47:25,960
diamonds, clwb, diamonds,
clubs-- felly dyma'r hap.

1013
00:47:25,960 --> 00:47:30,330
Calonnau, hearts-- felly rwy'n
bucketizing pob un o'r mewnbynnau yma.

1014
00:47:30,330 --> 00:47:32,430
A anghenion tabl hash
i edrych ar eich mewnbwn,

1015
00:47:32,430 --> 00:47:34,850
ac yna ei roi mewn rhai
gosod yn seiliedig ar yr hyn a welwch.

1016
00:47:34,850 --> 00:47:35,600
Mae'n algorithm.

1017
00:47:35,600 --> 00:47:37,980
Ac yr wyf yn defnyddio super
algorithm gweledol syml.

1018
00:47:37,980 --> 00:47:40,030
Y rhan anoddaf o'r rhain oedd
cofio beth oedd y lluniau oedd.

1019
00:47:40,030 --> 00:47:41,590
Ac yna mae pedwar cyfanswm bethau.

1020
00:47:41,590 --> 00:47:45,440
>> Nawr bod y cyrn yn tyfu, a oedd yn
yn beth dylunio bwriadol yma.

1021
00:47:45,440 --> 00:47:46,540
Ond beth arall a allai i ei wneud?

1022
00:47:46,540 --> 00:47:49,080
Felly, mewn gwirionedd dyma mae gennym
criw o hen lyfrau arholiadau ysgol.

1023
00:47:49,080 --> 00:47:51,240
Tybiwch fod criw o
Enwau myfyrwyr ar yma.

1024
00:47:51,240 --> 00:47:52,570
Dyma dabl hash mwy.

1025
00:47:52,570 --> 00:47:54,867
Yn hytrach na bedwar bwcedi,
Rwyf wedi, gadewch i ni ddweud 26.

1026
00:47:54,867 --> 00:47:57,950
Ac nid oeddem eisiau mynd fenthyg 26
pethau o'r tu allan [? Annenberg?], Felly

1027
00:47:57,950 --> 00:48:00,289
dyma pump sy'n cynrychioli
A drwy Z. Ac os wyf yn

1028
00:48:00,289 --> 00:48:03,580
gweld i fyfyriwr y mae ei enw yn dechrau gyda A,
Rydw i'n mynd i roi ei cwis yno.

1029
00:48:03,580 --> 00:48:08,850
Os bydd rhywun yn dechrau gyda C, dros yno,
A-- mewn gwirionedd, nid oedd am wneud hynny.

1030
00:48:08,850 --> 00:48:10,060
B yn mynd dros yma.

1031
00:48:10,060 --> 00:48:13,390
Felly mae gen i A a B ac C. A
Erbyn hyn dyma myfyriwr A arall.

1032
00:48:13,390 --> 00:48:16,212
Ond os y tabl hash hwn
rhoi ar waith gydag amrywiaeth,

1033
00:48:16,212 --> 00:48:17,920
Im 'yn fath o sgriwio
yn y fan hon, dde?

1034
00:48:17,920 --> 00:48:19,510
Yr wyf yn fath o angen inni roi hyn yn rhywle.

1035
00:48:19,510 --> 00:48:24,380
>> Felly, un ffordd y gallaf ddatrys hyn yw, i gyd
dde, A yn brysur, B yn brysur, C yn brysur.

1036
00:48:24,380 --> 00:48:28,880
Dw i'n mynd i roi iddo yn D. Felly, ar
yn gyntaf, yr wyf yn cael mynediad ar unwaith ar hap

1037
00:48:28,880 --> 00:48:31,064
i bob un o'r bwcedi ar gyfer y myfyrwyr.

1038
00:48:31,064 --> 00:48:33,230
Ond erbyn hyn mae'n fath o ddatganoli
i mewn i rywbeth llinol,

1039
00:48:33,230 --> 00:48:36,750
oherwydd os wyf eisiau chwilio am rywun
enw y mae ei dechrau gyda A, yr wyf yn gwirio yma.

1040
00:48:36,750 --> 00:48:38,854
Ond os nad yw hyn yn A
myfyriwr dwi'n chwilio am,

1041
00:48:38,854 --> 00:48:41,520
Wyf yn fath o yn rhaid i ddechrau wirio
y bwcedi, oherwydd yr hyn a wnaeth i mi

1042
00:48:41,520 --> 00:48:44,530
Roedd fath o llinol
ymchwilio i strwythur data.

1043
00:48:44,530 --> 00:48:47,710
Ffordd dwp o ddweud dim ond yn edrych
ar gyfer yr agoriad cyntaf sydd ar gael,

1044
00:48:47,710 --> 00:48:51,850
a'i roi fel cynllun a B, fel petai,
neu gynllun D yn yr achos hwn, mae'r gwerth

1045
00:48:51,850 --> 00:48:53,340
yn y lleoliad hwnnw yn lle hynny.

1046
00:48:53,340 --> 00:48:56,470
Mae hyn yn unig, felly os oes gennych
got 26 o leoliadau a dim fyfyrwyr

1047
00:48:56,470 --> 00:49:00,600
gydag enw Q neu Z, neu rywbeth tebyg
hynny, o leiaf eich bod yn defnyddio'r gofod.

1048
00:49:00,600 --> 00:49:03,140
>> Ond rydym eisoes wedi gweld mwy
atebion clyfar yma, dde?

1049
00:49:03,140 --> 00:49:04,870
Beth fyddech chi'n ei wneud yn lle hynny
os oes gennych gwrthdrawiad?

1050
00:49:04,870 --> 00:49:06,670
Os oes dau o bobl yn cael
yr enw A, beth fyddai

1051
00:49:06,670 --> 00:49:09,160
wedi bod yn fwy craff neu'n fwy
ateb 'n athrylithgar na dim ond

1052
00:49:09,160 --> 00:49:12,840
rhoi A pan fo D yn dybiedig i fod?

1053
00:49:12,840 --> 00:49:14,810
Pam nad ydw i'n jyst yn mynd
tu allan [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
fel malloc, nod arall, rhowch ef
yma, ac yna ei roi bod i fyfyriwr yma.

1055
00:49:19,960 --> 00:49:22,120
Felly, yr wyf yn y bôn yn cael
rhyw fath o amrywiaeth,

1056
00:49:22,120 --> 00:49:25,590
neu efallai yn fwy cain gan ein bod yn
dechrau gweld rhestr cysylltiedig.

1057
00:49:25,590 --> 00:49:29,520
>> Ac felly tabl hash yn strwythur
a allai edrych yn union fel hyn,

1058
00:49:29,520 --> 00:49:33,900
ond yn fwy glyfar, byddwch yn rhywbeth a elwir
gadwyno ar wahân, lle tabl hash

1059
00:49:33,900 --> 00:49:38,340
yn syml yw amrywiaeth, pob un
y mae ei elfennau na yn rhif,

1060
00:49:38,340 --> 00:49:40,470
yn rhestr cysylltiedig ei hun.

1061
00:49:40,470 --> 00:49:45,080
Felly eich bod yn cael mynediad cyflym super
penderfynu ble i hash eich gwerth i.

1062
00:49:45,080 --> 00:49:48,059
Yn debyg iawn gyda'r enghraifft cardiau,
Yr wyf yn gwneud penderfyniadau super gyflym.

1063
00:49:48,059 --> 00:49:49,600
Hearts goes here, diamonds yn mynd yma.

1064
00:49:49,600 --> 00:49:52,180
Un peth yma, A mynd yma,
D goes here, B mynd yma.

1065
00:49:52,180 --> 00:49:55,740
Felly gyflym super edrych-ups, ac os
ydych yn digwydd i redeg i mewn i achos

1066
00:49:55,740 --> 00:49:59,429
gwrthdrawiadau lle gennych, dau
pobl gyda'r un enw, yn dda yna

1067
00:49:59,429 --> 00:50:00,970
'ch jyst yn dechrau eu cysylltu â'i gilydd.

1068
00:50:00,970 --> 00:50:03,900
Ac efallai eich bod yn cadw eu didoli
yn nhrefn yr wyddor, efallai nad ydych yn ei wneud.

1069
00:50:03,900 --> 00:50:05,900
Ond o leiaf yn awr mae gennym y ddynamiaeth.

1070
00:50:05,900 --> 00:50:10,250
Felly, ar y naill law mae gennym gyflym super
amser cyson, a math o amser llinol

1071
00:50:10,250 --> 00:50:14,110
dan sylw os rhestrau cysylltiedig hyn
dechrau cael ychydig yn hir.

1072
00:50:14,110 --> 00:50:16,880
>> Felly y math hwn o wirion,
flynyddoedd jôc geeky yn ôl.

1073
00:50:16,880 --> 00:50:19,590
Yn y CS50 darnia-a-thon,
pan fydd myfyrwyr yn gwirio i mewn,

1074
00:50:19,590 --> 00:50:22,040
rhyw TF neu CA bob blwyddyn
meddwl ei fod yn ddoniol i roi i fyny

1075
00:50:22,040 --> 00:50:27,772
arwydd fel hyn, lle mae'n jyst
yn golygu os bydd eich enw yn dechrau gyda A,

1076
00:50:27,772 --> 00:50:28,870
mynd y ffordd hon.

1077
00:50:28,870 --> 00:50:31,110
Os yw'ch enw yn dechrau
gyda B, ewch this-- OK,

1078
00:50:31,110 --> 00:50:33,290
mae'n ddoniol efallai yn ddiweddarach yn y semester.

1079
00:50:33,290 --> 00:50:36,420
Ond mae un arall
ffordd o wneud hyn, hefyd.

1080
00:50:36,420 --> 00:50:37,410
Dewch yn ôl at hynny.

1081
00:50:37,410 --> 00:50:38,600
>> Felly mae yna strwythur hwn.

1082
00:50:38,600 --> 00:50:40,420
Ac mae hyn yn ein olaf
strwythur ar gyfer heddiw,

1083
00:50:40,420 --> 00:50:42,400
sy'n rhywbeth a elwir yn trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, sydd, am ryw reswm yn fyr
ar gyfer adfer, ond fe'i gelwir trie.

1085
00:50:47,140 --> 00:50:51,389
Felly mae trie yn ddiddorol arall
amalgam o lawer o syniadau hyn.

1086
00:50:51,389 --> 00:50:52,930
Mae'n goeden, yr ydym wedi gweld o'r blaen.

1087
00:50:52,930 --> 00:50:54,180
Dyw hi ddim yn goeden chwiliad deuaidd.

1088
00:50:54,180 --> 00:50:58,410
Mae'n goeden gydag unrhyw nifer o blant,
ond mae pob un o'r plant mewn trie

1089
00:50:58,410 --> 00:51:00,090
yn arae.

1090
00:51:00,090 --> 00:51:04,790
Amrywiaeth o faint, yn dweud, 26 neu efallai 27
os ydych chi eisiau cefnogi enwau chysylltnod

1091
00:51:04,790 --> 00:51:06,790
neu collnod mewn enwau pobl.

1092
00:51:06,790 --> 00:51:08,280
>> Ac felly mae hwn yn strwythur data.

1093
00:51:08,280 --> 00:51:10,290
Ac os ydych yn edrych o'r top
i'r gwaelod, fel os ydych yn

1094
00:51:10,290 --> 00:51:13,710
edrych ar y nod uchaf yno, M, yn
gan dynnu sylw at y peth leftmost yno,

1095
00:51:13,710 --> 00:51:17,665
sy'n cael ei wedyn yn A, X, C, E, L, L. Mae hyn yn
dim ond strwythur data sy'n fympwyol

1096
00:51:17,665 --> 00:51:19,120
yn storio enwau pobl.

1097
00:51:19,120 --> 00:51:25,720
A Maxwell yn cael ei storio gan dim ond dilyn
llwybr o amrywiaeth i amrywiaeth i amrywiaeth.

1098
00:51:25,720 --> 00:51:30,050
Ond yr hyn sy'n rhyfeddol am trie yn
hynny, tra rhestr cysylltiedig a hyd yn oed

1099
00:51:30,050 --> 00:51:34,520
amrywiaeth, y gorau yr ydym wedi gotten erioed yw
amser llinol neu amser logarithmig chwilio

1100
00:51:34,520 --> 00:51:35,600
rhywun i fyny.

1101
00:51:35,600 --> 00:51:40,530
Yn y strwythur data o trie, os
fy strwythur data wedi un enw ynddo

1102
00:51:40,530 --> 00:51:43,720
ac dwi'n chwilio am Maxwell, rwy'n
mynd i ddod o hyd iddo yn weddol gyflym.

1103
00:51:43,720 --> 00:51:47,910
Fi jyst yn edrych am M-A-X-W-E-L-L. Os
y strwythur data, mewn cyferbyniad,

1104
00:51:47,910 --> 00:51:51,830
os N yw miliwn, os oes
miliwn o enwau yn y strwythur data,

1105
00:51:51,830 --> 00:51:57,100
Maxwell yn dal i fynd i fod yn
discoverable ar ôl dim ond M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
grisiau.

1107
00:51:58,090 --> 00:52:01,276
A grisiau David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Mewn geiriau eraill, trwy adeiladu
strwythur data sy'n

1109
00:52:03,400 --> 00:52:07,240
cael yr holl o'r araeau hyn, pob un ohonynt
eu hunain yn cefnogi mynediad ar hap,

1110
00:52:07,240 --> 00:52:11,090
Gallaf ddechrau edrych i fyny pobl
enwi gan ddefnyddio swm o amser sy'n

1111
00:52:11,090 --> 00:52:14,340
gyfrannol i nad yw'r nifer
o bethau yn y strwythur data,

1112
00:52:14,340 --> 00:52:16,330
fel miliwn o enwau presennol.

1113
00:52:16,330 --> 00:52:20,135
Mae faint o amser mae'n ei gymryd i mi i ddod o hyd
M-A-X-W-E-L-L yn y strwythur data hwn yn

1114
00:52:20,135 --> 00:52:22,260
gyfrannol nid i'r
maint y strwythur data,

1115
00:52:22,260 --> 00:52:25,930
ond i hyd yr enw.

1116
00:52:25,930 --> 00:52:28,440
Ac yn realistig y
Enwau rydym yn edrych i fyny

1117
00:52:28,440 --> 00:52:29,970
byth yn mynd i fod yn wallgof hir.

1118
00:52:29,970 --> 00:52:32,600
Efallai rywun gymeriad 10
enw, 20 enw cymeriad.

1119
00:52:32,600 --> 00:52:33,900
Mae'n sicr yn gyfyngedig, dde?

1120
00:52:33,900 --> 00:52:37,110
Mae gan bobl ar y Ddaear sydd
Mae gan yr enw hiraf posibl,

1121
00:52:37,110 --> 00:52:39,920
ond yr enw hwnnw yn gysonyn
Hyd gwerth, dde?

1122
00:52:39,920 --> 00:52:41,980
Nid yw'n amrywio mewn unrhyw ystyr.

1123
00:52:41,980 --> 00:52:45,090
Felly, yn y modd hwn, rydym wedi
cyflawni strwythur data

1124
00:52:45,090 --> 00:52:47,800
hynny yw amser yn gyson am-edrych.

1125
00:52:47,800 --> 00:52:50,670
Mae'n gwneud cymryd nifer o gamau
yn dibynnu ar hyd y mewnbwn,

1126
00:52:50,670 --> 00:52:54,250
ond nid y nifer o enw
yn y strwythur data.

1127
00:52:54,250 --> 00:52:58,700
Felly, os ydym yn dyblu nifer y henwau
y flwyddyn nesaf o biliwn i ddau biliwn,

1128
00:52:58,700 --> 00:53:03,720
canfyddiad Maxwell yn mynd i gymryd
yr un nifer yn union o saith cam

1129
00:53:03,720 --> 00:53:04,650
i ddod o hyd iddo.

1130
00:53:04,650 --> 00:53:08,810
Ac felly rydym yn ymddangos i wedi cyflawni
ein greal sanctaidd o redeg amser.

1131
00:53:08,810 --> 00:53:10,860
>> Felly, un neu ddau o gyhoeddiadau gyflym.

1132
00:53:10,860 --> 00:53:11,850
Cwis sero yn dod i fyny.

1133
00:53:11,850 --> 00:53:14,600
Mwy am hynny ar wefan y cwrs yn
dros yr ychydig ddyddiau nesaf.

1134
00:53:14,600 --> 00:53:17,120
Dydd Llun lecture-- ei fod yn wyliau
yma yn Harvard ddydd Llun.

1135
00:53:17,120 --> 00:53:18,850
Dyw hi ddim yn yn New Haven,
felly rydym yn cymryd y dosbarth

1136
00:53:18,850 --> 00:53:20,310
i New Haven ar gyfer darlith ar ddydd Llun.

1137
00:53:20,310 --> 00:53:22,550
Bydd popeth yn cael ei ffilmio
a ffrydio'n fyw yn ôl yr arfer,

1138
00:53:22,550 --> 00:53:24,900
ond gadewch i ben heddiw
gydag ail clip 30

1139
00:53:24,900 --> 00:53:26,910
o'r enw "Thoughts Deep"
gan Daven Farnham, a oedd yn

1140
00:53:26,910 --> 00:53:30,850
Ysbrydolwyd y llynedd erbyn dydd Sadwrn
"Thoughts Deep" Night Live

1141
00:53:30,850 --> 00:53:35,700
gan Jack Handy, a oedd yn
Dylai bellach yn gwneud synnwyr.

1142
00:53:35,700 --> 00:53:38,810
>> FFILM: Ac yn awr, "Deep
Meddyliau "gan Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabl Hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SIARADWR 1: pob hawl, dyna ni am y tro.

1147
00:53:47,660 --> 00:53:48,805
Byddwn yn gweld chi yr wythnos nesaf.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: I weld ei waith.

1150
00:53:56,680 --> 00:53:58,304
Felly, gadewch i ni edrych ar hynny ar hyn o bryd.

1151
00:53:58,304 --> 00:53:59,890
Felly dyma, mae gennym amrywiaeth heb eu didoli.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, gallwch chi fynd yn ei flaen a restart
hwn am ddim ond un eiliad, os gwelwch yn dda.

1153
00:54:04,860 --> 00:54:08,562
Mae pob hawl, camerâu yn cael eu rholio, felly
gweithredu pryd bynnag y byddwch yn barod, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: pob hawl, felly yr hyn yr ydym
gennym yma yw amrywiaeth heb eu didoli.

1155
00:54:11,020 --> 00:54:13,960
Ac yr wyf i wedi lliw holl elfennau
coch i ddangos ei fod yn, mewn gwirionedd,

1156
00:54:13,960 --> 00:54:14,460
heb eu didoli.

1157
00:54:14,460 --> 00:54:17,960
Felly yn cofio bod y peth cyntaf rydym yn ei wneud
yw ein didoli hanner chwith y rhesi.

1158
00:54:17,960 --> 00:54:20,630
Yna rydym yn didoli'r hawl
hanner y rhesi.

1159
00:54:20,630 --> 00:54:22,830
Ac ya-da, ya-da, ya-da,
yr ydym yn eu cyfuno gyda'i gilydd.

1160
00:54:22,830 --> 00:54:24,520
Ac mae gennym amrywiaeth cwbl didoli.

1161
00:54:24,520 --> 00:54:25,360
Felly dyna sut uno fath yn gweithio.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, Whoa, Whoa,
torri, torri, torri, torri.

1163
00:54:27,109 --> 00:54:30,130
Doug, nad ydych yn gallu dim ond ya-da, ya-da,
ya-da, eich ffordd drwy'r fath uno.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Fi jyst yn gwneud.

1165
00:54:31,970 --> 00:54:32,832
Mae'n iawn.

1166
00:54:32,832 --> 00:54:33,540
Rydym yn dda i fynd.

1167
00:54:33,540 --> 00:54:34,760
Gadewch i ni jyst cadw dreigl.

1168
00:54:34,760 --> 00:54:35,380
Felly beth bynnag,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: rhaid i chi esbonio
mae'n llawnach na hynny.

1170
00:54:37,800 --> 00:54:39,999
Dyw hynny ddim yn unig yn ddigon.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, nid ydym yn ei wneud
Mae angen i fynd yn ôl i un.

1172
00:54:41,790 --> 00:54:42,350
Mae'n iawn.

1173
00:54:42,350 --> 00:54:45,690
Felly beth bynnag, os byddwn yn parhau â merge--
Ian, rydym yn yng nghanol y ffilmio.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Yr wyf yn gwybod.

1175
00:54:46,612 --> 00:54:49,320
Ac ni allwn dim ond ya-da, ya-da,
ya-da, trwy'r broses gyfan.

1176
00:54:49,320 --> 00:54:52,200
Mae'n rhaid i chi egluro sut mae'r
ddwy ochr yn cael eu cyfuno gyda'i gilydd.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Ond rydym wedi eisoes
esbonio sut mae'r ddau sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Yr ydych chi newydd ei ddangos
nhw amrywiaeth uno.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Maent yn gwybod y broses.

1180
00:54:56,486 --> 00:54:57,172
Maen nhw'n iawn.

1181
00:54:57,172 --> 00:54:58,380
Rydym wedi mynd dros ei ddeg gwaith.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Yr ydych newydd hepgor hawl drosto.

1183
00:55:00,330 --> 00:55:03,360
Rydym yn mynd yn ôl i un, yr ydych
Ni allwch chi ya-da, ya-da drosto.

1184
00:55:03,360 --> 00:55:05,480
Mae pob hawl, yn ôl i un.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Rhaid i mi fynd yn ôl
drwy bob un o'r sleidiau?

1186
00:55:07,833 --> 00:55:08,332
Fy Nuw.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Mae fel yr amser dosbarth, Ian.

1189
00:55:13,004 --> 00:55:13,940
Mae'n iawn.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Pob hawl.

1191
00:55:15,200 --> 00:55:16,590
Rydych yn barod?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Gweithredu.