Параллельное выполнение с собственным итератором - PullRequest
Новая
       46

Параллельное выполнение с собственным итератором

0 голосов
/ 18 апреля 2020

У меня есть простой код, который проверяет простоту большого числа, находя делители. Я пытаюсь сделать это параллельно, используя функцию std::none_of с политикой параллельного выполнения: 

BigInt isPrime(const BigInt &x) {
  BigInt i(0);
  BigIntRangeIterator range(2, x);
// If use std::vector, works fine:
// std::vector<BigInt> range;
// for (BigInt i(2); i < x; i = i + BigInt(1)) range.push_back(i);
  std::mutex m;
  std::none_of(std::execution::par_unseq, range.begin(), range.end()
              , [&](auto y) {
                  if (x % y == BigInt(0)) {
                    const std::lock_guard<std::mutex> lock(m);
                    i = y;
                    return true;
                  }
                  return false;
              }
  );
  return i;
}

Функция isPrime возвращает ноль, если число простое, в противном случае возвращается любой делитель числа x.

Чтобы не тратить место на хранение диапазона разделителей, я реализую собственный итератор для BigNum, который хранит только начальное, конечное и текущее значение и увеличивает его на единицу: 

/* Header file */
class BigIntRangeIterator
    : public std::iterator
    < std::forward_iterator_tag
    , BigInt
    , BigInt
    , const BigInt*
    , BigInt&
    >
{
  public:
    BigIntRangeIterator(): _begin(0), _end(0), _it(0){}
    BigIntRangeIterator(const BigInt &b, const BigInt &e)
      : _begin(b), _end(e), _it(b) {}

    bool operator!=(const BigIntRangeIterator &rhs) const;
    bool operator==(const BigIntRangeIterator &rhs) const;
    BigInt const & operator*() const;
    BigIntRangeIterator const & operator++();
    BigIntRangeIterator begin() const;
    BigIntRangeIterator end() const;

  private:
    BigInt _begin, _end, _it;
};

/*CPP file */
bool BigIntRangeIterator::operator!=(const BigIntRangeIterator &rhs) const {
  return _it != rhs._it;
}

bool BigIntRangeIterator::operator==(const BigIntRangeIterator &rhs) const {
  return _it == rhs._it;
}

BigInt const & BigIntRangeIterator::operator*() const {
  return _it;
}

BigIntRangeIterator const & BigIntRangeIterator::operator++() {
  _it = _it + BigInt(1);
  return *this;
}

BigIntRangeIterator BigIntRangeIterator::begin() const {
  return BigIntRangeIterator(_begin, _end);
}

BigIntRangeIterator BigIntRangeIterator::end() const {
  BigIntRangeIterator ret(_begin, _end);
  ret._it = _end;
  return ret;
}

My Проблема в том, что эта функция всегда выполняется в одном потоке, игнорируя политику параллельного выполнения. Почему он это делает?

1 Ответ

0 голосов
/ 18 апреля 2020

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

...