1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Cyfuno Trefnu]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Mae hyn yn CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Gadewch i ni siarad am uno fath.

5
00:00:09,000 --> 00:00:14,000
Hyd yma rydych wedi ei weld, math swigen fath mewnosod, a didoli dethol.

6
00:00:14,000 --> 00:00:17,000
Er byddaf yn fath o don fy llaw ar yr hyn yr wyf yn ei olygu wrth gwell,

7
00:00:17,000 --> 00:00:21,000
uno fath yn gyffredinol yn perfformio'n well nag unrhyw un o'r 3 math.

8
00:00:22,000 --> 00:00:27,000
>> Ond cyn siarad am uno fath, gadewch i ni siarad am uno 2 restr datrys.

9
00:00:27,000 --> 00:00:31,000
Byddwn yn galw'r broses o gymryd 2 restr didoli, fel y rhain,

10
00:00:31,000 --> 00:00:35,000
a gwneud rhestr unigol datrys allan ohonyn nhw - uno y rhestrau.

11
00:00:35,000 --> 00:00:37,750
Sut allwn ni wneud hyn?

12
00:00:37,750 --> 00:00:41,290
Wel, un syniad yw i jyst daro un rhestr ar ddiwedd y rhestr arall

13
00:00:41,290 --> 00:00:43,830
ac yna ddatrys y rhestr o ganlyniad.

14
00:00:43,830 --> 00:00:47,220
>> Er bod hyn yn gweithio, mae'n llawer o waith diangen.

15
00:00:47,220 --> 00:00:49,900
Gallwn wneud yn gyflymach na dim ond didoli.

16
00:00:49,900 --> 00:00:54,100
Sylwch fod un syniad anghywir ydy at jyst yn cymryd cwpanau yn ail o bob rhestr.

17
00:00:54,100 --> 00:00:56,460
Er y gall ymddangos fel bod y gwaith ar y dechrau,

18
00:00:56,460 --> 00:01:05,760
wneud hynny rydym yn y pen i fyny gyda 4, 8, 15, 23, 16 - sylwer mai 16 a 23 allan o le.

19
00:01:05,760 --> 00:01:09,380
Mae hyn oherwydd bod 2 elfen a ddylai ymddangos yn olynol yn y rhestr unedig

20
00:01:09,380 --> 00:01:11,720
yn y rhestr gychwynnol un.

21
00:01:11,720 --> 00:01:14,850
Mae 15 ac 16 yn y rhestr ar y chwith.

22
00:01:14,850 --> 00:01:19,810
Y gamp yw i fanteisio ar y ffaith bod y ddwy restr yn cael eu datrys eisoes.

23
00:01:19,810 --> 00:01:23,320
Mae hyn yn golygu os ydym yn unig yn edrych ar elfennau cyntaf o'r ddwy restr o -

24
00:01:23,320 --> 00:01:29,580
yma, 4 ac 8 - rhaid i un ohonynt hefyd fod elfen gyntaf y rhestr unedig.

25
00:01:29,580 --> 00:01:31,620
Wel, pam hynny?

26
00:01:31,620 --> 00:01:33,520
Mae'r ddau o'r rhestri hyn yn cael eu datrys yn barod,

27
00:01:33,520 --> 00:01:38,410
ac felly mae'n rhaid naill ai 4 neu 8 fydd yr elfen lleiaf pan rydym yn cyfuno y 2 rhestrau.

28
00:01:38,410 --> 00:01:41,770
Yn yr achos hwn, y lleiaf yw 4,

29
00:01:41,770 --> 00:01:46,370
fel y gallwn gymryd 4 ac yn ei gwneud yn elfen gyntaf ein rhestr gyfunol.

30
00:01:46,370 --> 00:01:50,710
Nawr rydym yn parhau i uno'r 3 sy'n weddill elfennau o'r rhestr gyntaf

31
00:01:50,710 --> 00:01:52,920
a 4 elfen yr ail restr.

32
00:01:52,920 --> 00:01:57,150
>> Unwaith eto, dim ond angen edrych ar yr elfen gyntaf o'r ddwy restr.

33
00:01:57,150 --> 00:02:01,060
Mae'n rhaid i'r lleiaf o'r 2 fod yr ail elfen ein rhestr gyfunol.

34
00:02:01,060 --> 00:02:05,440
Y tro hwn, rhwng 8 a 15 y lleiaf yn 8, ac felly rydym yn ychwanegu bod

35
00:02:05,440 --> 00:02:09,240
fel yr ail elfen ein rhestr datrys.

36
00:02:09,240 --> 00:02:12,180
Gallwn barhau cymharu elfennau cyntaf o'r ddwy restr o

37
00:02:12,180 --> 00:02:14,420
a chael gwared ar y lleiaf o'r 2.

38
00:02:14,420 --> 00:02:19,460
Cymharu 15 a 23, 15 yn llai ac felly dyna ein drydedd elfen.

39
00:02:21,000 --> 00:02:23,910
Nawr cymharu 16 a 23, 16 yn llai.

40
00:02:23,910 --> 00:02:26,820
Felly dyna bedwaredd elfen.

41
00:02:26,820 --> 00:02:30,390
>> Sylwch fod 2 elfen yn dod o'r un rhestr yn olynol.

42
00:02:30,390 --> 00:02:34,400
Dyma pam nad oedd y rhestr unedig gall dim ond elfennau yn ail o'r 2 rhestrau.

43
00:02:34,400 --> 00:02:40,020
Cymharu 50 a 23, 23 yn llai o faint, felly rydym yn dewis hynny.

44
00:02:40,770 --> 00:02:44,070
Rhwng 50 a 42, 42 yn llai o faint.

45
00:02:44,070 --> 00:02:48,290
Rhwng 50 a 108, 50 yn llai o faint.

46
00:02:48,290 --> 00:02:52,330
Ac, yn olaf, rydym yn unig yn cael 108, felly mae'n rhaid iddo fynd ar y diwedd ein rhestr.

47
00:02:53,750 --> 00:02:56,180
Hysbysiad bod gennym 'n glws, rhestr datrys.

48
00:02:56,180 --> 00:02:59,040
Bob tro y byddwn yn cymharu y 2 elfen gyntaf y 2 restr

49
00:02:59,040 --> 00:03:02,730
roeddem yn gallu penderfynu ar yr elfen nesaf y rhestr unedig.

50
00:03:02,730 --> 00:03:08,070
Mae hyn yn golygu os bydd y rhestr derfynol yn cynnwys rhifau n, lle mae n yma yn 8,

51
00:03:08,070 --> 00:03:12,610
yna mae angen ar gymariaethau n fwyaf i gael yr holl o'r niferoedd hynny i mewn i'r lle iawn.

52
00:03:13,230 --> 00:03:16,230
O'r fath algorithm sy'n cael ei ddweud i redeg mewn amser llinol,

53
00:03:16,230 --> 00:03:18,090
ond peidiwch â phoeni am hynny yma.

54
00:03:18,570 --> 00:03:22,810
>> Gan ddefnyddio ein algorithm ar gyfer uno, gallwn wneud algorithm fath gyflym uno.

55
00:03:22,810 --> 00:03:25,170
Felly, gadewch i ailosod ein rhestrau.

56
00:03:35,210 --> 00:03:37,750
Mae 2 cam mawr yn y broses o uno fath.

57
00:03:37,750 --> 00:03:41,500
Yn gyntaf, yn barhaus rhannu rhestr o gwpanau mewn i haneri

58
00:03:41,500 --> 00:03:44,860
nes bydd gennym griw o restrau gyda dim ond 1 cwpan ynddynt.

59
00:03:44,860 --> 00:03:47,350
Peidiwch â phoeni os bydd rhestr yn cynnwys odrif

60
00:03:47,350 --> 00:03:49,880
ac ni allwch wneud toriad yn berffaith lân rhyngddynt.

61
00:03:49,880 --> 00:03:53,750
Dim ond fympwyol ddewis pa rhestr i gynnwys y cwpan ychwanegol i mewn

62
00:03:53,750 --> 00:03:56,240
Felly, gadewch i ni rannu'r rhestrau hyn.

63
00:03:58,140 --> 00:04:01,310
Nawr rydym yn cael 2 rhestrau.

64
00:04:04,120 --> 00:04:06,570
Nawr rydym wedi 4 rhestrau.

65
00:04:10,350 --> 00:04:13,870
>> Ac yn awr mae gennym 8 rhestri gyda phaned un ym mhob rhestr.

66
00:04:13,870 --> 00:04:16,630
Felly dyna ni ar gyfer cam 1.

67
00:04:16,630 --> 00:04:22,230
Ar gyfer cam 2, byddwn dro ar ôl tro uno parau o restrau defnyddio'r algorithm uno a ddysgwyd o'r blaen.

68
00:04:22,230 --> 00:04:29,160
Cyfuno 108 a 15, rydym yn darfod i fyny ag y rhestr 15, 108.

69
00:04:30,330 --> 00:04:36,250
Cyfuno 50 a 4, rydym yn y pen i fyny gyda 4, 50.

70
00:04:36,960 --> 00:04:41,400
Cyfuno 8 a 42, rydym yn darfod i fyny ag 8, 42.

71
00:04:42,790 --> 00:04:48,130
Ac uno 23 a 16 oed, rydym yn darfod i fyny ag 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nawr ein holl restrau o faint 2.

73
00:04:53,020 --> 00:04:56,180
Sylwch fod pob un o'r 4 rhestrau yn cael ei datrys.

74
00:04:56,180 --> 00:04:59,160
>> Felly, gallwn ddechrau cyfuno parau o restrau eto.

75
00:04:59,160 --> 00:05:03,240
Cyfuno 15 a 108 a 4 a 50 -

76
00:05:03,240 --> 00:05:11,170
gyntaf yn y 4, yna bydd y 15, yna y 50, yna bydd y 108.

77
00:05:11,170 --> 00:05:15,120
Cyfuno 8, 42 a 16, 23,

78
00:05:15,120 --> 00:05:22,440
rydym yn gyntaf yn y 8, yna 16, yna y 23, ac yna 42.

79
00:05:22,440 --> 00:05:27,370
Felly, nawr rydym wedi dim ond 2 restr o faint 4, pob un ohonynt yn cael ei ddidoli.

80
00:05:27,370 --> 00:05:30,980
Felly, nawr rydym cyfuno'r 2 restr.

81
00:05:30,980 --> 00:05:33,440
Yn gyntaf rydym yn cymryd y 4.

82
00:05:33,440 --> 00:05:36,580
Yna rydym yn cymryd y 8.

83
00:05:36,580 --> 00:05:50,700
Yna rydym yn cymryd y 15 a 16, yna 23, yna 42, yna 50, yna 108.

84
00:05:50,700 --> 00:05:52,220
Ac rydym ni'n ei wneud.

85
00:05:52,220 --> 00:05:54,900
Erbyn hyn mae gennym restr datrys.

86
00:05:54,900 --> 00:05:57,890
Felly, pa mor gyflym oedd hyn, yn union?

87
00:05:57,890 --> 00:06:02,000
Mewn termau technegol, merge fath yw O (n log n),

88
00:06:02,000 --> 00:06:07,380
tra bod pob un, math swigen fath mewnosod, a didoli dethol yn O (n ²).

89
00:06:07,380 --> 00:06:11,120
Yn wir, fel y byddwch yn dysgu cyn bo hir, ni fyddwch yn gallu dod o hyd i fath

90
00:06:11,120 --> 00:06:14,820
sy'n perfformio'n well na O (n log n) yn achos gyffredinol.

91
00:06:14,820 --> 00:06:19,120
Unwaith eto, peidiwch â phoeni am hyn nodiant O fawr os nad ydych wedi ei weld eto.

92
00:06:19,120 --> 00:06:23,490
>> Dim ond yn gwybod bod hyn yn golygu os ydym am roi trefn rhestr mawr iawn

93
00:06:23,490 --> 00:06:26,820
Gallai, math swigen fath mewnosod, a dewis math o bosibl yn cymryd

94
00:06:26,820 --> 00:06:29,500
sylweddol hwy nag uno fath.

95
00:06:29,500 --> 00:06:33,210
Nid yw'n golygu y bydd uno fath fod yn gyflymach ar gyfer yr holl restrau

96
00:06:33,210 --> 00:06:36,220
neu hyd yn oed ar gyfer unrhyw un rhestr o dan faint penodol.

97
00:06:36,220 --> 00:06:41,950
Er enghraifft, efallai y fath mewnosod yn y math cyflymaf ar gyfer yr holl restrau llai na 5 elfen.

98
00:06:41,950 --> 00:06:47,360
Yn ymarferol, merge fath fel arfer yn gyflymach ar gyfer rhestrau mor fach â 50 elfen.

99
00:06:47,360 --> 00:06:51,120
>> Ond nid yw hyn cyflymder ychwanegol yn dod heb pris.

100
00:06:51,120 --> 00:06:54,770
Yn wahanol i'n fathau eraill, sy'n cymryd rhestr a diwygio'r rhestr yn ei le

101
00:06:54,770 --> 00:06:58,740
hyd nes y cawn rhestr datrys, merge fath mae angen ychydig o le ychwanegol

102
00:06:58,740 --> 00:07:00,900
i uno 2 yn rhestru gyda'i gilydd.

103
00:07:00,900 --> 00:07:04,690
Ni allwn unwaith ddefnyddio'r rhestrau sy'n cael eu cyfuno i storio'r rhestr unedig

104
00:07:04,690 --> 00:07:08,880
gan y gallai rydym yn diystyru elfennau y mae angen eu cyfuno.

105
00:07:08,880 --> 00:07:13,540
Mae'r gofod yn dipyn o bris, ond nid fel arfer yn afresymol.

106
00:07:13,540 --> 00:07:15,330
A dyna ni am uno fath.

107
00:07:15,330 --> 00:07:18,490
>> Fy enw i yw Rob Bowden, ac mae hyn yn CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- A dewis fath.

110
00:07:24,000 --> 00:07:25,880
[Chwerthin]

111
00:07:25,880 --> 00:07:31,480
O, rhaid i gymryd y allan yn rhy oherwydd fy mod yn newid sut yr oeddwn yn ei chyflwyno.

112
00:07:31,480 --> 00:07:35,680
Rhestr ar y chwith. Dyna oedd yn typo.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] I sgriwio i fyny -

114
00:07:39,290 --> 00:07:41,190
[Chwerthin]

115
00:07:41,190 --> 00:07:44,190
Nid wyf yn gwybod beth -