69 lines
2.2 KiB
Python
69 lines
2.2 KiB
Python
import multiprocessing as mp
|
|
import time
|
|
import random
|
|
|
|
def matrix_multiply_sequential(A, B):
|
|
n = len(A)
|
|
C = [[0] * n for _ in range(n)]
|
|
for i in range(n):
|
|
for k in range(n):
|
|
for j in range(n):
|
|
C[i][j] += A[i][k] * B[k][j]
|
|
return C
|
|
|
|
def multiply_chunk(args):
|
|
start, end, A, B = args
|
|
n = len(B)
|
|
C_part = [[0] * n for _ in range(end - start)]
|
|
for i in range(start, end):
|
|
for k in range(n):
|
|
for j in range(n):
|
|
C_part[i - start][j] += A[i][k] * B[k][j]
|
|
return (start, end, C_part)
|
|
|
|
def matrix_multiply_parallel(A, B, processes=1):
|
|
n = len(A)
|
|
if processes == 1:
|
|
return matrix_multiply_sequential(A, B)
|
|
|
|
chunk_size = n // processes
|
|
chunks = []
|
|
for i in range(processes):
|
|
start = i * chunk_size
|
|
end = n if i == processes - 1 else (i + 1) * chunk_size
|
|
chunks.append((start, end, A, B))
|
|
|
|
with mp.Pool(processes=processes) as pool:
|
|
results = pool.map(multiply_chunk, chunks)
|
|
|
|
C = [[0] * n for _ in range(n)]
|
|
for start, end, C_part in results:
|
|
for i in range(start, end):
|
|
C[i] = C_part[i - start]
|
|
return C
|
|
|
|
def generate_matrix(n):
|
|
return [[random.randint(1, 100) for _ in range(n)] for _ in range(n)]
|
|
|
|
if __name__ == '__main__':
|
|
sizes = [100, 300, 500]
|
|
processes_list = [1, 2, 4, 8]
|
|
|
|
for size in sizes:
|
|
A = generate_matrix(size)
|
|
B = generate_matrix(size)
|
|
print(f"\nРазмер матрицы: {size}x{size}")
|
|
|
|
# Последовательная версия
|
|
start_time = time.time()
|
|
matrix_multiply_sequential(A, B)
|
|
seq_time = time.time() - start_time
|
|
print(f"Последовательный алгоритм: {seq_time:.4f} сек")
|
|
|
|
# Параллельные версии
|
|
for processes in processes_list:
|
|
start_time = time.time()
|
|
matrix_multiply_parallel(A, B, processes)
|
|
par_time = time.time() - start_time
|
|
speedup = seq_time / par_time
|
|
print(f"Параллельный (процессы: {processes}): {par_time:.4f} сек (ускорение: {speedup:.2f}x)") |