[Powered by Google Translate] [Cyfuno Trefnu] [Rob Bowden - Harvard University] [Mae hyn yn CS50. - CS50.TV] Gadewch i ni siarad am uno fath. Hyd yma rydych wedi ei weld, math swigen fath mewnosod, a didoli dethol. Er byddaf yn fath o don fy llaw ar yr hyn yr wyf yn ei olygu wrth gwell, uno fath yn gyffredinol yn perfformio'n well nag unrhyw un o'r 3 math. 

Ond cyn siarad am uno fath, gadewch i ni siarad am uno 2 restr datrys. Byddwn yn galw'r broses o gymryd 2 restr didoli, fel y rhain, a gwneud rhestr unigol datrys allan ohonyn nhw - uno y rhestrau. Sut allwn ni wneud hyn? Wel, un syniad yw i jyst daro un rhestr ar ddiwedd y rhestr arall ac yna ddatrys y rhestr o ganlyniad. 

Er bod hyn yn gweithio, mae'n llawer o waith diangen. Gallwn wneud yn gyflymach na dim ond didoli. Sylwch fod un syniad anghywir ydy at jyst yn cymryd cwpanau yn ail o bob rhestr. Er y gall ymddangos fel bod y gwaith ar y dechrau, wneud hynny rydym yn y pen i fyny gyda 4, 8, 15, 23, 16 - sylwer mai 16 a 23 allan o le. Mae hyn oherwydd bod 2 elfen a ddylai ymddangos yn olynol yn y rhestr unedig yn y rhestr gychwynnol un. Mae 15 ac 16 yn y rhestr ar y chwith. Y gamp yw i fanteisio ar y ffaith bod y ddwy restr yn cael eu datrys eisoes. Mae hyn yn golygu os ydym yn unig yn edrych ar elfennau cyntaf o'r ddwy restr o - yma, 4 ac 8 - rhaid i un ohonynt hefyd fod elfen gyntaf y rhestr unedig. Wel, pam hynny? Mae'r ddau o'r rhestri hyn yn cael eu datrys yn barod, ac felly mae'n rhaid naill ai 4 neu 8 fydd yr elfen lleiaf pan rydym yn cyfuno y 2 rhestrau. Yn yr achos hwn, y lleiaf yw 4, fel y gallwn gymryd 4 ac yn ei gwneud yn elfen gyntaf ein rhestr gyfunol. Nawr rydym yn parhau i uno'r 3 sy'n weddill elfennau o'r rhestr gyntaf a 4 elfen yr ail restr. 

Unwaith eto, dim ond angen edrych ar yr elfen gyntaf o'r ddwy restr. Mae'n rhaid i'r lleiaf o'r 2 fod yr ail elfen ein rhestr gyfunol. Y tro hwn, rhwng 8 a 15 y lleiaf yn 8, ac felly rydym yn ychwanegu bod fel yr ail elfen ein rhestr datrys. Gallwn barhau cymharu elfennau cyntaf o'r ddwy restr o a chael gwared ar y lleiaf o'r 2. Cymharu 15 a 23, 15 yn llai ac felly dyna ein drydedd elfen. Nawr cymharu 16 a 23, 16 yn llai. Felly dyna bedwaredd elfen. 

Sylwch fod 2 elfen yn dod o'r un rhestr yn olynol. Dyma pam nad oedd y rhestr unedig gall dim ond elfennau yn ail o'r 2 rhestrau. Cymharu 50 a 23, 23 yn llai o faint, felly rydym yn dewis hynny. Rhwng 50 a 42, 42 yn llai o faint. Rhwng 50 a 108, 50 yn llai o faint. Ac, yn olaf, rydym yn unig yn cael 108, felly mae'n rhaid iddo fynd ar y diwedd ein rhestr. Hysbysiad bod gennym 'n glws, rhestr datrys. Bob tro y byddwn yn cymharu y 2 elfen gyntaf y 2 restr roeddem yn gallu penderfynu ar yr elfen nesaf y rhestr unedig. Mae hyn yn golygu os bydd y rhestr derfynol yn cynnwys rhifau n, lle mae n yma yn 8, yna mae angen ar gymariaethau n fwyaf i gael yr holl o'r niferoedd hynny i mewn i'r lle iawn. O'r fath algorithm sy'n cael ei ddweud i redeg mewn amser llinol, ond peidiwch â phoeni am hynny yma. 

Gan ddefnyddio ein algorithm ar gyfer uno, gallwn wneud algorithm fath gyflym uno. Felly, gadewch i ailosod ein rhestrau. Mae 2 cam mawr yn y broses o uno fath. Yn gyntaf, yn barhaus rhannu rhestr o gwpanau mewn i haneri nes bydd gennym griw o restrau gyda dim ond 1 cwpan ynddynt. Peidiwch â phoeni os bydd rhestr yn cynnwys odrif ac ni allwch wneud toriad yn berffaith lân rhyngddynt. Dim ond fympwyol ddewis pa rhestr i gynnwys y cwpan ychwanegol i mewn Felly, gadewch i ni rannu'r rhestrau hyn. Nawr rydym yn cael 2 rhestrau. Nawr rydym wedi 4 rhestrau. 

Ac yn awr mae gennym 8 rhestri gyda phaned un ym mhob rhestr. Felly dyna ni ar gyfer cam 1. Ar gyfer cam 2, byddwn dro ar ôl tro uno parau o restrau defnyddio'r algorithm uno a ddysgwyd o'r blaen. Cyfuno 108 a 15, rydym yn darfod i fyny ag y rhestr 15, 108. Cyfuno 50 a 4, rydym yn y pen i fyny gyda 4, 50. Cyfuno 8 a 42, rydym yn darfod i fyny ag 8, 42. Ac uno 23 a 16 oed, rydym yn darfod i fyny ag 16, 23. Nawr ein holl restrau o faint 2. Sylwch fod pob un o'r 4 rhestrau yn cael ei datrys. 

Felly, gallwn ddechrau cyfuno parau o restrau eto. Cyfuno 15 a 108 a 4 a 50 - gyntaf yn y 4, yna bydd y 15, yna y 50, yna bydd y 108. Cyfuno 8, 42 a 16, 23, rydym yn gyntaf yn y 8, yna 16, yna y 23, ac yna 42. Felly, nawr rydym wedi dim ond 2 restr o faint 4, pob un ohonynt yn cael ei ddidoli. Felly, nawr rydym cyfuno'r 2 restr. Yn gyntaf rydym yn cymryd y 4. Yna rydym yn cymryd y 8. Yna rydym yn cymryd y 15 a 16, yna 23, yna 42, yna 50, yna 108. Ac rydym ni'n ei wneud. Erbyn hyn mae gennym restr datrys. Felly, pa mor gyflym oedd hyn, yn union? Mewn termau technegol, merge fath yw O (n log n), tra bod pob un, math swigen fath mewnosod, a didoli dethol yn O (n ²). Yn wir, fel y byddwch yn dysgu cyn bo hir, ni fyddwch yn gallu dod o hyd i fath sy'n perfformio'n well na O (n log n) yn achos gyffredinol. Unwaith eto, peidiwch â phoeni am hyn nodiant O fawr os nad ydych wedi ei weld eto. 

Dim ond yn gwybod bod hyn yn golygu os ydym am roi trefn rhestr mawr iawn Gallai, math swigen fath mewnosod, a dewis math o bosibl yn cymryd sylweddol hwy nag uno fath. Nid yw'n golygu y bydd uno fath fod yn gyflymach ar gyfer yr holl restrau neu hyd yn oed ar gyfer unrhyw un rhestr o dan faint penodol. Er enghraifft, efallai y fath mewnosod yn y math cyflymaf ar gyfer yr holl restrau llai na 5 elfen. Yn ymarferol, merge fath fel arfer yn gyflymach ar gyfer rhestrau mor fach â 50 elfen. 

Ond nid yw hyn cyflymder ychwanegol yn dod heb pris. Yn wahanol i'n fathau eraill, sy'n cymryd rhestr a diwygio'r rhestr yn ei le hyd nes y cawn rhestr datrys, merge fath mae angen ychydig o le ychwanegol i uno 2 yn rhestru gyda'i gilydd. Ni allwn unwaith ddefnyddio'r rhestrau sy'n cael eu cyfuno i storio'r rhestr unedig gan y gallai rydym yn diystyru elfennau y mae angen eu cyfuno. Mae'r gofod yn dipyn o bris, ond nid fel arfer yn afresymol. A dyna ni am uno fath. 

Fy enw i yw Rob Bowden, ac mae hyn yn CS50. [CS50.TV] - A dewis fath. [Chwerthin] O, rhaid i gymryd y allan yn rhy oherwydd fy mod yn newid sut yr oeddwn yn ei chyflwyno. Rhestr ar y chwith. Dyna oedd yn typo. [Misspoke] I sgriwio i fyny - [Chwerthin] Nid wyf yn gwybod beth -