Генерация уникальных простых чисел из нескольких потоков в Java - PullRequest
Новая
       13

Генерация уникальных простых чисел из нескольких потоков в Java

0 голосов
/ 16 марта 2020

В этом коде ниже несколько потоков производителей иногда генерируют одинаковые простые числа. Как я могу гарантировать, что разные производители всегда генерируют уникальное простое число? 

public class UniquePrimes {


    private static BlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<Integer>(); 
    static ConcurrentHashMap<Integer, String> primesproduced = new ConcurrentHashMap<Integer, String>();

    public static void main(String[] args) {

        Scanner reader = new Scanner(System.in);
        System.out.print("Enter number of threads you want to create: ");
        int NOOFTHREADS = reader.nextInt();
        reader.close();

        ExecutorService executorPool = Executors.newFixedThreadPool(NOOFTHREADS);

        AtomicInteger currentPrime = new AtomicInteger();
        Runnable producer = () -> {
            String threadName = Thread.currentThread().getName();

            int p = 0;
            try {

                p = generateNextPrime(currentPrime.incrementAndGet());
                linkedBlockingQueue.put(p);
                primesproduced.put(p, threadName);
                System.out.println("Thread " + threadName + " produced prime number " + p);

            } catch (InterruptedException e) {

                e.printStackTrace();
            }
        };



        List<Runnable> tasks = new ArrayList<Runnable>();

        for (int i = 0; i < NOOFTHREADS; i++) {
            tasks.add(producer);

        }

        CompletableFuture<?>[] futures = tasks.stream().map(task -> CompletableFuture.runAsync(task, executorPool))
                .toArray(CompletableFuture[]::new);

        CompletableFuture.allOf(futures).join();
        executorPool.shutdown();

        System.out.println("\nTotal unique primes produced: " + primesproduced.size() + " and they are: ");


        System.out.print(
        primesproduced.entrySet().stream().filter(map -> map.getKey().intValue()>0).map(k -> "[" + k + "]").collect(Collectors.joining(",")));

        }
    }

    private static int generateNextPrime(int currentPrime) {    

        currentPrime++;
        if (currentPrime < 2) {
            currentPrime = 2;

            return currentPrime;

        }
        for (int i = 2; i < currentPrime; i++) {
            if (currentPrime % i == 0) {
                currentPrime++;
                i = 2;
            } else {
                continue;
            }
        }       
        return currentPrime;
    }
}

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

Спасибо за любую помощь.

1 Ответ

0 голосов
/ 16 марта 2020

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

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

value = atomicInt.addAndGet(1000);

добавляет 1000 к atomicInt и устанавливает value в значение atomicInt непосредственно перед успешным добавлением. Таким образом, вы можете рассматривать value как начало диапазона из 1000 целых чисел, назначенных текущей нити для поиска.

Еще один совет: посмотрите на Сито Эратосфена , если хотите лучшая производительность.

Я предполагаю, что вы делаете это как домашнее задание или учебное упражнение, поэтому я не буду его кодировать для вас.

...