src/main/java/ru/dmitry/montecarlo/service/MonteCarloParallel.java - master - onequ1z/JavaCoursePaperTulSU

src/main/java/ru/dmitry/montecarlo/service/MonteCarloParallel.java
278 строк13 KB
tayno
Добавлена опциональная многопоточная реализация MonteCarlo
08 дек 2025, 09:24
08 дек 2025, 09:244cd7f31
package ru.dmitry.montecarlo.service;

import ru.dmitry.montecarlo.model.Figure;
import ru.dmitry.montecarlo.model.MonteCarloResult;
import ru.dmitry.montecarlo.model.Point;
import ru.dmitry.montecarlo.model.Rectangle;
import ru.dmitry.montecarlo.util.Stopwatch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.*;

/**
 * Многопоточная реализация оценки площади методом Монте-Карло.
 * Распределяет работу между несколькими потоками для ускорения вычислений.
 * <p>
 * Если количество потоков <= 1, автоматически использует однопоточную версию.
 */
public class MonteCarloParallel implements MonteCarloEstimator {
    private final Profiler profiler;
    private final int threads;

    /**
     * Создаёт экземпляр MonteCarloParallel с заданным количеством потоков.
     *
     * @param threads количество потоков для параллельного выполнения (если <= 1, используется однопоточная версия)
     */
    public MonteCarloParallel(int threads) {
        this(threads, new Profiler(false));
    }

    /**
     * Создаёт экземпляр MonteCarloParallel с заданным количеством потоков и профилировщиком.
     *
     * @param threads  количество потоков для параллельного выполнения
     * @param profiler профилировщик для измерения производительности (может быть null)
     */
    public MonteCarloParallel(int threads, Profiler profiler) {
        this.threads = threads;
        this.profiler = profiler != null ? profiler : new Profiler(false);
    }

    /**
     * Оценивает площадь заданной фигуры с помощью многопоточного метода Монте-Карло.
     * <p>
     * Работа распределяется между потоками: каждый поток обрабатывает часть от общего количества N.
     * Результаты безопасно объединяются в конце.
     * <p>
     * Если threads <= 1, используется однопоточная версия для избежания накладных расходов.
     *
     * @param figure    геометрическая фигура, площадь которой оценивается
     * @param rectangle ограничивающий прямоугольник, содержащий фигуру
     * @param n         количество случайных выборок (испытаний)
     * @param rng       генератор случайных чисел (используется для создания seed для каждого потока)
     * @return результат оценки методом Монте-Карло
     * @throws IllegalArgumentException если figure, rectangle или rng равны null
     */
    public MonteCarloResult estimateArea(Figure figure,
                                         Rectangle rectangle,
                                         long n,
                                         Random rng) {
        if (figure == null) {
            throw new IllegalArgumentException("Figure не может быть null");
        }
        if (rectangle == null) {
            throw new IllegalArgumentException("Rectangle не может быть null");
        }
        if (rng == null) {
            throw new IllegalArgumentException("Random generator не может быть null");
        }

        if (n <= 0) {
            return new MonteCarloResult(0L, 0L, 0.0, 0.0, 0L);
        }

        // Если потоков <= 1, используем однопоточную версию
        if (threads <= 1) {
            MonteCarlo singleThreaded = new MonteCarlo(profiler);
            return singleThreaded.estimateArea(figure, rectangle, n, rng);
        }

        Stopwatch sw = new Stopwatch();
        sw.start();

        if (profiler.isEnabled()) {
            profiler.startOperation("MonteCarloParallel.estimateArea");
        }

        ExecutorService executor = null;
        try {
            // Получаем границы прямоугольника
            double[] bounds = rectangle.getBounds();
            double minX = bounds[0];
            double maxX = bounds[1];
            double minY = bounds[2];
            double maxY = bounds[3];

            // Разделяем работу между потоками
            long samplesPerThread = n / threads;
            long remainder = n % threads;

            executor = Executors.newFixedThreadPool(threads);
            List<Future<Long>> futures = new ArrayList<>(threads);

            // Получаем базовый seed для создания детерминированных seed'ов для потоков
            // Используем nextLong() для получения значения из генератора, но это не идеально детерминировано
            // Для полной детерминированности нужно передавать seed явно
            long baseSeed = rng.nextLong();

            // Создаём задачи для каждого потока
            for (int i = 0; i < threads; i++) {
                long threadSamples = samplesPerThread;
                if (i < remainder) {
                    threadSamples++; // Распределяем остаток по первым потокам
                }

                // Создаём детерминированный seed для каждого потока
                long threadSeed = createThreadSeed(baseSeed, i);

                Future<Long> future = executor.submit(new WorkerTask(
                        figure, minX, maxX, minY, maxY, threadSamples, threadSeed));
                futures.add(future);
            }

            // Собираем результаты
            long totalHits = 0L;
            for (Future<Long> future : futures) {
                try {
                    totalHits += future.get();
                } catch (InterruptedException | ExecutionException e) {
                    shutdownExecutor(executor);
                    throw new RuntimeException("Ошибка при выполнении параллельных вычислений", e);
                }
            }

            shutdownExecutor(executor);

            // Вычисляем оценку площади
            double rectArea = rectangle.area();
            double estimatedArea = calculateEstimatedArea(rectArea, totalHits, n);

            // Вычисляем относительную ошибку
            double exactArea = figure.exactArea();
            double relativeErrorPercent = calculateRelativeError(estimatedArea, exactArea);

            long durationMillis = sw.stop();

            if (profiler.isEnabled()) {
                profiler.endOperation("MonteCarloParallel.estimateArea", sw);
            }

            return new MonteCarloResult(n, totalHits, estimatedArea, relativeErrorPercent, durationMillis);
        } catch (Exception e) {
            if (sw.isRunning()) {
                sw.stop();
            }
            if (executor != null) {
                shutdownExecutor(executor);
            }
            throw e;
        }
    }

    /**
     * Безопасно завершает работу ExecutorService.
     * Сначала пытается корректно завершить все задачи, затем принудительно останавливает при необходимости.
     *
     * @param executor ExecutorService для завершения
     */
    private void shutdownExecutor(ExecutorService executor) {
        if (executor == null) {
            return;
        }
        executor.shutdown();
        try {
            if (!executor.awaitTermination(60, TimeUnit.SECONDS)) {
                executor.shutdownNow();
                // Ждём ещё немного для завершения принудительно остановленных задач
                if (!executor.awaitTermination(10, TimeUnit.SECONDS)) {
                    // Логируем предупреждение, если executor не завершился
                    System.err.println("Предупреждение: ExecutorService не завершился в течение отведённого времени");
                }
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
            Thread.currentThread().interrupt();
        }
    }

    /**
     * Создаёт детерминированный seed для потока на основе базового seed.
     * Это обеспечивает воспроизводимость результатов при использовании одного и того же базового seed.
     * <p>
     * Использует простую формулу для создания уникальных seed'ов для каждого потока:
     * threadSeed = baseSeed ^ (threadIndex * largePrime)
     * <p>
     * Большое простое число (0x9E3779B97F4A7C15L) обеспечивает хорошее распределение seed'ов.
     *
     * @param baseSeed   базовый seed (обычно из основного генератора)
     * @param threadIndex индекс потока (0-based)
     * @return seed для потока
     */
    private long createThreadSeed(long baseSeed, int threadIndex) {
        // Создаём детерминированный seed для каждого потока
        // Используем большое простое число для хорошего распределения
        return baseSeed ^ (threadIndex * 0x9E3779B97F4A7C15L);
    }

    /**
     * Вычисляет оценку площади на основе доли попаданий.
     *
     * @param rectArea площадь ограничивающего прямоугольника
     * @param hits     количество попаданий
     * @param n        общее количество испытаний
     * @return оценка площади фигуры
     */
    private double calculateEstimatedArea(double rectArea, long hits, long n) {
        return rectArea * ((double) hits / (double) n);
    }

    /**
     * Вычисляет относительную ошибку в процентах.
     *
     * @param estimatedArea оценка площади
     * @param exactArea     точная площадь
     * @return относительная ошибка в процентах (0.0, если exactArea = 0)
     */
    private double calculateRelativeError(double estimatedArea, double exactArea) {
        if (exactArea > 0.0) {
            return Math.abs(estimatedArea - exactArea) / exactArea * 100.0;
        } else {
            return 0.0;
        }
    }

    /**
     * Задача для выполнения в отдельном потоке.
     * Генерирует случайные точки и подсчитывает попадания в фигуру.
     */
    private static class WorkerTask implements Callable<Long> {
        private final Figure figure;
        private final double minX;
        private final double maxX;
        private final double minY;
        private final double maxY;
        private final long samples;
        private final long seed;

        WorkerTask(Figure figure, double minX, double maxX, double minY, double maxY,
                   long samples, long seed) {
            this.figure = figure;
            this.minX = minX;
            this.maxX = maxX;
            this.minY = minY;
            this.maxY = maxY;
            this.samples = samples;
            this.seed = seed;
        }

        @Override
        public Long call() {
            Random threadRng = new Random(seed);
            long hits = 0L;

            for (long i = 0; i < samples; i++) {
                double x = minX + threadRng.nextDouble() * (maxX - minX);
                double y = minY + threadRng.nextDouble() * (maxY - minY);
                Point p = new Point(x, y);
                if (figure.contains(p)) {
                    hits++;
                }
            }

            return hits;
        }
    }
}