Изучение многопоточности. Пытался сделать поиск простых чисел - PullRequest
Новая
       6

Изучение многопоточности. Пытался сделать поиск простых чисел

0 голосов
/ 27 апреля 2018

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

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

Псевдокод выглядит так: 

for each core
  # new thread
  for i in (range / numberOfCores) * currentCore
    if !possiblePrimeIsntActuallyPrime
      if  possiblePrime % i == 0
        possiblePrimeIsntActuallyPrime = true
        return
    else
      return

Что работает, но 8 потоков, создаваемых для каждого возможного простого, похоже, замедляют работу системы.

Есть предложения по дальнейшей оптимизации?

1 Ответ

0 голосов
/ 27 апреля 2018

Использовать пул потоков.

Создание 8 потоков и сохранение их в массиве. Загрузите новые данные каждый раз, когда закончите, и начните снова. Это предотвратит их создание и уничтожение каждый раз.

Кроме того, при расчете диапазона проверяемых чисел проверяйте только до ceil(sqrt(N)), так как после этого гарантированно либо ничего не будет добавлено, либо другой соответствующий фактор уже проверен. то есть ceil(sqrt(24)) равно 5.

После того, как вы отметили 5, вам больше ничего не нужно проверять, потому что 6 входит в 24 4 раза, а 4 проверено, 8 - в 3 раза, 3 проверено и т. Д.

...