Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

07.04.2025

Покращення split_tests

Поки я згадав про свою утиліту для розподілу тестових пакетів split_tests, захотілося її оптимізувати — тобто зробити так, щоб вона розділяла тести на комплекти найрівнішої тривалості.

На початку вона використовувала жадібний алгоритм. Сортуєш файли за зменшенням часу. А потім береш по черзі та додаєш до найменшого досі комплекту.

Це чудово, але всі знають, що жадібні алгоритми неефективні. Дослідив цю тему. Виявилося, що задача має назву планування ідентичних машин та вже має декілька розвʼязків. (Хоча і є NP-складною.)

Обрав алгоритм найбільшої різниці. Він теж поводиться жадібно, але оперує над цілими розподілами. Після генерації початкового стану, бере два найбільш нерівні розподіли та схрещує їх “один проти одного”, щоб різниці погасили одна одну. На заміну виходить новий, значно рівніший розподіл. Так продовжується, доки не залишиться тільки один, оптимальний розподіл.

А тепер те, з чого краще було почати. Виявилося, що навіть жадібний алгоритм давав розбіжність не більше 0.01%! Бачите, в пакеті є декілька жирнючих тестових файлів, але ж більшість інших тривають менше секунди. Тому жадібний алгоритм чудово порався з тим, щоб “законопатити проміжки”.

Мої ж розбіжності мали іншу причину: час виконання не є стабільним. Особливо для інтеграційних тестів. Тому як ти рівно не діли, а по факту коливання між збірками будуть значно більші, ніж виграш від зміни алгоритму. Тож варто спрямувати зусилля на збір статистики та обчислення більш впевнених метрик.

Втім, новий алгоритм причешу та опублікую: може, в когось інші обставини.