Сьогодні ми почнемо серію більш технічних тем, тому що після останнього відео про інтерв'ю було багато запитів про алгоритми та структури даних. Тому я вирішив зробити серію відео на цю тему.
Отож поїхали. Розпочнемо ми з основ computer science - це структури даних.
Концепт структур даних є найбільш фундаментальним для розробника.
Ці знання є must have для дизайну та проєктування ефективних digital систем.
Ми зіштовхуємось з даними щодня. І тому, те як ми зберігаємо та обробляємо дані має велике значення. Наприклад, візьмем словник українсько-англійської мови.
Ми можемо швидко шукати та перекладати слова. Завдяки тому що усі слова в словнику посортовані за алфавітом. Якби слова були у рандомному / хаотичному порядку - таким словником було б дуже важко користуватись.
Наступний приклад, мапа міста:
Усі дані, такі як об'єкти, будинки та вулиці, нанесені у виді геометричних фігур на двовимірну площину - план. Таким чином, мапа є структурованою та допомагає нам швидко, наприклад, прокласти маршрут від однієї локації до іншої.
Наступний приклад, товарний чек:
Такі дані краще організувати в формі таблиці - для того, щоб можна було швидко отримати необхідну інформацію про вартість товару або продавця.
Таким чином, ми бачимо, що нам потрібні різні структури даних для організації різної інформації. Комп'ютер також працює з різними типами даних текст, відео , аудіо, зображення та будь-що. Взагалі організація та групування таких даних має значення, тому що комп'ютери працюють з великою кількістю таких даних. І тому якщо не використовувати оптимальні структури для зберігання - багато обчислювальних ресурсів буде витрачатись дарма.
Формальне визначення структури даних є спосіб зберігання та організації інформації в комп'ютері, для подальшого ефективного використання.
Ми можемо описати такі структури як:
1. Математичні / логічні моделі у абстрактному вигляді
Наприклад
Модель телевізора може бути визначена як електричний прилад, який може:
У такій теоретичній моделі ми не фокусуємось як саме працює цей пристрій, чи хто виготовив його. Ми просто визначаємо абстрактний тип даних / структуру.
Тож ідемо далі. Визначимо абстрактну модель для списку List. Який може:
Конкретною реалізацією абстрактного типу даних List наприклад є Array.
2. Ми можемо говорити про структури даних як про реалізацію, тобто про конкретний тип даних.
Наприклад, іншою імплементацією структури List є LinkedList. Цей конкретний тип ми також розглянемо пізніше.
Таким чином ми бачимо, що абстрактна модель описує дані та операції над ними, але нічого не каже про імплементацію.
Ми будемо розглядати структури даних спочатку як абстрактні моделі - а потім будемо робити конкретну реалізацію. Наразі планую розглянути такі базові структури у наступних відео:
Ми зіштовхуємось з даними щодня. І тому, те як ми зберігаємо та обробляємо дані має велике значення. Наприклад, візьмем словник українсько-англійської мови.
Ми можемо швидко шукати та перекладати слова. Завдяки тому що усі слова в словнику посортовані за алфавітом. Якби слова були у рандомному / хаотичному порядку - таким словником було б дуже важко користуватись.
Наступний приклад, мапа міста:
Усі дані, такі як об'єкти, будинки та вулиці, нанесені у виді геометричних фігур на двовимірну площину - план. Таким чином, мапа є структурованою та допомагає нам швидко, наприклад, прокласти маршрут від однієї локації до іншої.
Наступний приклад, товарний чек:
Такі дані краще організувати в формі таблиці - для того, щоб можна було швидко отримати необхідну інформацію про вартість товару або продавця.
Таким чином, ми бачимо, що нам потрібні різні структури даних для організації різної інформації. Комп'ютер також працює з різними типами даних текст, відео , аудіо, зображення та будь-що. Взагалі організація та групування таких даних має значення, тому що комп'ютери працюють з великою кількістю таких даних. І тому якщо не використовувати оптимальні структури для зберігання - багато обчислювальних ресурсів буде витрачатись дарма.
Формальне визначення структури даних є спосіб зберігання та організації інформації в комп'ютері, для подальшого ефективного використання.
Ми можемо описати такі структури як:
1. Математичні / логічні моделі у абстрактному вигляді
Наприклад
Модель телевізора може бути визначена як електричний прилад, який може:
- включатись / вимикатись
- отримувати сигнал
- програвати аудіо та відео
У такій теоретичній моделі ми не фокусуємось як саме працює цей пристрій, чи хто виготовив його. Ми просто визначаємо абстрактний тип даних / структуру.
Тож ідемо далі. Визначимо абстрактну модель для списку List. Який може:
- Зберігати наданні числа
- Отримувати числа за порядковим номером / індексом у списку
- Може змінювати числа за індексом
Конкретною реалізацією абстрактного типу даних List наприклад є Array.
2. Ми можемо говорити про структури даних як про реалізацію, тобто про конкретний тип даних.
Наприклад, іншою імплементацією структури List є LinkedList. Цей конкретний тип ми також розглянемо пізніше.
Таким чином ми бачимо, що абстрактна модель описує дані та операції над ними, але нічого не каже про імплементацію.
Ми будемо розглядати структури даних спочатку як абстрактні моделі - а потім будемо робити конкретну реалізацію. Наразі планую розглянути такі базові структури у наступних відео:
- Array (масив)
- Linked List (зв'язаний список)
- Stack (стек)
- Queue (черга)
- Tree (дерево)
- Graph (граф)
- Логічну модель (на прикладах TDD / BDD)
- Операції для структури
- Ціна операції O(n) / або складність маніпуляції над даними
- Імплементація структури даних за допомогою мови програмування. Скоріше за все це буде typescript.
- Буду шарити код на github із задачками.
0 Коментарі