Просто про списках, словниках і множинах або ТОП 5 структур даних

    
 
Привіт. Їй! Не кажіть "Так блін! Я знаю, чим відрізняється список від вектора, мені не потрібна ця стаття ". Прошу, загляньте під кат і освіжіть свої знання. Я сподіваюся, однак, що ви зможете почерпнути з цієї статті набагато більше і, деякі, можливо, нарешті розберуться, чому існує так багато типів даних для колекцій об'єктів.
 
 Введення
Так уже склалося, що в програмуванні колекції представляє багато, немає ДУЖЕ БАГАТО різних сутностей — списки, масиви, вектора, безлічі, стеки, черги, асоціативні масиви і у більшості з цих структур даних є ще по кілька підвидів.
 
Повинні ж бути причини, щоб для простого представлення якої-небудь сукупності об'єктів існувало настільки багато різних варіацій.
 
Повинні ж бути відмінності між списком і масивом? Між асоціативним масивом і хеш-таблицею?
 
 

Колекція

Для початку — саме нудне (так, я люблю таке). Що таке колекція взагалі?
 
Колекція — структура даних (тип, клас, навіть краще сказати інтерфейс), яка створена, щоб утримувати в собі деяку кількість об'єктів (залежно від мови і термінології вони повинні бути одного типу або можуть бути різних типів).
 
Різні типи колекцій можуть бути статичними або динамічними, тобто змінювати свій розмір або залишатися постійними, можуть бути впорядкованими (точніше враховують порядок елементів) і неупорядкованими (відповідно не враховують).
 
Над колекціями передбачено кілька стандартних операцій (зараз ми поговоримо про мутабельності, тобто змінних колекціях), таких як: отримання розміру, додавання елемента, видалення елемента, пошук (є який-небудь елемент в колекції чи ні), їх дуже багато.
 
Гаразд, свій негласний борг я виконав, тепер поїхали!
 
 1 Вектор (Vector, Array)
 
 А ви чого чекали?
 
Вектор (він же одновимірний масив) — впорядкований набір елементів з довільним доступом по числовому індексом. Що для нас важливо в цьому визначенні? Та нічого. Жартую, насправді нам важливо майже кожне слово:
 
Доступ до елементів проводиться по числовому індексом (зазвичай починаючи з 0-го індексу, хоча є і винятки), зазвичай доступ до елементу колекції по індексу записується як myFavoriteCats [i] або blackKitties [5]. Причому для позначення цього самого числа — індексу використовують букву i.
 
А коли однієї букви не вистачає приплітають сюди j і k.
 
Отже, далі ми розуміємо, що доступ довільний — значить ми можемо звертатися до елементів під індексами 0, 42, 2014 і вобщем-то очікуємо, що операція буде складності O (1), тобто константної і незалежно від того який з елементів ми запитаємо він нас зі швидкістю світла тут же повернеться.
 
Далі — вектор — упорядкована колекція, що власне зрозуміло — у нас є такі поняття як перший, останній елемент, для кожного конкретно взятого елемента ми також можемо назвати попередній і наступний.
 
 

Релізація

Зазвичай вектор (як низкоуровневая структура) буде представляти із себе дескриптор, що містить різну інформацію, невіддільну від самої структури (найрозумніше тримати там тільки розмір вектора) і покажчик на перший елемент.
 
Така реалізація дозволить за константне час отримати доступ до довільного елементу вектора за його індексом, а також дозволить виконувати копіювання, конкатенацію та інші прості операції на низькому рівні.
 
І дійсно, отримати доступ до певного елемента дуже просто — додаємо до покажчика на перший елемент індекс (з деякими поправками на розмір типу даних) і отримуємо покажчик на потрібний елемент! Залишилося разименовать і у нас у змінній потрібна кішечка!
 
Гаразд, вектор — класна структура, але і у нього є недоліки (а у кого їх немає?!), Наприклад не можна просто так взяти і додати в вектор новий елемент! Особливо втиснути його в середину. Не можна також сказати, що кішки з номерами 0, 1 і 4 у нас є, а з номерами 2 і 3 — ні (раніше вони були, але виявилося, що це собаки).
 
Можна уявити собі вектор, як книжкову полицю з відділеннями, в кожному з яких міститься рівно одна книга. Щоб засунути новий роман Донцової між 10-м і 11-м томом Великий совєцької Енциклопедії потрібно сильно постаратися і перекласти всі томи з 11-го по 65-й томи (можна схитрувати і поставити 11-ий том в кінець, але я вам цього не говорив, та й ми в такому випадку втратимо впорядкованість).
 
 
 У моїй пам'яті все саме так
 
 

Застосування

У нашому випадку вектор б ідеально підійшов для топ-10 найбільш милих кошенят, тому що додавати і видаляти елементи не потрібно (тільки змінювати), пропусків між 1-им і 5-м місцем бути не повинно, та й зручно звертатися за номером.
 
Гаразд. У будь-якому випадку вектор класний, ми просто подивимося які є ще колекції.
 
 2 Список (List)
 
 Перший том
 
Ух! Список завдань на сьогодні, список покупок в магазині. Список гостей на весілля… Так. Ближче до справи.
 
Ми вже знаємо, що елементи вектора лежать акуратненько один за одним, красиво і рівно. Це дає нам як переваги так і недоліки.
 
Список в цьому плані повністю протилежна річ — його елементи можуть бути розкидані по пам'яті як завгодно! Через це ми втрачаємо можливість швидко отримати елемент за індексом, а також не можемо швидко скопіювати весь список, але отримуємо досить приємну штуку — ми можемо вставляти елементи за константне час в будь-яке місце! З чуток видаляються елементи зі списку теж за O (1).
 
 

Реалізація

Хм. А як з формальним визначенням?
 
Список — впорядкований набір елементів, для кожного з яких зберігається покажчик на наступний (або для двусвязного списку і на наступний і на попередній) елементи списку.
 
Для останнього елемента списку ми зберігаємо нульовий вказівник (на діаграмах я буду використовувати покажчик на нульову кішку (Null Cat), не лякайтеся).
 
Увага! У канонічній реалізації списку, для того, щоб отримати розмір списку, необхідно обійти весь список — дійшовши до нульового покажчика (лінійний час — складність O (n)) і хоча в деяких реалізаціях розмір кешируєтся в дескрипторі списку (або в першому елементі), що не варто на це покладатися.
 
 
 Якби я міг, я б один елемент списку розмістив на північному полюсі, а інший десь в околицях Бетельгейзе
 
 

Застосування

Список б підійшов для (увага!) списку бездомних кошенят, відсортованих за віком (по зростанню). Нам як-раз потрібно часто додавати і видаляти елементи зі списку (ви не подумайте нічого такого — кошенят забирають), та й частіше знадобляться перші елементи списку — я б взяв собі маленького пухнастого кошеня, а не 8-ми-річного манула.
 
Гаразд. Списки це начебто проста структура. Що є ще?
 
 3 Безліч (Set)
 
 Це Сет
 
Схоже поняття є в математиці, а точніше в теорії множин. Безліч відрізняється і від вектора і від списку, хоча їх реалізація може бути схожа.
 
Безліч — невпорядкований набір елементів, без повторів. Ух. І все? Ні тобі довільного доступу, нічого! Навіщо таке потрібно?
 
Як ми знаємо в векторі можна швидко отримати елемент за індексом, в списку можна швидко додати або видалити елемент, а що з безліччю?
 
У безлічі можна швидко перевірити, чи є який-небудь елемент всередині, або його немає. Скажімо якби я хотів дізнатися, чи знаходиться конкретна кішка в моєму списку улюблених, то і для списку і для вектора мені довелося б перебрати (в Худжі випадку) всі елементи!
 
 

Реалізація

У безлічі, тому що воно невпорядковані можна сортувати елементи при додаванні і в разі чого влаштувати бінарний пошук. Хм. Адже ось парадокс, колекція неупорядкована, а всередині все буде по-порядку. Тут важливо зрозуміти, що якщо ви додасте новий елемент у безліч, не факт, що він піде в кінець.
 
Насправді, працюючи з безліччю взагалі не можна покладатися на який-небудь порядок елементів, він може бути будь-яким — саме тому безліч і неупорядкована колекція.
 
Варто відзначити, що безліч може бути реалізовано безліччю різних способів, наприклад можна використовувати хеширование, для ще більш швидкого пошуку елементів, тому докладно реалізацію я розглядати не буду. Скажу лише, що можна схитрувати і використовувати наші знання за списками.
 
Взагалі є ще впорядковані множини, безлічі з повторами (мультімножество), і ймовірно має бути впорядковане мультімножество.
 
 
 Теорія множин дається простіше, якщо брати безліч кошенят
 
 

Застосування

Безліч ідеально підійде для списку улюблених кошенят, бо безліч. Ха! Жартую.
 
Але воно дійсно підійде, тому-що таку колекцію не потрібно сортувати (впорядкованість не важлива) і ми легко зможемо перевірити, чи знаходиться який-небудь конкретний кіт у цій множині (скажімо у мене 100 кошенят і улюблених я годую креветками).
 
Ну ладно. Безлічі теж хороші, але невже є щось ще?
 
 4 Словник (Associative Array, Map, Dictionary)
 
 Зізнайтеся, це краще, ніж просто словник
 
Словник (він же асоціативний масив) — це той-же вектор, але з невеликими відмінностями. В якості індексу (який у словнику буде називатися ключ) можуть виступати не тільки числа, а й будь-які інші типи даних (навіть інші колекції!). Також допустимі пропуски, якщо ми все-таки будемо використовувати в якості ключа ціле число, наприклад у нас може бути елемент пов'язаний з ключем 5, але при цьому відсутні елемент пов'язаний з ключем 4.
 
Що все це означає на практиці? Всього-лише, те, що в квадратних дужках для казу до елементу за "індексом" ми можемо вказувати довільний тип, наприклад allMyCats ["Murka"].
 
 

Реалізація

Неозброєним видно, що можна просто завести масив (або список) пар (Ключ, Значення) і додати спеціальну функцію, яка буде пробігати по цьому списку і повертати певне значення по пов'язаному з ним ключу.
 
Ми також не можемо сказати яка пара перших, яка остання і що раніше "Murka" або "Borka", тому словник вважається невпорядкованою структурою.
 
Знову-ж з кожним ключем може бути пов'язане лише одне значення, тому для наведеного прикладу з іменами кішок словник в чистому вигляді підходить слабо.
 
Реалізація, як і у випадку з безліччю, може бути абсолютно різною, можна впорядкувати пари по ключу і використовувати для отримання елемента бінарний пошук (у такому випадку елементи повинні бути упорядочеваемимі). Знову-ж можна реалізувати словник за допомогою хешування ключа, що досить часто використовується з рядками.
 
 

Застосування

Самий правдоподібний і грамотний спосіб — використовувати словник разом зі списком, де ключем словника буде рядок — ім'я кішки, а значенням — список кішок з таким ім'ям. Це дозволить швидко знайти всіх кішок по імені Мурка і вибрати з них ту, яка в даний момент потрібна.
 
 
 Приблизно так виглядає в пам'яті std :: map <std :: color, std :: list <std::cat>>
 
І у мене для вас новина — типи колекцій закінчилися. Ну все. Взагалі більше немає. Зовсім.
 
 5 Стек (Stack)
 
 Ще один кіт і буде Stack Overflow
 
Ха! Я вас обдурив (всмисле пожартував)! Є ще пара структур даних, які представляють колекції.
 
Отже стек — колекція з незвичайним доступом, точніше з незвичайними правилами щодо того, як можуть бути додані і видалені елементи.
 
Все просто — елемент,, званий "останнім", перший вибуває з з стека.
 
Стек дуже потрібний і корисний в програмуванні. Наприклад за допомогою стека здійснюється вкладений виклик процедур — в стек зберігаються адресу повернення і аргументи викликаної функції.
 
 

Реалізація

У високорівневою реалізації нічого особливо цікавого немає — покажчик на список і елементи додаються в початок цього списку, і видаляються з нього-ж.
 
У низкоуровневой реалізації (точніше те, як він реалізований в сучасних архітектурах) є цікаві моменти.
 
Стек там є невеликим зарезервованим ділянкою пам'яті й разом з ним зберігається два покажчика — на початок стека (де лежить перший доавленний елемент) і кінець стека — де лежить останній доданий.
 
Якщо в стек помістити занадто багато даних програма завершиться з усім знайомої помилкою — Stack Overflow, це означає, що покажчик на кінець стека перевищив верхня допустима межа.
 
Також може статися зворотна ситуація (Stack Underflow), якщо спробувати забрати з стека більше ніж у ньому є, але в високорівневих мовах вона не зустрічається (зрозуміло чому — нам не дають напряму працювати зі стеком).
 
Якщо кому цікаво як це все працює — вивчення асемблера для якої-небудь популярної архітектури, начебто i386, може вам допомогти.
 
 

Застосування

Можна було-б описати в цьому місці стек з бідних кошенят висотою з гору, але насправді в високорівневих мовах стек рідко необхідний, часто вистачає рекурсії, яка використовує стек неявно. Я не став прикладати надуманий приклад (і не зміг придумати нормальний, вибачте), тому переходимо до наступного пункту.
 
 Різне
Насправді є ще купа колекцій, таких як черга, двостороння черга (дек), двусвязанний список, кільцеве безліч, черги з пріоритетом.
 
Є дерева (та їх цілий ліс!) І графи.
 
Є імовірнісні структури даних, такі як розподіл усіх безліч і список з пропусками.
 
Я дуже хочу про все це написати, але часу і місця на Хабре не завжди мало.
 
Однак є безліч (або вектор) речей, що відносяться до теми, які я хотів би згадати хоч побіжно, нехай просить мене цікавий читач і піде читати розумну книгу.
 
 

Рядки

У першу чергу те, як реалізовані рядки в деяких мовах може здатися дивним. Найпростіше і ефективне рішення це напевно рішення C — рядок це набір символів, з нульовим символом в кінці, що дозволяє обходитися без дескриптора.
 
У C + + std :: string вже більше походить на вектор.
 
Ну а в старому паскале дескриптор (точніше всього-лише довжина) зберігається в нульовому елементі масиву.
 
У Haskell String — це список символів ([Char]), з чого випливає, що отримання довжини рядка має складність O (n). Зате їх дуже зручно оббігати рекурсивно.
 
У загальному випадку, рядок — це впорядкований набір символів і не більше. Який саме тип колекції буде використаний — не важливо (ну я б не радив використовувати безліч, ха!).
 
 

Черга (Queue)

Черга дуже схожа на стек і в теж час є його протилежністю — першим ми отримаємо назад не той елемент, що ми додали останнім, а той, що "стоїть у черзі" довше за всіх. Черга дуже зручна структура, але незважаючи, на те, що принцип її роботи схожий зі стеком, в ефективній реалізації є невелика відмінність.
 
Для стека ми могли схитрувати і виділити прийнятний за розміром ділянку пам'яті, в разі чого його розширюючи, тому-що стек то зменшується, то збільшується, тому що елементи і додаються і видаляються "з одного кінця". Якщо ж ми представимо роботу черги, то вона буде "повзти в пам'яті" — початок буде постійно зрушуватися вгору, тому трюк, який можна застосувати для стека, буде працювати гірше і тут вже набагато краще буде використовувати двусвязний список (і не забудьте зберігати покажчики на перший і останній елементи).
 
Ще можете спробувати реалізвать чергу на двох стеках, але це теж менш ефективно.
 
Також є дек (двостороння чергу — deque). У ній можна додавати елементи як в кінець, так і в початок. І забирати їх теж і з кінця і з початку.
 
 Висновок
 
 Ух. Я починаю повторюватися
 
Я зовсім не згадав, про комбінування різних колекцій, завдяки яким утворюються матриці, таблиці. Також я не торкнувся дерева, кільцеве безліч, майже нічого не написав про черги, дуже мало інформації по хешування (я таки відбувся парою слів від цієї теми) та іншим методам оптимізації.
 
Однак я думаю стаття виконає свою роль — просто і зрозуміло викладе основи структур даних для читачів різного ступеня підготовленості. І я буду радий продовжити й висвітлити безліч (або чергу, ха!) Інших тем в такому-ж ключі.
 
Дякуємо тим, хто зміг дочитати аж до цих рядків (як вони це витримали?).
 
Поки і удачі!
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.