А/В эксперименты. Ускорение вычислений с помощью бакетизации

Введение

В современном мире больших данных и высокопроизводительных вычислений оптимизация времени выполнения алгоритмов играет ключевую роль. Одним из эффективных методов ускорения вычислений является бакетизация данных.

В данной статье мы рассмотрим, как бакетизация может существенно ускорить вычисления, и представим график зависимости отношения времени на расчеты без бакетизации к времени на расчеты с бакетизацией.

Что такое бакетизация?

Бакетизация — это процесс разделения общей выборки случайным образом на несколько подгрупп (buckets), которые затем анализируются отдельно. Этот метод широко используется в статистических исследованиях, особенно в A/B тестировании.

Процесс бакетизации

  1. Определяем каждому из N изначальных независимых наблюдений случайное число от 1 до M (M≤N), назовем это бакетом.

  2. Агрегируем по этим бакетам, считаем сумму метрики в каждом бакете, считаем количество наблюдений в каждом бакете, и теперь у нас независимое наблюдение — бакет.

Бакетизация 1 млн наблюдений в 200 наблюдений

Бакетизация 1 млн наблюдений в 200 наблюдений

Основные преимущества бакетизации включают:

  1. Снижение объема данных: Группировка данных уменьшает количество обрабатываемых элементов, что снижает нагрузку на память и процессор.

  2. Ускорение вычислений: Выполнение операций на уровне групп (бакетов) требует меньше времени по сравнению с выполнением тех же операций на уровне индивидуальных данных.

  3. Упрощение алгоритмов: Некоторые алгоритмы могут быть значительно упрощены при работе с агрегированными данными, что также способствует ускорению вычислений.

Методология

Для исследования эффективности бакетизации данных и её влияния на время выполнения вычислений мы провели симуляцию, в которой сравнили два подхода: индивидуальный (без бакетизации) и агрегированный (с бакетизацией). Вычисления производились в 1 поток.

Описание эксперимента

  1. Генерация данных:

  2. Бакетизация:

    • Данные были распределены по 1000 бакетам.

    • Для каждого бакета рассчитывались суммы и количество элементов.

  3. Симуляции:

    • Для обоих подходов (индивидуальный и агрегированный) мы провели t-тесты на различия между контрольной и экспериментальной группами.

    • В каждой симуляции использовалось 100 повторений для получения стабильных результатов.

  4. Измерение времени:

    • Время выполнения симуляций замерялось для каждого подхода, и затем рассчитывалось отношение времени выполнения индивидуального подхода к времени выполнения агрегированного подхода.

Результаты

Результаты эксперимента были визуализированы на графике зависимости отношения времени на расчеты без бакетизации к времени на расчеты с бакетизацией от количества наблюдений.

Зависимость отношения времени на расчеты без бакетизации к времени на расчеты с бакетизацией от количества наблюдений

Зависимость отношения времени на расчеты без бакетизации к времени на расчеты с бакетизацией от количества наблюдений

Анализ результатов

На графике видно, что отношение растет линейно с увеличением количества наблюдений. Это подтверждает гипотезу о том, что бакетизация позволяет значительно ускорить вычисления.

Получившиеся коэффициенты линейной регрессии:

  • Наклон (Slope): 1.69e-05

  • Сдвиг (Intercept): -5.38

  • Коэффициент детерминации (R-squared): 0.976

Эти результаты свидетельствуют о сильной линейной зависимости и высокой эффективности бакетизации для ускорения вычислений при увеличении объема данных.

Код:

  1. Импорт библиотек

    import numpy as np
    from scipy.stats import ttest_ind
    import time
    from tqdm import tqdm
    import plotly.graph_objects as go
    import scipy.stats as stats
    import warnings
    warnings.filterwarnings("ignore")
  2. Функция run_simulation:

    def run_simulation(control_group, treatment_group):
        """
        Выполняет t-тест для двух групп данных и возвращает p-значение.
    
        Args:
            control_group (array-like): Данные контрольной группы.
            treatment_group (array-like): Данные экспериментальной группы.
    
        Returns:
            float: p-значение t-теста.
        """
        _, p_value = ttest_ind(control_group, treatment_group)
        return p_value
  3. Функция run:

    • Генерирует данные.

    • Выполняет бакетизацию данных.

    • Проводит симуляции для обоих подходов (ind и agg).

    • Замеряет время выполнения симуляций и возвращает результаты в виде словаря.

    def run(n_obs, n_buckets, n_simulations):
        """
        Выполняет симуляции для сравнения времени выполнения расчетов с бакетизацией и без неё.
    
        Args:
            n_obs (int): Количество пользователей (размер данных).
            n_buckets (int): Количество бакетов для бакетизации.
            n_simulations (int): Количество повторений симуляций.
    
        Returns:
            dict: Словарь с временем выполнения для каждого подхода.
        """
        # Генерация данных
        data_ind = np.random.normal(10, 1, n_obs)
        
        # Бакетизация данных
        bucket_indices_control = np.random.randint(0, n_buckets, data_ind.size)
        bucket_sums_control = np.bincount(bucket_indices_control, weights=data_ind, minlength=n_buckets)
        bucket_counts_control = np.bincount(bucket_indices_control, minlength=n_buckets)
        data_agg = bucket_sums_control / bucket_counts_control
    
        # Параметры для симуляций
        params = [
            ('ind', data_ind[:n_obs//2], data_ind[n_obs//2:]),
            ('agg', data_agg[:n_buckets//2], data_agg[n_buckets//2:])
        ]
        
        times = {}
        for param in params:
            start_time = time.time()
            for _ in range(n_simulations):
                run_simulation(param[1], param[2])
            elapsed_time = time.time() - start_time
            sim_type = 'Individual Data' if param[0] == 'ind' else 'Aggregated Data'
            times[sim_type] = elapsed_time
        return times
  4. Основной блок кода:

    • Определяет параметры эксперимента (размеры данных, количество бакетов и количество симуляций).

    • Запускает симуляции для каждого размера данных и сохраняет результаты.

    • Строит график зависимости отношения времени на расчеты без бакетизации к времени на расчеты с бакетизацией.

    • Добавляет линию тренда и аннотацию с результатами регрессии.

    • Настраивает макет графика и отображает его.

    # Параметры эксперимента
    ns_obs = np.linspace(10**4, 10**7, 100).astype(int)
    n_buckets = 1000
    n_simulations = 100
    
    results = {}
    for n_obs in tqdm(ns_obs, desc='Processing user counts'):
        results[n_obs] = run(n_obs, n_buckets, n_simulations)
        
    # Визуализация результатов с линией тренда
    ind_times = np.asarray([results[n]['Individual Data'] for n in ns_obs])
    agg_times = np.asarray([results[n]['Aggregated Data'] for n in ns_obs])
    ratio = ind_times / agg_times
    
    # Вычисление коэффициентов регрессии
    slope, intercept, r_value, p_value, std_err = stats.linregress(ns_obs, ratio)
    trendline = intercept + slope * ns_obs
    
    # Создание графика
    fig = go.Figure()
    fig.add_trace(go.Scatter(x=ns_obs, y=ratio, mode='markers+lines', name='Data Points'))
    
    # Добавление линии тренда
    fig.add_trace(go.Scatter(x=ns_obs, y=trendline, mode='lines', name='Trend Line',
                             line=dict(color='red', dash='dash')))
    
    # Форматирование текста аннотации с использованием экспоненциальной нотации
    stats_text = f"Slope: {slope:.2e}
    Intercept: {intercept:.2f}
    R-squared: {r_value**2:.3f}" # Добавление аннотации с результатами регрессии fig.add_annotation(x=ns_obs[-1], y=trendline[-1], text=stats_text, showarrow=True, font=dict(size=12), arrowhead=1, arrowsize=1, arrowwidth=2, arrowcolor='red', ax=20, ay=-30, bgcolor='white', bordercolor='black') # Настройка макета fig.update_layout( title='Comparison of Computation Times', xaxis_title='Number of Users', yaxis_title='Individual approach time / Aggregated approach time', plot_bgcolor='white', paper_bgcolor='white', font_color='black', width=1200, height=800, showlegend=True ) fig.show()

Вывод

Проведенное исследование показало, что бакетизация данных позволяет значительно ускорить вычисления. Отношение времени выполнения операций без бакетизации к времени выполнения с бакетизацией увеличивается линейно с ростом объема данных, что подтверждает высокую эффективность метода.

Применение бакетизации особенно полезно в задачах, связанных с обработкой больших объемов данных, где время выполнения вычислений играет критически важную роль. В условиях растущих требований к производительности этот метод может стать ключевым инструментом для оптимизации вычислений и повышения эффективности обработки данных.

Отдельная статья про сравнение мощности критериев с использованием бакетизации и без

© Habrahabr.ru