Програмування у телекомунікаціях та радіотехніці
Ст. викл. каф. 501,
Душепа Віталій Анатолійович
06.03.2023
Лекція 5
Page ▪ 1
Лекція 5
1. Поняття обчислювальної складності
2. Способи прискорення коду
3. Трохи про економію пам’яті
Page ▪ 2
Можемо безпосередньо виміряти час виконання:
Але розрахований таким чином час:
from time import time
�def my_sum(n):
total = 0
for i in range(n+1):
total += i
return total
�n = 10
t0 = time()
y = my_sum(n)
print(time()-t0)
1). Залежить від потужності комп’ютера
Тобто залежить від сторонніх факторів
Page ▪ 3
Ідея – просто порахувати кількість операцій
Домовимося что наступні операції займають однаковий час:
1). Математичні операції (+,-,*,/)
2). Порівняння (1 == 2)
3). Присвоєння (a=1)
4). Доступ до об’єктів у пам’яті (a[3])
Просто рахуємо кількість операцій
Page ▪ 4
Це вже краще (залежить лише від алгоритму, а не потужності обчислювача)
Но нам бы хотелось иметь более простой способ
Ідея – просто порахувати кількість операцій
Page ▪ 5
Залежність кількості операцій від вхідних параметрів
Page ▪ 6
1).
Что понимать под размером входных данных?
2).
def my_sum(n):
total = 0
for i in range(n+1):
total += i
return total
def my_sum(L):
total = 0
for i in L:
total += i
return total
Page ▪ 7
Ще один важливий момент
best
case
average
case
worst
case
def isStock(L1,a):
for e1 in L1:
if e1 == a:
return True
Пример
Цикл может закончиться как на первой итерации, так и на последней (в зависимости от входных значений).
Page ▪ 8
quadratic рано или поздно обгонит linear
Порядок росту функції (order of growth)
linear рано или поздно обгонит constant
Page ▪ 9
Порядок росту функції (order of growth)
Page ▪ 10
Позначення
Позначення О() (“велика О”)
при оцінці програми:
- описує найгірший випадок
- показує темпи росту в залежності від розміру входа
- оцінює алгоритм (а не потужність обчислювача)
Page ▪ 11
Більш математичне пояснення
Як математично перевірити, що дві функції мають однаковий порядок росту
Page ▪ 12
Приклади O() нотації
- відкидуємо множинник (константу)
По суті:
- залишаємо лише домінуючий член
Page ▪ 13
Приклади O() для програм
Page ▪ 14
Від низьких до високих
Page ▪ 15
Правила комбінування O()
Правило складання
- використовується для послідовних фрагментів коду
Приклад
Page ▪ 16
Правила комбінування O()
Правило перемноження
- використовується для вкладених конструкцій коду
Приклад
Page ▪ 17
Яка обчислювальна складність?
Питання 1
constant
logarithmic
linear
log-linear
polynomial
exponential
Page ▪ 18
Яка обчислювальна складність?
Питання 1
constant
logarithmic
linear
log-linear
polynomial
exponential
Page ▪ 19
Лекція 5
1. Поняття обчислювальної складності
2. Способи прискорення коду
3. Трохи про економію пам’яті
Page ▪ 20
У минулому розділі ми розлянули підходи для оцінки складності безпосередньо алгоритму
Як пришвидчити код
Для меншого часу виконання ми можемо:
- вища частота процесору
- багато ядер (якщо задача розпаралелюється)
- вектрні обчислення (замість циклів)
- інша мова програмування
Page ▪ 21
Векторизация циклов
Разные реализации алгоритма
Время выполнения:
Пример
Смоделируем вектор случайных чисел (N = 1 000 000 элементов). Необходимо вычислить сумму квадратов вектора
Формируем вектор
с помощью цикла
?
6.2189 (с)
поэлементное возведение в степень и функция sum
Время выполнения:
0.0410 (с)
векторное умножение
Время выполнения:
0.0053 (с)
1D – (nPoints,)
2D – (1, nPoints)
from numpy.random import rand
from time import time
�nPoints = 10**7
noise_vector = rand(nPoints)
t_start = time()
result = 0
for i in noise_vector:
result += i**2
time_1 = time() - t_start
print(time_1)
from numpy import sum
�t_start = time()
result = sum(noise_vector**2)
time_2 = time() - t_start
print(time_2)
from numpy import reshape
�t_start = time()
noise_vector_2D = reshape(noise_vector,
(1,nPoints))
result = noise_vector_2D @ noise_vector_2D.T
time_3 = time() - t_start
print(time_3)
Page ▪ 22
Использование numba
цикл с использованием numba
Время выполнения:
0.0593 (с)
Время выполнения:
6.2189 (с)
Разные реализации алгоритма
Смоделируем вектор случайных чисел (N = 1 000 000 элементов). Необходимо вычислить сумму квадратов вектора
Формируем вектор
?
from numpy.random import rand
from time import time
�nPoints = 10**7
noise_vector = rand(nPoints)
с помощью цикла
t_start = time()
result = 0
for i in noise_vector:
result += i**2
time_1 = time() - t_start
print(time_1)
import numba
�@numba.jit
def my_func(noise_vector):
result = 0
for i in noise_vector:
result += i**2
return result
�t_start = time()
result = my_func(noise_vector)
time_4 = time() - t_start
print(time_4)
Page ▪ 23
Що таке JIT
Преимущества
JIT (англ. Just-in-time compilation, компиляция «на лету»)
Компилируемые языки требуют строгой типизации
c= a+b
Часто використовують динамічну типизацію
Вікіпедія
Page ▪ 24
Використання numba
Бібліотека Numba використовує JIT
1. Дуже добре прискорює невеликі прості (цикли) фрагменти коду python
Часто, щоб гарно прискорити код його доводиться модифікувати, прописуючи типи даних для змінних
В цьому випадку, по суті, не потребує переписувати код
2. Не кожну функцію вона може прискорити. Складні функції, де одні й ті самі змінні можуть приймати дані різних типів (або специфічни типи даних зі сторонніх бібліотек), можуть навіть уповільнитися.
Page ▪ 25
Лекція 5
1. Поняття обчислювальної складності
2. Способи прискорення коду
3. Трохи про економію пам’яті
Page ▪ 26
Работа с памятью
1). Удаление ненужных переменных
del a, b, c
2). Использовать Numpy при работе с большими массивами
(самые простые советы)
Как посмотреть размер переменной?
Page ▪ 27