Ось готовий урок, створений у стилі лекцій CS50. Вдягаємо чорну футболку, виходимо на сцену Sanders Theatre і поїхали! 🚀

🎓 CS50: Sets (Множини) та Sorted Sets

Привіт, друзі! 👋

Сьогодні ми поговоримо про структуру даних, яка рятує розробників від зайвої роботи, а сервери — від перевантаження. Ми вже знаємо про масиви (Arrays) та списки (Lists). Вони чудові, правда? Ми можемо покласти туди все, що завгодно.

Але уявіть собі ситуацію.

1. 🔥 Вступ: Проблема та мотивація

Ви розробляєте систему для голосування на Євробаченні. У вас є масив, куди падають голоси. І ось один дуже емоційний фанат натискає кнопку "Голосувати" 50 разів поспіль за одну хвилину.

Ваш масив виглядає так: ["user_1", "user_2", "user_1", "user_1", "user_3", "user_1"...]

Запитання до вас: Чи справедливо, що "user_1" має 4 голоси, а інші — по одному? Звісно, ні. Нам потрібно зарахувати лише один унікальний голос від кожної людини.

Якби ми використовували звичайний список, нам довелося б писати код: "Пробіжись по всьому списку, перевір, чи є там вже цей юзер, і тільки якщо немає — додай". А якщо у вас мільйон голосів? Кожного разу перевіряти мільйон записів? Це ж катастрофа для швидкості! 🐢

Тут на сцену виходять Sets (Множини).

Аналогія: Уявіть собі фейс-контроль у нічному клубі. Охоронцю байдуже, скільки разів ви намагаєтеся зайти. Якщо ви вже всередині — другий ваш "клонів" туди не пустять. Ви або там є, або вас немає. Крапка.

2. 🧠 Теоретична база (без нудьги)

Отже, що таке Set (Множина)?

📌 Set — це колекція унікальних елементів. У ній немає порядку (перший, другий, останній). Головне правило: ніяких дублікатів.

📌 Sorted Set (Відсортована множина) — це те саме, але елементи в ній завжди стоять у певному порядку (наприклад, від меншого до більшого або за рейтингом).

Як це працює «під капотом»? (Magic Box 🎩)

Ви можете запитати: "Дейвіде, а чому Set швидший за список?"

У списку, щоб знайти елемент, комп'ютер перебирає комірки одна за одною: "Ти число 5? Ні. Ти число 5? Ні...". Це довго.

У множинах використовується хешування (Hashing). Уявіть величезну шафу з пронумерованими шухлядами. Коли ви даєте множині число, наприклад, 105, вона пропускає його через математичну формулу (хеш-функцію), і та каже: "Клади це в шухляду №3".

Коли ви питаєте: "Чи є в нас число 105?", множина не шукає всюди. Вона знову рахує формулу, отримує 3 і перевіряє тільки шухляду №3. Це миттєво! ⚡️

Що треба запам’ятати залізобетонно: 1. Sets гарантують унікальність. 2. Sets (зазвичай) не зберігають порядок додавання. 3. Перевірка "чи є елемент в базі" у Set працює супершвидко (O(1)).

3. 🧪 Приклади (Python Style)

Давайте подивимось на код. Я використовуватиму Python, бо він читається як англійська, але логіка однакова і в C++, і в Java, і в JavaScript.

Приклад 1: Прибираємо дублікати (The Classic)

Уявіть, що ми зібрали список email-адрес для розсилки, але туди потрапили копії.

# У нас є список із дублями
emails_list = ["bob@gmail.com", "alice@yahoo.com", "bob@gmail.com", "mike@proton.me"]

# Що ви очікуєте побачити, якщо ми перетворимо це на множину?
unique_emails = set(emails_list)

print(unique_emails)
# Результат: {'alice@yahoo.com', 'mike@proton.me', 'bob@gmail.com'}

Бачите? bob@gmail.com залишився тільки один. І порядок змінився — це нормально!

Приклад 2: Магія перетинів (Соціальна мережа)

У вас є друзі, і у мене є друзі. Хто наші спільні друзі?

my_friends = {"Alice", "Bob", "Charlie"}
your_friends = {"Bob", "David", "Charlie", "Eve"}

# Знаходимо перетин (Intersection) — тих, хто є І там, І там
common = my_friends.intersection(your_friends)

print(f"Спільні друзі: {common}")
# Результат: {'Bob', 'Charlie'}

У реальних проєктах (наприклад, в Tinder чи LinkedIn) саме так шукають "2 mutual connections".

Приклад 3: Sorted Set (Таблиця лідерів)

У стандартному Python немає окремого типу SortedSet, але в реальних системах (наприклад, база даних Redis) це кілер-фіча. Уявіть гру. Нам треба зберігати гравців і їхні бали, і щоб вони завжди були відсортовані від найкрутішого до новачка.

Концептуально це виглядає так: { ("Player1", 100), ("Player2", 500), ("Player3", 250) } Автоматично перетворюється на: 1. Player2 (500) 2. Player3 (250) 3. Player1 (100)

Це дозволяє миттєво показати "Топ-3 гравці", не сортуючи весь мільйонний список заново.

4. 🛠 Практична частина

Час розім'яти пальці! Відкривайте свій IDE або блокнот.

🔹 Завдання 1: Фільтр спаму У вас є список слів: ["buy", "crypto", "free", "money", "buy", "click"]. Створіть із нього множину, щоб побачити лише унікальні слова-тригери.

🔹 Завдання 2: Хто прогуляв? Є множина всіх студентів групи: all_students = {"Ivan", "Maria", "Petro", "Olya"}. Є множина тих, хто здав домашку: submitted = {"Maria", "Ivan"}. Використовуючи операцію різниці (difference), знайдіть список боржників.

🔹 Завдання 3: Доступ дозволено? Створіть множину admins = {"admin", "root", "super"}. Напишіть код, який питає у користувача логін (input()) і миттєво перевіряє, чи є він адміном. (Підказка: використовуйте оператор in).

🔹 Завдання 4: Міні-кейс "Унікальні візити" Ви — аналітик веб-сайту. Користувачі заходять на сторінки. Список візитів (IP-адреси): ['192.168.1.1', '127.0.0.1', '192.168.1.1', '10.0.0.1']. Скільки унікальних відвідувачів було на сайті? Виведіть число.

🔹 Завдання 5 (Зірочка*): Sorted Logic У вас є словник з оцінками: {"Math": 90, "History": 75, "CS": 100}. Спробуйте вивести предмети в порядку зростання оцінки. (Тут доведеться схитрувати і використати функцію сортування ключів, адже чисті множини не мають порядку!).

5. 💡 Мислення як у розробника

Як відрізнити новачка від профі, коли вони працюють з даними?

🚫 Помилка новачка: Використовувати списки (Lists) для перевірки наявності (if item in my_list). Чому це погано: Якщо у вас 10 тисяч товарів, програма буде гальмувати.

✅ Думка профі: "Мені треба часто перевіряти, чи існує цей ID? Я відразу зроблю з цього Set. Я жертвую трохи пам'яті заради шаленої швидкості".

🚫 Помилка новачка: Сподіватися, що set збереже порядок, у якому ви додавали елементи. Сюрприз: Ви додали А, Б, В, а отримали В, А, Б.

✅ Думка профі: "Якщо мені важливий порядок, я використаю Sorted Set (в базах даних) або просто відсортую список після очистки дублікатів".

6. 🧩 Підсумок

Отже, що ми маємо сьогодні в сухому залишку?

Sets (Множини) — це про унікальність. Ніяких клонів.
Вони супершвидкі для пошуку (завдяки магії хешування).
Sorted Sets додають до цього ще й порядок (рейтинги, черги).

Тепер ви вмієте не просто "складати дані в купу", а організовувати їх ефективно. Ви можете знайти спільне, відсіяти зайве і миттєво перевірити приналежність.

👀 Тизер: Ми говорили про "ключі" та "хешування". А що, якби ми могли до кожного ключа причепити ще й значення? Наприклад, не просто знати, що "Ivan" існує, а зберігати його номер телефону? Наступного разу ми розберемо Hash Tables (Словники/Dictionaries) — структуру, на якій тримається весь сучасний інтернет!

А поки що... це був CS50! 🖐️🎤