Даг Lloyd: Так у CS50, мы разгледзелі шмат розных структур дадзеных, дакладна? Мы бачылі масівы, і звязана спісы, хэш-табліцы і, і спрабуе, стэкі і чэргі. Мы таксама даведаемся крыху аб дрэвах і кучы, але на самой справе гэта ўсяго толькі канец тым, што варыяцыі на тэму. Там на самай справе гэта выгляд з чатырох асноўных ідэй што ўсё яшчэ можа зводзіцца да. Масівы, звязаныя спісы, хэш-табліцы, і спрабуе. І, як я ўжо сказаў, варыяцыі на іх, але гэта даволі шмат адбываецца абагульніць усё, што мы будзем казаць аб у гэтым класе з пункту гледжання С. Але як зрабіць гэта ўсё мерай, праўда? Мы гаварылі пра плюсы і мінусы кожнага з іх у асобных відэа на іх, але ёсць шмат лічбаў атрымліваць кінуў вакол. Там вельмі шмат агульнага думкі атрымліваць раскіданыя. Давайце паспрабуем і кансалідацыі гэта ў адным месцы. Давайце ўзважваць плюсы ад мінусы, і разгледзець у склад якога дадзеныя можа быць правільным дадзеных структура вашай канкрэтнай сітуацыі, незалежна ад выгляду дадзеных, якія вы захоўвання. Вам не абавязкова заўсёды павінны выкарыстоўваць звышхуткіх ўстаўкі, выдалення, і пошук з сінтаксічнага дрэва, калі вы сапраўды не клапоцяцца пра ўстаўкі і выдаленні занадта. Калі вам трэба проста хутка выпадковых доступу, можа быць, масіў, тым лепш. Такім чынам, давайце пераганяць, што. Давайце пагаворым аб кожным з чатырох асноўных выгляду структур дадзеных што мы гаварылі, і проста бачыць, калі яны маглі б быць добра, і калі яны не могуць быць так добра. Такім чынам, давайце пачнем з масівамі. Так ўстаўкі, гэта свайго роду дрэнна. 

Ўносяцца ў канцы масіва ў парадку, калі мы будуем масіў, як мы ідзем. Але калі нам трэба ўставіць элементы ў сярэдзіне, ўспомніце ўстаўкі сартаваць, ёсць шмат зруху, каб адпавядаць элемент там. І таму, калі мы збіраемся, каб ўставіць дзе заўгодна, але ў канцы масіва, гэта, напэўна, не так ужо вялікая. 

Аналагічна, выдаленне, калі мы не выдаленне з канца масіва, гэта, верагодна, таксама не так выдатна, калі мы не хочам, каб пакінуць пустыя прабелы, якія звычайна мы не робім. Мы хочам, каб выдаліць элемент, і потым накшталт зрабіць гэта ўтульна зноў. І так выдалення элементаў з масіў, а таксама не гэтак вялікая. 

Пошук, аднак, гэта выдатна. У нас ёсць адвольны доступ, пастаянная часу пошуку. Мы проста скажам, сем, і мы ідзем масіву перасялення сем. Мы кажам 20, з ходу ў Масіў перасяленне 20. Мы не павінны паўтараць праз. Гэта вельмі добра. 

Масівы таксама адносна лёгка сартаваць. Кожны раз, калі мы казалі аб сартаванні Алгарытм, такіх як выбар выгляду, сартаванне ўстаўкамі, пузырьковый сартаванне, зліццё сартаваць, мы заўсёды выкарыстоўвалі масівы, каб зрабіць гэта, таму што масівы даволі лёгка роду, у адносінах да структурам дадзеных мы бачылі да гэтага часу. 

Яны таксама адносна невялікі. Там не так шмат дадатковага прасторы. Вы проста адкладзеце роўна столькі як вам трэба, каб трымаць вашыя дадзеныя, і гэта даволі шмат яго. Так яны даволі малыя і эфектыўнай такім чынам. Але іншы недахоп, хоць, з'яўляецца тое, што яны не будуць ліквідаваны ў памеры. Мы павінны абвясьціць, як менавіта вялікі, мы хочам наш масіў, каб быць, і мы толькі адзін стрэл на яго. Мы не можам расці і сціснуць яго. 

Калі мы павінны расці або сціснуць яго, мы трэба абвясціць зусім новы масіў, скапіяваць ўсе элементы Першы масіў ў другой масіў. І калі мы пралічыліся, што раз мы павінны зрабіць гэта зноў. Не так выдатна. Так масівы не даюць нам гнуткасць каб мець пераменнае колькасць элементаў. 

З звязанага спісу, устаўка даволі лёгка. Мы проста лавіраваць на фронце. Выдаленне таксама даволі лёгка. Мы павінны знайсці элементы. Гэта ўключае некаторы пошук. 

Але як толькі вы знайшлі элемент Вы шукаеце, усё, што вам трэба зрабіць, гэта змяніць паказальнік, магчыма два, калі ў вас ёсць звязаны list-- ўдвая Звязаны спіс, rather-- і тады вы можаце проста вызваліць вузел. Вы не павінны перакладаць ўсё вакол. Вы проста змяніць два паказальніка, так што гэта даволі хутка. 

Пошук дрэнна, праўда? Для таго, каб нам знайсці элемент звязанага спісу, Ці паасобку ці двайны сувяззю, мы павінны шукаць яго лінейным. Мы павінны пачаць з самага пачатку і перамясціць канец, або пачаць у канцы ходу да пачатку. Мы не маем адвольны доступ больш. Так што, калі мы робім Шмат пошуку, можа быць, звязаны спіс не з'яўляецца зусім так добра для нас. 

Яны таксама вельмі цяжка разабрацца, ці не так? Адзіны спосаб вы можаце сапраўды сартавання звязанага спісу для сартавання яго, як вы пабудаваць яго. Але калі вы сартаваць яго, як вы не пабудаваць яго, вы больш не прыняцця хуткіх уставак больш. Вы не проста лавіраваць рэчы на ​​фронт. Вы павінны знайсці правільнае месца, каб пакласці яго, і тады ваш ўстаўкі становіцца амаль так жа дрэнна як устаўка ў масіў. Так звязаныя спісы не так выдатна для сартавання дадзеных. 

Яны таксама даволі невялікі, памер-мудры. Двунаправленный спіс трохі больш, чым паасобку, звязаных спісаў, які трохі больш у параўнанні з масівамі, але гэта не велізарная колькасць невыкарыстоўваемай прасторы. Так што, калі прастору ў вялікай пашане, але не вельмі інтэнсіўным прэміум, гэта можа быць правільны шлях. 

Хэш-табліцы. Ўносяцца ў хэш-табліцы даволі простая. Гэта двухступеньчатая працэс. Па-першае, мы павінны запусціць нашы дадзеныя праз хэш-функцыя, каб атрымаць хэш-код, а затым вставляем элемент у Хэш-табліца ў гэтай хэш-код размяшчэння. 

Выдаленне, падобна звязанага спісу, лёгка, як толькі вы знойдзеце элемент. Вы павінны знайсці яго першым, але потым, калі вы выдаліце ​​яго, вам проста трэба абмяняць пару паказальнікаў, калі вы выкарыстоўваеце асобны ланцужкі. Калі вы выкарыстоўваеце зандзіравання, або калі вы не з дапамогай ланцужкі на ўсіх у хэш-табліцы, выдаленне на самай справе вельмі проста. Усё, што вам трэба зрабіць, гэта Хэш Дадзеныя, а затым перайсці да гэтага месца. І калі вы не ёсць якія-небудзь сутыкненняў, Вы зможаце выдаліць вельмі хутка. 

Цяпер, пошук, дзе рэчы атрымаць крыху больш складана. Гэта ў сярэднім лепш, чым звязаныя спісы. Калі вы выкарыстоўваеце ланцужкі, Вы ўсё яшчэ ёсць звязаны спіс, які азначае, што вы па-ранейшаму маюць Пошук шкоду звязаны спіс. Але таму, што вы прымаць вашыя звязана Пералік і падзелу яго на 100 або 1000 або п элементаў у вашай хэш-табліцы, вы звязаныя спісы ўсё адно п-памеру. Яны ўсё значна менш. Вы н звязаныя спісы замест аднаго звязанага спісу памеру п. 

І так пастаянная гэты рэальны фактар, які мы звычайна не гаварыць пра складанасць часу, яго сапраўды фактычна зрабіць розніцу тут. Так пошук па-ранейшаму лінейны пошук, калі вы выкарыстоўваеце ланцужкі, але даўжыня спісу Вы шукаеце праз вельмі, вельмі кароткі ў параўнанні. Зноў жа, калі гэта вашы сартаванне Мэта тут, хэш табліцы верагодна, не правільны шлях. Проста выкарыстоўвайце масіў, калі сартаванне гэта сапраўды важна для вас. 

І яны могуць запусціць гаму памераў. Цяжка сказаць, ці з'яўляецца Хэш-табліца з'яўляецца маленькі ці вялікі, таму што гэта сапраўды залежыць ад наколькі вялікі ваш хэш табліцы. Калі вы толькі збіраецеся быць захоўвання пяць элементаў у вашым хэш-табліцы, і ў вас ёсць хэш-табліцу 10000 элементаў у ім, вы, верагодна, марнаваць шмат месца. Кантраст быць Вы таксама можаце ёсць вельмі кампактныя хэш-табліцы, але менш ваша хэш-табліца атрымлівае, чым больш кожны з гэтых звязаных спісаў атрымлівае. І таму на самай справе няма спосабу вызначыць дакладна памер хэш-табліцы, але гэта, верагодна, бяспечна сказаць гэта наогул будзе больш, чым звязаны Спіс захоўвання тыя ж дадзеныя, але менш, чым сінтаксічнага дрэва. 

І спрабуе гэта чацвёрты з гэтых структур што мы гаворым пра. Устаўка ў сінтаксічнага дрэва з'яўляецца складаным. Там вельмі шмат дынамічных вылучэнне памяці, асабліва ў пачатку, а вы пачынаеце будаваць. Але гэта пастаянная часу. Гэта толькі чалавечы фактар вось што робіць яго складаным. Маючы сутыкнуцца нулявы паказальнік, Таноса прастору, туды, магчыма, Таноса прастору адтуль зноў. Свайго роду запалохвання фактар паказальнікі ў дынамічным размеркаванні памяці з'яўляецца перашкодай, каб ачысціць. Але як толькі вы ачысцілі яго, устаўка на самай справе адбываецца даволі проста, і гэта, вядома, сталая часу. 

Выдаленне лёгка. Усё, што вам трэба зрабіць, гэта перайсці ўніз пара паказальнікаў і бясплатным вузла, так што гэта даволі добра. Пошук таксама даволі хутка. Гэта толькі на аснове даўжыня вашых дадзеных. Так што, калі ўсе вашы дадзеныя ў пяць сімвалаў радкі, Напрыклад, вы захоўваеце пяць знакавыя радкі ў Вашай сінтаксічнага дрэва, гэта зойме ўсяго пяць крокаў да знайсці тое, што вы шукаеце. Пяць проста пастаянным фактарам, так зноў, устаўка, выдаленне, пошук і тут увесь час пастаяннай, эфектыўна. 

Іншая справа, што ваш Trie з'яўляецца на самай справе выгляд ужо адсартаваныя, праўда? З-за таго, як мы устаўка элементаў, перайшоўшы па літарах з Ключ, або лічба за лічбай ключа, звычайна, на ваш Trie заканчваецца час выгляд сартуюцца, як вы будуеце яго. Гэта на самай справе не робіць сэнс падумаць аб сартаванні такім жа чынам, мы думаем пра гэта з масівамі, або звязаныя спісы, або хэш-табліцы. Але ў нейкім сэнсе, ваш Trie сартуецца, як вы ідзяце. 

Недахопам, вядома, з'яўляецца тое, што Trie хутка становіцца велізарным. З кожнай кропкі пераходу, вы можаце have-- калі ваш ключ складаецца з лічбаў, у вас ёсць 10 іншых месцы, якія вы можаце пайсці, што азначае, што кожны вузел змяшчае інфармацыю аб дадзеных, якія вы хочаце захаваць у гэтым вузле, плюс 10 паказальнікаў. Што, па CS50 IDE, 80 байт. Так што, па меншай меры 80 байта для кожны вузел, які вы ствараеце, і гэта нават не лічачы дадзеных. І калі вашыя вузлы лісты замест лічбаў, зараз у вас ёсць 26 паказальнікаў ад кожнага месца. І 26 разоў 8, верагодна, 200 байт, ці нешта падобнае. А ў вас ёсць капітал і lowercase-- вы можаце ўбачыць, дзе я збіраюся з гэтым, праўда? Вашы вузлы могуць атрымаць сапраўды вялікі, і таму Trie Сам, у цэлым, можа атрымаць сапраўды вялікі, занадта. Так што, калі прастора на высокім прэмія па вашай сістэме, Trie не можа быць правільным спосабам ісці, нават калі іншыя яго перавагі ўступаюць у гульню. Я Дуг Лойд. Гэта CS50.