ДАГ 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.