Тема: Трохи про оптимізацію
Знайомий студіозус мені наскаржився, що йому викладач безпідставно, на його думку, знизив оцінку. Задача: знайти мінімум, максимум і їхні індекси в масиві. Рішення знайомого: вводимо дві змінні - індекси мінімума і максимума, в циклі перебираємо весь масив, повертаємо індекси і самі мінімум і максимум (див. FindMinMax нижче - це мій код, але ідея та сама). Викладач вимагав створити ще дві змінні - для мінімума і максимума (див. FindMinMaxCached). Нормально пояснити студенту, чому, він не зміг; я пропоную таке пояснення: уявіть собі, що масив на магнітній стрічці, тоді перемотування до поточних мінімума і максимума перетворять алгоритм складності O(n) на щось типу O(n*log(n)). Але, заради цікавості, вирішив накидати код на Python і порівняти різні алгоритми.
Очікування:
t(FindMinMax) > t(FindMinMaxCached) > t(FindMinMaxPythonic) > t(FindMinMaxFast)
Результат:
All ok!
FindMinMax:
156.7342047
FindMinMaxCached:
153.25538239999997
FindMinMaxPythonic:
148.37255109999995
FindMinMaxFast:
155.92299950000006
Насправді:
t(FindMinMax) > t(FindMinMaxFast) > t(FindMinMaxCached) > t(FindMinMaxPythonic)
Як бачимо, варіант з зайвими змінними дійсно трохи швидший, хоча й незначно (завдяки, як я розумію, процесорному кешу, в якому зберігаються ті самі значення). Третій варіант - FindMinMaxPythonic- я додав, як демонстрацію неефективності "пітонячого" способу: спершу шукаємо min і max, а потім - їхні індекси. Все коротко і просто, щоправда, там має бути два зайвих цикли... але виходить найшвидше. Гадаю, це завдяки оптимізації стандартних функцій, треба буде порівняти з C++ чи асемблером на дозвіллі. Останній варіант - FindMinMaxFast - я планував як "покращений пітонячий спосіб": стандартної функції пошуку індексу максимального елемента немає, її доводиться формувати саме так, але це (думав я) буде швидше, ніж два цикли в FindMinMaxPythonic. Не так сталося, як гадалося - результат гірший навіть за варіант з 4-ма змінними.
Короткий висновок: без профайлінгу немає сенсу оптимізувати код по швидкості, а добре читаний код кращий за той, що видається швидким, але його важко читати.