#course #algorithm #series

🧵Наскільки ефективний мій код? 4/8

O(n log n) – Лінійно-логарифмічна складність

Це оптимальна складність для більшості алгоритмів сортування. Ви не зможете стабільно сортувати швидше, ніж O(n log n), якщо не знаєте чогось специфічного про вхідні дані.

📌 Приклад: Сортування злиттям (Merge Sort)

function mergeSort($array) {
    if (count($array) <= 1) return $array;

    $middle = floor(count($array) / 2);
    $left = mergeSort(array_slice($array, 0, $middle));
    $right = mergeSort(array_slice($array, $middle));

    return merge($left, $right);
}

function merge($left, $right) {
    $result = [];
    while (count($left) && count($right)) {
        $result[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}

⛏️ Рекурсія ділить масив навпіл до базового випадку (елемент або два), після чого їх зливає у правильному порядку. Цей підхід дозволяє досягти складності O(n log n) — бо log n — це глибина рекурсії, а n — злиття всіх елементів на кожному рівні.

🧠 Якщо бачите рекурсію + злиття / обʼєднання / ітерацію — майже завжди це O(n log n).

У наступному пості — O(n^2) — і чому вкладені цикли часто погана ідея.

⬅️ Попередня складність | Наступна складність ➡️

#humor

Навіяно обговоренням в одному з PHP чатів

#game

Ранок
Сьогодні дуже легке поняття
Адепти Symfony тут?

👂🎉

І поки пʼєте каву та думаєте над ребусом, задонатьте на русоріз чи на будь який інший збір, щоб ми і далі могли просинатися в своїх домівках 💙💛

#talks

🏷 Чому канал називається саме так?

Кількість разів, коли мені ставили це запитання наближається до десятка, тому напишу пост, щоб не відповідати всім одне й те саме, а кидати посилання на нього.

Назва "Створений щоб помирати" — це не тролінг і не випадковий вираз.
Це відгук мого філософського ставлення до світу навколо: все має початок і кінець, і в цьому є назвичайна сила.

Колись ходила напівжартівлива але безумовно хейтерська фраза, що "PHP створений щоб померти". Її кидали в обличчя як образу: мовляв, мова не оптимізована, процеси неефективні, ресурси жере. І можливо десь так воно й було тоді, але це дійсно частина природи PHP: він створює процес, виконує роботу і помирає, вивільняючи ресурси. Як і розробники, адже людина не живе вічно, але доки існує — робить свою справу (гарно чи ні, це вже окрема справа).

Саме тому я вирішив назвати канал саме так. Не щоб знецінити PHP — а щоб перехопити контроль.
Є гарний приклад, який мені подобається, в фільмі 2010 року "Надто крута для тебе (She's Out of My League) був персонаж Венделл який сам себе називав "Засцика" (Stainer).
Він пояснює походження свого прізвиська так: в дитинстві він мав проблему — мочився в штани. Щоб уникнути знущань, він сам почав називати себе "Засцика", таким чином позбавляючи інших можливості образити його цим. Він перетворив колишню слабкість на ідентичність.

Так і з цією назвою — це прийняття. І трохи самоіронії. Але з любов’ю до цієї чудової мови програмування.

#course #algorithm #series

🧵Наскільки ефективний мій код? 5/8

O(n^2) – Квадратична складність

Це вже повільно. Алгоритми з O(n^2) мають вкладені цикли, і час виконання зростає квадратично відносно розміру вхідних даних.

📌 Приклад: Сортування бульбашкою (Bubble Sort)

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

👀 Кожен елемент перевіряється з кожним — от і квадратична складність. Якщо масив має 1000 елементів — буде до мільйона операцій.

⚠️ Будь-який вкладений цикл — тривожний дзвіночок. У реальному коді O(n^2) трапляється при порівнянні всіх з усіма: наприклад, фільтрація перетинів, дублікати, агрегації без індексів.

🧠 Часом уникнути O(n^2) не вийде, але щойно бачите подвійний цикл — варто хоча б запитати себе: а чи немає кращого способу?

📌 Завтра поговоримо про O(n^3) — кубічну складність. Це вже зовсім важка артилерія.

⬅️ Попередня складність | Наступна складність ➡️

#game

Новий ранок — новий ребус

💾📏

Нікому не побажаю на це наштовхуватися в проді

І якщо в тебе є 3 хвилини на каву і ребус, знайди 1 хвилину і зроби ранковий 🍩 на русо🔪, щоб кожен окупант отримав по дрону в пику

upd: другий смайл то лінійка

#course #php #php8_5 #talks #4students

А хіба current() та end() вже не справляються❓

На одній з персональних консультацій ми з одним з підписників обговорювали статтю про нововведення в PHP 8.5, зокрема появу функцій array_first() та array_last().
У нього виникло питання:

“А навіщо це потрібно, якщо є current() і end()?”

І раптом я подумав, що це питання може виникнути не тільки в нього, бо може здатися, що current() та end() роблять те саме.

Тому я вирішив написати короткий пост, щоб розкласти все по поличках 👇

Функції current() справді повертає перший елемент, а end() останній елемент масиву, але тільки після того, як зрушують внутрішній вказівник масиву. Це означає, що:

$array = ['a', 'b', 'c', 'd'];

echo current($array); // 'a'

echo next($array); // 'b'
echo current($array); // 'b', а не 'a'

echo end($array);     // 'd'
echo current($array); // 'd' а не 'a'

Тобто функція current() повертає не перший елемент масиву, а той, на який вказує вказівник, а end() останній елемент масиву, але при цьому переставляє на нього внутрішній вказівник масиву, що в свою чергу може привезти до непередбачуванних наслідків.
Концептуальний приклад:
Ми хочемо вивести всі елементи масиву, якщо останній елемент не "d"

$array = ['a', 'b', 'c'];

if (end($array) !== 'd') { // але вказівник вже перемістився на 'c'
    while ($item = current($array)) {
        echo $item . PHP_EOL;
        next($array);
    }
}

Але на екран виведеться тильки 'c'

✅ array_first() та array_last() — декларативні та передбачувані
Нові функції будуть завжди повертати перше або останнє значення без побічних ефектів.
Вони не змінюють стан вказівника і не залежать від нього:

$array = ['a', 'b', 'c'];

array_first($array); // 'a'
array_last($array);  // 'c'

// Незалежно від вказівника
next($array);
array_first($array); // все ще 'a'

📌 PHP продовжує розвиватися в бік декларативного і безпечного коду, і ці нові функції — це не "зайве", а ще один крок до меншої кількості багів.

Якщо помітили у себе в коді current() чи end() — можливо, час подивитись на них під новим кутом.

#course #algorithm #series

🧵Наскільки ефективний мій код? 6/8

O(n³) – Кубічна складність

Тут вже все дуже серйозно. Алгоритми з O(n³) використовують три вкладені цикли. Це означає, що при зростанні розміру даних, час виконання збільшується в кубі.

📌 Приклад: Множення двох матриць

function matrixMultiplication($matrixA, $matrixB) {
    $rowsA = count($matrixA);
    $colsA = count($matrixA[0]);
    $colsB = count($matrixB[0]);

    $result = [];
    for ($i = 0; $i < $rowsA; $i++) {
        for ($j = 0; $j < $colsB; $j++) {
            $result[$i][$j] = 0;
            for ($k = 0; $k < $colsA; $k++) {
                $result[$i][$j] += $matrixA[$i][$k] * $matrixB[$k][$j];
            }
        }
    }
    return $result;
}

📊 Звучить академічно, але трапляється частіше, ніж здається: в обчисленнях, побудові графів, пошуку комбінацій. Усе, що потребує порівняння трійок даних або тривимірних структур — кандидати на O(n³).

⚠️ Це вже критична точка. Якщо можете уникнути такого коду — уникайте. Часто можна знайти способи звести це до O(n²) або навіть O(n log n).

📌 Завтра поговоримо про O(2ⁿ) — експоненціальну складність. І це вже не жарти.

⬅️ Попередня складність | Наступна складність ➡️

#game #dictionary34

☕️ Доброго ранку!
Сьогодні в нас нова ранкова активність — «Три-чотири» 🧠

Правила прості:
🔹поясни поняття в трьох, максимум чотирьох словах
🔹можна правильно, а можна смішно
🔹кількість коментарів не обмежена
🔹кожну версію пиши в окремому коментарі

💬 Відповідь, що набере більше всього вподобайок увійде до словника, який я буду збирати!

🎯 Поняття дня:

Легасі код

По одній з версій, це:

Неясно як, але працює

👇 Пиши свою версію в коментарях.

---

🇺🇦 Якщо ти в тилу, закинь свої 2 гривні на ЗСУ в будь-який фонд, якому довіряєш!
Допоможи нашому війську стати сильнішим 💪

#course #algorithm #series

🧵Наскільки ефективний мій код? 7/8

O(2ⁿ) – Експоненціальна складність

Це вже абсолютна прірва. Зі зростанням обсягу вхідних даних час виконання алгоритму росте дуже швидко. Подвоїли вхід — подвоїли час. І з кожним наступним збільшенням ситуація тільки погіршується.

📌 Приклад: Обчислення чисел Фібоначчі наївним рекурсивним методом

function naiveFibonacci($n) {
    if ($n <= 1) return $n;
    return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
}

На перший погляд — все просто. Але з кожним викликом функція породжує два нових. І так далі, і далі… Пам’ятаєш кроликів 🐇 Фібоначчі? Ось вони, множаться як божевільні.

💡 У реальних проєктах рекурсивні алгоритми з експоненціальною складністю трапляються рідко, бо майже завжди є ефективніший підхід (динамічне програмування, кешування результатів).

⚠️ O(2ⁿ) — це червоний прапорець. Якщо ви бачите щось подібне у продакшені — час бити на сполох і шукати оптимізацію.

📌 Завтра поговоримо про фінальний босс: O(n!) — факторіальну складність. Таке не пробачається навіть тестових завданнях.

⬅️ Попередня складність | Наступна складність ➡️

#course #php #talks #4students #tips #tools

🧲 Один з інструментів DRY або єдиний дозволений copy/paste

Багато технічних співбесід показують, що розробники або не використовують трейти зовсім, або роблять це без розуміння практичного сенсу. Часто їх просто бояться — мовляв, поведінка трейту може бути неочевидною або ж спричинити баги, які складно відслідкувати.

Але суть в тому, що трейти — це всього лише інструмент, який треба застосовувати там, де від нього буде найбільше користі.

І найчастіше це не сервісні класи (хоча є ситуації коли і тут вони будуть доречні), а обʼєктні структури: сутності, DTO, VO, event'и тощо. Саме там трейти — ідеальний інструмент для роздачі типової поведінки без зайвої ієрархії і порушення DRY.

Гарний приклад — бібліотека knplabs/doctrine-behaviors. своїми інтерфейсами вона надає вашим сутностям типову поведінку (наприклад, Timestampable, SoftDeletable, Translatable тощо), але замість того, щоб реалізовувати інтерфейси в кожному класі, ви просто додаєте реалізацію — підключаючи відповідний трейт. Ніяких милиць у вигляді абстрактних батьківських класів, які «надають поведінку», тільки чистий код, лаконічний use TraitName і ніякого copy/paste

Хоча справедливості заради варто визнати: copy/paste все одно відбувається, просто не в коді, а на рівні інтерпретатора.

🎯 Висновок

Трейти — це спосіб дотримуватися DRY і не лізти в спадкування там, де воно недоречне. Це дуже потужний інструмент якщо використовувати його правильно і там де треба.

PS:
🧠 Порада: як зробити, щоб трейт гарантовано працював в будь-якому класі без помилок?

❗️ Ніколи не звертайтесь всередині трейту до властивостей або методів класу, в який трейт підключено. Трейт не знає, куди його вставлять — і тому контекст будь-якого трейту має бути самообмеженим. Це головна умова, щоб ваш трейт працював стабільно і не викликав помилки.

Погано:

trait BadTrait {
    public function generateUniqueId(): void 
    {
        $this->id = uniqid();
    }
}

Добре:

trait GoodTrait {
    protected string $id; 

    public function generateUniqueId(): void 
    {
        $this->id = uniqid();
    }
}

#game #dictionary34

☀️ Доброго ранку!
Граємо в «Три-чотири» 🧠

Правила тут

🎯 Поняття дня:

Middleware

По одній з версій, це:

Магія поза Гоґвортсом

👇 Пиши свою версію в коментарях.

---

🇺🇦 Ранок без донату на ЗСУ — як request без response.
🎯 Закинь свої 2 гривні у return — підтримай наших захистників! 💛💙

#course #algorithm #series

🧵Наскільки ефективний мій код? 8/8

O(n!) – Факторіальна складність

Це — вершина обчислювального кошмару. Факторіальна складність означає, що кількість операцій зростає як добуток усіх цілих чисел до n. Для n = 10 — це вже 3 628 800 варіантів. І так, усе це треба обробити.

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800

📌 Приклад: Генерація всіх можливих перестановок елементів

function permutations(array $items): array {
    if (count($items) <= 1) return [$items];

    $result = [];
    foreach ($items as $key => $item) {
        $remaining = $items;
        unset($remaining[$key]);
        foreach (permutations(array_values($remaining)) as $perm) {
            $result[] = array_merge([$item], $perm);
        }
    }
    return $result;
}

Цей код генерує всі можливі перестановки елементів масиву. І якщо їх 8 — то вже 40 320 варіантів. Це може виглядати невинно, поки не впаде прод у Black Friday.

📌 Факторіальна складність — це завжди крайній захід. Якщо задача передбачає перебір усіх варіантів, спершу шукайте апроксимацію, жадібний алгоритм або евристику.


🎬 На цьому серія завершується.
Якщо хочете ще серію подібну до цієї, пишіть в коментарях або в особисті.

⬅️ Попередня складність

#humor

Коли йдеш за трендами і вирішив розробити свою ML модель але єдина мова, яку ти знаєш — це PHP

#game #dictionary34

🌥 Ранок!
Забув написати відкладений пост, тому трохи із затримкою граємо в «Три-чотири» 🧠 (правила)

🎯 Поняття дня:

Фреймворк

По одній з версій, це:

Батько твого контролера

👇 Пиши свою версію в коментарях.

---
🕯Задонать свої 47 гривень на ЗСУ, щоб люди не гинули увісні від кацапських шахедів, що залетають в багатоповерхівки.

#game #dictionary34

🎂 Доброго ранку!
Граємо в «Три-чотири» 🧠 (правила)

🎯 Поняття дня:

Динамічна типізація

По одній з версій:

Тип змінюється як настрій

👇 Пиши свою версію в коментарях.

---
Мені сьогодні 4⃣2⃣, тому, у якості привітання, зкиньте 42 гривні на русоріз або на інший збір, якому ви довіряєте.

#game #dictionary34

🌄 Доброго ранку!
Після змушеної переви, продовжую

Граємо в «Три-чотири» 🧠 (правила)

🎯 Поняття дня:

Лямбда функція

По одній з версій:

Виконавець для колбеків

👇 Напиши свою смішну або правильну версію в коментарях.

---
🎯 Кожна твоя думка в коментарях — це плюс у словник, а кожен донат — плюс до нашої Перемоги. Підтримай ЗСУ!

#course #php #talks #4students #tips

🧮 Який в тебе масив — асоціативний чи індексований?

В PHP масив — це універсальний інструмент, який не вимагає від тебе визначати розмір, тип елементів чи навіть структуру ключів. Це з одного боку ніби і зручно, але з іншого — є проблемою.
Більшість мов програмування виділяють масиви (indexed arrays) і словники/мапи (associative arrays), а в PHP це одна й та ж сама структура, будь-який масив може стати асоціативним або нумерованим в залежності від ключів, які ти використовуєш:

$a = [1, 2, 3, 4, 5];  // індексований
$b = ['foo' => 6];     // асоціативний
$c = [
    ...$a,
    ...$b
];                     // змішаний

Часто виникає потреба по-різному обробляти масиви в залежності від їх типу. Але PHP не дає такої базової можливості, бо він взагалі не розрізняє індексовані та асоціативні масиви, про що прямо написано в документації.

Можна подумати, що array_is_list може допомогти зʼясувати хто є хто

array_is_list($a); // true  [0=>1, 1=>2, 2=>3, 3=>4, 4=>5]
array_is_list($b); // false [foo=>6]
array_is_list($c); // false [0=>1, 1=>2, 2=>3, 3=>4, 4=>5, foo=>6]

На перший погляд все добре, але ні.

Розширемо наш приклад, витягнемо з масиву $a тільки непарні числа

$a2 = array_filter($a, fn($x) => $x % 2 !== 0); // 1,3,5
array_is_list($a2); // false бо 0=>1, 2=>3, 4=>5

🙄 Що сталося з масивом? Невже він став асоціативним?

Ні. Просто array_filter зберігає оригінальні ключі. І хоч це все ще числові ключі, але через “дірки” в індексації array_is_list повертає false.
Тобто, PHP не ставить знак дорівнює між "нумерованим" та "індексованим" типами масивів.

Ще одна неприємність яка може вас очікувати: рядкові ключі — не гарантують “асоціативність”

Багато хто вважає, що якщо в масиві ключ рядковий — все, це асоціативний масив. Але якщо ключ виглядає як число, PHP конвертує його в int. Наприклад, штрихкоди товарів:

$products = [
    "0123456789052" => "Товар",
    "8018075001428" => "Ще товар"
];
print_r(array_keys($array));
//Array
//(
//    [0] => "0123456789052" 
//    [1] => 8018075001428 // -- рядок став числом
//)

Тому на ключі типу “рядок чи число” теж покладатися не можна.

Висновок:

Я бачив багато коду, де масив використовують як list, а потім раптово додають рядковий ключ — і все, data integrity накрилась. Якщо твоя логіка дійсно залежить від того, який у тебе масив — перевіряй не array_is_list, а реально структуру ключів (через array_keys, is_int, is_string і т.д.). А ще краще — не лінуйся типізувати і перевіряти дані на вході, навіть якщо це PHP.

Чи стикаєтеся ви в роботі з такими складностями і як з них виходите?