lab01/task3_python.py - master - Konst_And/Labs_cpp

lab01/task3_python.py
73 строки4 KB
And Konst
move py files
05 мар 2026, 15:15
05 мар 2026, 15:152995f69
# Задание 3: часто встречающийся элемент

import matplotlib.pyplot as plt
import numpy as np

# Данные
sizes = np.array([100, 500, 1000, 5000, 10000, 50000, 100000, 500000, 1000000])

# Равномерное распределение
linear_uniform = np.array([1716, 5937, 10947, 48150, 98181, 468616, 932382, 4706088, 9607371])
strategyA_uniform = np.array([1708, 5519, 10154, 49459, 101224, 473142, 953035, 4664417, 9393788])
strategyB_uniform = np.array([1655, 6515, 9999, 49043, 94131, 470259, 914849, 4642236, 9436002])
strategyC_uniform = np.array([1903, 5527, 10988, 50343, 94193, 466832, 915330, 4581201, 9683887])

# Неравномерное распределение
linear_skewed = np.array([1715, 3427, 5950, 21053, 40554, 186254, 337049, 2146844, 4014337])
strategyA_skewed = np.array([2149, 4404, 7166, 22301, 43164, 204460, 372442, 2064309, 4306131])
strategyB_skewed = np.array([1854, 3858, 5272, 21597, 40239, 185583, 330199, 1979355, 4201616])
strategyC_skewed = np.array([1834, 3374, 4602, 21337, 41296, 184614, 349691, 2071244, 4085363])

def get_linear_fit(x, y):
    coeffs = np.polyfit(x, y, 1)
    return coeffs[0], coeffs[1]  # k, b

fig, axes = plt.subplots(2, 2, figsize=(14, 12))
axes = axes.flatten()

strategies = [
    ('Линейный поиск', linear_uniform, linear_skewed),
    ('Стратегия A (в начало)', strategyA_uniform, strategyA_skewed),
    ('Стратегия B (транспозиция)', strategyB_uniform, strategyB_skewed),
    ('Стратегия C (со счетчиками)', strategyC_uniform, strategyC_skewed)
]

colors = {'uniform': 'blue', 'skewed': 'red'}

for idx, (title, data_uniform, data_skewed) in enumerate(strategies):
    ax = axes[idx]
    
    k_uniform, b_uniform = get_linear_fit(sizes, data_uniform)
    k_skewed, b_skewed = get_linear_fit(sizes, data_skewed)
    
    ax.scatter(sizes, data_uniform, color=colors['uniform'], s=50, alpha=0.7, label='Равномерное (данные)')
    ax.scatter(sizes, data_skewed, color=colors['skewed'], s=50, alpha=0.7, label='Неравномерное (данные)')
    
    sizes_smooth = np.linspace(0, 1100000, 100)
    fit_uniform = k_uniform * sizes_smooth + b_uniform
    fit_skewed = k_skewed * sizes_smooth + b_skewed
    
    ax.plot(sizes_smooth, fit_uniform, '-', color=colors['uniform'], linewidth=2, 
            label=f'Равномерное: y = {k_uniform:.2e}x + {b_uniform:.2e}')
    ax.plot(sizes_smooth, fit_skewed, '-', color=colors['skewed'], linewidth=2,
            label=f'Неравномерное: y = {k_skewed:.2e}x + {b_skewed:.2e}')
    
    ax.set_xlabel('Размер массива (N)', fontsize=11)
    ax.set_ylabel('Время (мкс)', fontsize=11)
    ax.set_title(f'{title}', fontsize=13)
    ax.legend(fontsize=8)
    ax.grid(True, alpha=0.3, linestyle='--')

plt.suptitle('Зависимость времени поиска от размера массива\n', 
             fontsize=14, y=1.02)
plt.tight_layout()
#plt.savefig('task 3_frequent_element.png', dpi=300, bbox_inches='tight')
plt.show()

print(f"{'Стратегия':<25} {'Равномерное':<35} {'Неравномерное':<35}")
print("-" * 70)

for title, data_uniform, data_skewed in strategies:
    k_uniform, b_uniform = get_linear_fit(sizes, data_uniform)
    k_skewed, b_skewed = get_linear_fit(sizes, data_skewed)
    print(f"{title:<25} k = {k_uniform:<12.2e} b = {b_uniform:<12.2e}    k = {k_skewed:<12.2e} b = {b_skewed:<12.2e}")