Как улучшить работу с Python, используя блокировки?
1 ответ
Добро пожаловать в StackOverflow и поздравляем с первым вопросом!
Мне кажется, ваш вопрос заслуживает двух ответов:
- Как правильно использовать многопоточность.
- Один из способов ускорения суммирования целых чисел от 1 до N.
Как использовать многопоточность
В многопоточности всегда есть некоторые накладные расходы: создание потоков, блокировка и т. Д. Даже если эти накладные расходы действительно малы, некоторые накладные расходы останутся. Это означает, что многопоточность того стоит, только если у каждого потока есть существенная работа, которую нужно выполнить. Ваша функция почти ничего не делает внутри lock.acquire()/release(). Потоки сработали бы, если бы вы выполняли там более сложную работу. Но вы используете функцию блокировки правильно - это не очень хорошая проблема для многопоточности.
Быстрое суммирование 1..N
Измерение, измерение, измерение
Я использую Python 3.7, и у меня установлено pytest-benchmark 3.2.2. Pytest-benchmark запускает функцию для вас соответствующее количество раз и сообщает статистику по времени выполнения.
import threading
import pytest
def compute_variant1(N: int) -> int:
global sum_
global i
sum_ = 0
i = 1
lock = threading.Lock()
def thread_worker():
global sum_
global i
lock.acquire()
sum_ += i
i += 1
lock.release()
threads = []
for j in range(N):
threads.append(threading.Thread(target = thread_worker))
threads[-1].start()
for t in threads:
t.join()
return sum_
@pytest.mark.parametrize("func", [
compute_variant1])
@pytest.mark.parametrize("N,expected", [(10, 55), (30, 465), (100, 5050)])
def test_var1(benchmark, func, N, expected):
result = benchmark(func, N=N )
assert result == expected
Запустите это с: py.test --benchmark-histogram=bench И откройте сгенерированный bench.svg Он также печатает эту таблицу:
----------------------------------------------------------------------------------------------------- benchmark: 3 tests -----------------------------------------------------------------------------------------------------
Name (time in us) Min Max Mean StdDev Median IQR Outliers OPS Rounds Iterations
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_var1[10-55-compute_variant1] 570.0710 (1.0) 4,900.3160 (1.51) 658.8392 (1.0) 270.6056 (1.36) 602.5220 (1.0) 42.6373 (1.0) 19;82 1,517.8209 (1.0) 529 1
test_var1[30-465-compute_variant1] 1,701.2970 (2.98) 3,237.5830 (1.0) 1,879.8490 (2.85) 198.3905 (1.0) 1,802.5160 (2.99) 146.4465 (3.43) 59;43 531.9576 (0.35) 432 1
test_var1[100-5050-compute_variant1] 5,809.7500 (10.19) 13,354.3520 (4.12) 6,698.4778 (10.17) 1,413.1428 (7.12) 6,235.4355 (10.35) 766.0440 (17.97) 6;7 149.2876 (0.10) 74 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Упрощенные алгоритмы быстрее
Часто это действительно полезно сравнить быструю реализацию с самой простой.
Самая простая реализация, о которой я могу подумать - без использования трюков Python - это простой цикл:
def compute_variant2(N):
sum_ = 0
for i in range(1, N+1):
sum_ += i
return sum_
В Python есть функция с именем sum(), которая принимает список или любой итеративный как range(N):
def compute_variant3(N: int) -> int:
return sum(range(1, N+1))
Вот результаты (я удалил некоторые столбцы):
------------------------------------------------------- benchmark: 3 tests ------------------------------------------------
Name (time in us) Mean StdDev Median Rounds Iterations
---------------------------------------------------------------------------------------------------------------------------
test_var1[100-5050-compute_variant2] 4.2328 (1.0) 1.6411 (1.0) 4.1150 (1.0) 163106 1
test_var1[100-5050-compute_variant3] 4.7113 (1.11) 1.6773 (1.02) 4.5560 (1.11) 141744 1
test_var1[100-5050-compute_variant1] 6,404.1856 (>1000.0) 668.2502 (407.21) 6,257.6385 (>1000.0) 106 1
---------------------------------------------------------------------------------------------------------------------------
Как вы можете видеть variant1 на основе потоков намного, во много раз медленнее, чем последовательные реализации.
Еще быстрее, используя математику
Карл Фридрих Гаусс, когда он был ребенком 1 , заново открыл решение нашей проблемы в форме аклозы: N * (N + 1) / 2.
Это можно выразить в Python:
def compute_variant4(N: int) -> int:
return N * (N + 1) // 2
Давайте сравним это с другими быстрыми реализациями (я опущу первую реализацию):
И, как вы можете видеть из таблицы: последний вариант быстрее, и, что важно, не зависит от N .
---------------------------------------------------------------------------------------------------- benchmark: 12 tests -----------------------------------------------------------------------------------------------------
Name (time in ns) Min Max Mean StdDev Median IQR Outliers OPS (Kops/s) Rounds Iterations
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
var1[10-55-compute_variant4] 162.0100 (1.0) 1,053.6800 (1.0) 170.1799 (1.0) 32.5862 (1.0) 163.7200 (1.0) 8.1800 (1.59) 1135;1225 5,876.1353 (1.0) 58310 100
var1[13-91-compute_variant4] 162.1400 (1.00) 1,354.3200 (1.29) 181.5037 (1.07) 46.2132 (1.42) 176.1800 (1.08) 5.1500 (1.0) 2214;14374 5,509.5296 (0.94) 61452 100
var1[30-465-compute_variant4] 188.8900 (1.17) 1,874.2800 (1.78) 200.4983 (1.18) 40.8533 (1.25) 191.0000 (1.17) 9.8300 (1.91) 1245;1342 4,987.5732 (0.85) 51919 100
var1[100-5050-compute_variant4] 192.9091 (1.19) 5,938.7273 (5.64) 209.0628 (1.23) 75.8845 (2.33) 198.5455 (1.21) 10.9091 (2.12) 1879;4696 4,783.2508 (0.81) 194515 22
var1[10-55-compute_variant2] 676.1000 (4.17) 18,987.8000 (18.02) 719.4231 (4.23) 194.5556 (5.97) 689.0000 (4.21) 34.9000 (6.78) 1447;2199 1,390.0027 (0.24) 125898 10
var1[13-91-compute_variant2] 753.9000 (4.65) 12,103.8000 (11.49) 799.2837 (4.70) 201.3654 (6.18) 766.5000 (4.68) 38.1000 (7.40) 1554;3049 1,251.1203 (0.21) 124441 10
var1[10-55-compute_variant3] 1,021.0000 (6.30) 77,718.8000 (73.76) 1,157.6125 (6.80) 544.1982 (16.70) 1,098.2000 (6.71) 73.0000 (14.17) 3802;12244 863.8469 (0.15) 186672 5
var1[13-91-compute_variant3] 1,127.6000 (6.96) 44,606.4000 (42.33) 1,279.9332 (7.52) 476.7700 (14.63) 1,200.2000 (7.33) 90.0000 (17.48) 4022;21018 781.2908 (0.13) 172147 5
var1[30-465-compute_variant2] 1,304.7500 (8.05) 48,218.5000 (45.76) 1,457.3923 (8.56) 550.7975 (16.90) 1,385.7500 (8.46) 80.2500 (15.58) 3944;22221 686.1570 (0.12) 177086 4
var1[30-465-compute_variant3] 1,738.6667 (10.73) 86,587.3333 (82.18) 1,935.1659 (11.37) 762.7118 (23.41) 1,860.3333 (11.36) 128.6667 (24.98) 2474;6870 516.7516 (0.09) 176773 3
var1[100-5050-compute_variant2] 3,891.0000 (24.02) 181,009.0000 (171.79) 4,218.4608 (24.79) 1,721.8413 (52.84) 3,998.0000 (24.42) 210.0000 (40.78) 1788;2670 237.0533 (0.04) 171881 1
var1[100-5050-compute_variant3] 4,200.0000 (25.92) 76,885.0000 (72.97) 4,516.5853 (26.54) 1,452.5713 (44.58) 4,343.0000 (26.53) 210.0000 (40.78) 1204;2311 221.4062 (0.04) 153587 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------