Hugging Face's logo

geostalker80
/
comics

Model card Files
xet
 Community
comics
File size: 3,621 Bytes
a256f36
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from math import ceil, log
import time
import random
import numpy as np
import matplotlib.pyplot as plt

def add(A, B):
    A = np.asarray(A)
    B = np.asarray(B)
    return A + B

def subtract(A, B):
    A = np.asarray(A)
    B = np.asarray(B)
    return A - B

def joinQuadrants(q11,q12,q21,q22):
    top = np.concatenate((q11, q12), axis=1)
    bottom = np.concatenate((q21, q22), axis=1)
    joinedMatrix = np.concatenate((top, bottom), axis=0)

    return joinedMatrix


def strassen_matrix_multiply(A, B):
    n = len(A)

    if n <= 2:
        return classic_matrix_multiply(A, B)
    else:
        mid = n // 2

        a11 = A[0:mid, 0:mid]
        a12 = A[mid:n, 0:mid]
        a21 = A[0:mid, mid:n]
        a22 = A[mid:n, mid:n]

        b11 = B[0:mid, 0:mid]
        b12 = B[mid:n, 0:mid]
        b21 = B[0:mid, mid:n]
        b22 = B[mid:n, mid:n]

        m1 = strassen_matrix_multiply(add(a11, a22), add(b11, b22))
        m2 = strassen_matrix_multiply(add(a21, a22), b11)
        m3 = strassen_matrix_multiply(a11, subtract(b12, b22))
        m4 = strassen_matrix_multiply(a22, subtract(b21, b11))
        m5 = strassen_matrix_multiply(add(a11, a12), b22)
        m6 = strassen_matrix_multiply(subtract(a21, a11), add(b11, b12))
        m7 = strassen_matrix_multiply(subtract(a12, a22), add(b21, b22))

        c12 = add(m3, m5)
        c21 = add(m2, m4)
        c11 = subtract(add(add(m1, m4), m7), m5)
        c22 = subtract(add(add(m1, m3), m6), m2)

        C = joinQuadrants(c11,c12,c21,c22)

        return C

def classic_matrix_multiply(A, B):
    C = [[0 for row in range(len(A))] for col in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j] += A[i][k] * B[k][i]
    return C

def randomMatrix(n):
    return np.random.randint(100, size=(n, n))

def measure_time(n_values):
    strassen_times = []
    standard_times = []    
    for n in n_values:
        A = randomMatrix(n)
        B = randomMatrix(n)
        # Вимірюємо час для алгоритму Штрассена-Вінограда
        start_time = time.time()
        strassen_matrix_multiply(A, B)
        strassen_time = time.time() - start_time
        strassen_times.append(strassen_time)


        # Вимірюємо час для стандартного алгоритму множення
        start_time = time.time()
        classic_matrix_multiply(A, B)
        standard_time = time.time() - start_time
        standard_times.append(standard_time)

    return strassen_times, standard_times

# Число рядків матриць: 4, 16, 64, 256, 1024, 4096
n_values = [4, 16, 16, 64, 256, 1024, 4096]

strassen_times, standard_times = measure_time(n_values)

# Вивести результати у вигляді таблиці)
print("Розмір матриці (n) | Час виконання (с) (Strassen) | Час виконання (с) (Standard)")
print("-" * 65)
for i, n in enumerate(n_values):
  print(f"{n:<19} | {strassen_times[i]:<28.6f} | {standard_times[i]:.6f}")


# Побудова графіків
plt.figure(figsize=(10, 6))
plt.xscale('log', base=2)
plt.yscale('log', base=2)
plt.plot(n_values, strassen_times, label='Strassen Algorithm')
plt.plot(n_values, standard_times, label='Standard Algorithm')
plt.xlabel('log2(n) - Розмір матриці (n)')
plt.ylabel('log2(T(n)) - Час виконання (с)')
plt.legend()
plt.title('Порівняння алгоритмів множення матриць')
plt.grid(True)

# Відображення графіку
plt.show()