<jupyter_start><jupyter_text>Базовая имплементация на Numpy<jupyter_code>def qr(A):
    Q = A.copy()
    Q[:, 0] /= np.linalg.norm(Q[:, 0])
    for i in range(1, A.shape[0]):
        Q[:, i] -= Q[:, :i].dot(Q[:, :i].T).dot(Q[:, i])
        Q[:, i] /= np.linalg.norm(Q[:, i])
    R = Q.T.dot(A)
    return Q, R

def eigenvalues(A, rtol=1e-6, atol=1e-8):
    squared_A = np.square(A)
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        Q, R = qr(A)
        A = R.dot(Q)
        squared_A = np.square(A)
    return np.diag(A)

for n in n_values:
    result = make_experiment(eigenvalues, N=n)
    results.append(result)<jupyter_output><empty_output><jupyter_text>Попытка ускорения итерации на Numpy<jupyter_code>def make_iteration(A):
    Q = A.copy()
    Q[:, 0] /= np.linalg.norm(Q[:, 0])
    for i in range(1, A.shape[0]):
        Q[:, i] -= Q[:, :i].dot(Q[:, :i].T).dot(Q[:, i])
        Q[:, i] /= np.linalg.norm(Q[:, i])
    return Q.T.dot(A).dot(Q)

def eigenvalues(A, rtol=1e-6, atol=1e-8):
    squared_A = np.square(A)
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        A = make_iteration(A)
        squared_A = np.square(A)
    return np.diag(A)

for n in n_values:
    result = make_experiment(eigenvalues, N=n)
    results.append(result)<jupyter_output><empty_output><jupyter_text>Оптимизация вычисления функции на Numpy за счёт кэширования результатов<jupyter_code>def make_iteration(A):
    Q = A.T.copy()
    saved_Q = np.zeros_like(A)
    for i in range(A.shape[0]):
        Q[i] -= saved_Q.dot(Q[i])
        Q[i] /= np.linalg.norm(Q[i])
        saved_Q += np.outer(Q[i], Q[i])
    return np.linalg.multi_dot([Q, A, Q.T])

def eigenvalues(A, rtol=1e-6, atol=1e-8):
    squared_A = np.square(A)
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        A = make_iteration(A)
        squared_A = np.square(A)
    return np.diag(A)

for n in n_values:
    result = make_experiment(eigenvalues, N=n)
    results.append(result)<jupyter_output><empty_output><jupyter_text>Numba JIT<jupyter_code>from numba import jit

@jit(nopython=True)
def make_iteration(A):
    Q = A.T.copy()
    saved_Q = np.zeros_like(A)
    for i in range(A.shape[0]):
        Q[i] -= saved_Q.dot(Q[i])
        Q[i] /= np.linalg.norm(Q[i])
        saved_Q += np.outer(Q[i], Q[i])
    return Q.dot(A).dot(Q.T)

@jit(nopython=True)
def eigenvalues(A, rtol=1e-6, atol=1e-8):
    squared_A = np.square(A)
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        A = make_iteration(A)
        squared_A = np.square(A)
    return np.diag(A)

for n in n_values:
    result = make_experiment(eigenvalues, N=n)
    results.append(result)<jupyter_output><empty_output><jupyter_text>Numba JIT с дополнительными параметрами<jupyter_code>from numba import jit

@jit(nopython=True, nogil=True, fastmath=True, cache=True)
def make_iteration(A):
    Q = A.T.copy()
    saved_Q = np.zeros_like(A)
    for i in range(A.shape[0]):
        Q[i] -= saved_Q.dot(Q[i])
        Q[i] /= np.linalg.norm(Q[i])
        saved_Q += np.outer(Q[i], Q[i])
    return Q.dot(A).dot(Q.T)

@jit(nopython=True, nogil=True, fastmath=True, cache=True)
def eigenvalues(A, rtol=1e-6, atol=1e-8):
    squared_A = np.square(A)
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        A = make_iteration(A)
        squared_A = np.square(A)
    return np.diag(A)

for n in n_values:
    result = make_experiment(eigenvalues, N=n)
    results.append(result)<jupyter_output><empty_output><jupyter_text>Numba guvectorize<jupyter_code>from numba import guvectorize, float64

@guvectorize(["void(float64[:, ::1], float64, float64, float64[::1])"], "(n,n), (), () -> (n)", nopython=True, target='cpu')
def eigenvalues(A, rtol=1e-6, atol=1e-8, out=None):
    squared_A = A * A
    while squared_A.sum() - np.diag(squared_A).sum() >= rtol * squared_A.sum() + atol:
        Q = A.T.copy()
        Q[0] /= np.linalg.norm(Q[0])
        saved_Q = np.zeros_like(A)
        for i in range(A.shape[0]):
            Q[i] -= saved_Q.dot(Q[i])
            Q[i] /= np.linalg.norm(Q[i])
            saved_Q += np.outer(Q[i], Q[i])
        A = Q.dot(A).dot(Q.T)
        
        squared_A = A * A
    out[:] = np.diag(A)

def eigenvalues_wrapper(A, rtol=1e-6, atol=1e-8):
    result = np.empty(A.shape[0], dtype=float)
    eigenvalues(A, rtol, atol, result)
    return result

for n in n_values:
    result = make_experiment(eigenvalues_wrapper, N=n)
    results.append(result)
def f(x):
    return np.array(list(map(float, x.split()))) / 1000

gg = [
    f("0.069969 0.080002 0.070009 0.069989 0.07 0.069998 0.08"),
    f("0.309973 0.300028 0.309973 0.32003 0.30997 0.310007 0.299993"),
    f("3.00883 3.13567 3.20012 3.14 3.17999 3.11904 3.16399"),
    f("21.4515 21.4018 21.6 21.5061 21.14 21.8804 21.641"),
    f("29.7156 29.3104 29.7019 31.9827 30.4195 29.6241 31.0762"),
    f("87.9677 87.8141 87.8033 87.9801 88.7885 87.4791 86.9187"),
]
gg
names = ['Numpy 1', 'Numpy 2', 'Numpy 3', 'Numba JIT', 'Numba JIT с доп. пар.', 'Numba guvectorize', 'C++']
total_results = np.array(results + gg).reshape(len(names), len(n_values), -1) * 1000
R = pd.DataFrame(np.core.defchararray.add(np.core.defchararray.add(np.round(total_results.mean(axis=-1), 1).astype(str), " ± "), np.round(total_results.std(axis=-1), 1).astype(str)), index=names, columns=n_values)
R
for i, j in enumerate(np.round(total_results.mean(axis=-1), 1).argmin(axis=0)):
    R.iloc[j, i] = '\\textbf{' + R.iloc[j, i] + "}"
R
R[np.arange(10, 60, 10)].reset_index().to_csv("../report/tables/results.csv", sep=';', index=False)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18681318681318682, 'fraction_numerical': 0.05703819989534275, 'mean_word_length': 3.288706058339566, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '275017', 'license': 'MIT', 'n_tokens_mistral': 2719, 'n_tokens_neox': 2511, 'n_words': 451, 'path': 'experiments/EigenValues.ipynb', 'repo_name': 'CrafterKolyan/eigenvalues-speed-comparison', 'size': '5733'}