Нужно ли в любом случае проверить, равно ли n строк в строке матрицы в fortran?

Мне было интересно, если бы появился быстрый просмотр fortran по всем строкам maxtrix и определить, равно ли n число терминов.

Насколько я понял ваш проблема, это то, что вы хотите:

• функция с сигнатурой: (integer(:), integer) -> logical
• эта функция получает 1-D массив line и проверяет, есть ли любое значение, которое появляется как минимум n раз в массиве
• , функция не должна указывать , что или , сколько были этими значениями, их позиции или точное количество повторений

Существует много способов добиться этого. «Что является наиболее эффективным?» Это будет зависеть от конкретных условий ваших данных, системы, компилятора и т. д. Чтобы проиллюстрировать это, я вышел с тремя различными решениями. Конечно, все они дают правильный ответ. Вам рекомендуется проверить каждый из них (или любой другой, который вы придумали) с образцами ваших реальных данных.

---

Наивное решение # 1 - хорошие «полные петли»

Это алгоритм по умолчанию. Он перемещается line и сохраняет каждое значение в списке агрегатора packed, который имеет каждое отдельное значение, найденное до сих пор, и сколько раз они появлялись. В тот момент, когда любое значение достигает n повторений, fuction возвращает .true.. Если никакие значения не достигли n повторений, и больше нет возможности завершить предикат, он возвращает .false..

Я говорю defalut , потому что это минимальный linear (который я выяснил) на основе хороших петлей do. Это, вероятно, будет лучшим для общего случая, если у вас есть нулевая информация о характере данных, системе или даже специфике языка программирования. Агрегатор должен завершить функцию сразу после выполнения условия, но за счет дополнительного переполнения списка (по его длине). Если в данных много разных значений, а n велико, агрегатор становится слишком длинным, и поиск может стать дорогостоящей операцией. Кроме того, почти нет места для параллелизма, векторизации и других оптимизаций.

! generic approach, with loops and aggregator
pure logical function has_at_least_n_repeated(line, n)
  integer, intent(in) :: line(:), n
  integer :: i, j, max_repetitions, qty_distincts
  ! packed(1,:) -> the distinct integers found so far
  ! packed(2,:) -> number of repetitions of each distinct integer so far
  integer :: packed(2, size(line) - n + 2)

  if(n < 1 .or. size(line) == 0) then
    has_at_least_n_repeated = .false.
  else if(n == 1) then
    has_at_least_n_repeated = .true.
  else
    packed(:, 1) = [line(1), 1]
    qty_distincts = 1
    max_repetitions = 1
    i = 1
    ! iterate until there aren't enough elements left to reach n repetitions
    outer: do, while(i - max_repetitions <= size(line) - n)
      i = i + 1
      ! test for a match on packed
      do j = 1, qty_distincts
        if(packed(1, j) == line(i)) then
          packed(2, j) = packed(2, j) + 1
          if(packed(2, j) == n) then
            has_at_least_n_repeated = .true.
            return
          end if
          max_repetitions = max(max_repetitions, packed(2, j))
          cycle outer
        end if
      end do
      ! add to packed
      qty_distincts = qty_distincts + 1
      packed(:, qty_distincts) = [line(i), 1]
    end do outer
    has_at_least_n_repeated = .false.
  end if
end

---

Наивное решение # 2 - попытка некоторой векторизации

Этот подход пытается воспользоваться из arraysh -настройки Fortran и быстрых реализаций внутренних функций. Вместо внутреннего цикла do существует вызов встроенного count с аргументом массива, позволяющий компилятору выполнять некоторую векторию. Кроме того, если вы используете какой-либо инструмент для параллелизма или знаете, как работать с coarrays (и поддержкой вашего компилятора), вы можете использовать этот подход для их реализации.

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

! alternative approach, intrinsic functions without cache
pure logical function has_at_least_n_repeated(line, n)
  integer, intent(in) :: line(:), n
  Integer :: i

  if(n < 1 .or. size(line) == 0) then
    has_at_least_n_repeated = .false.
  else if(n == 1) then
    has_at_least_n_repeated = .true.
  else
    ! iterate until there aren't enough elements left to reach n repetitions
    do i = 1, size(line) - n + 1
      if(count(line(i + 1:) == line(i)) + 1 >= n) then
        has_at_least_n_repeated = .true.
        return
      end if
    end do
    has_at_least_n_repeated = .false.
  end if
end

---

Наивное решение # 3 - функциональный стиль

Это мой любимый (личные критерии). Мне нравятся функциональные языки, и мне нравится заимствовать некоторые аспекты этого в императивные языки. Этот подход делегирует вычисление внутренней вспомогательной рекурсивной функции. Здесь нет do петель. В каждом вызове функции только часть файла line передается как аргумент: более короткий массив, который пока не проверен. Нет необходимости в кэше.

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

Примечание: Fortran не разрешает вложенные процедуры в contains части основная программа. Чтобы он работал как представленный, вам нужно будет поместить функцию в модуль, подмодуль или сделать его внешней функцией. Другой вариант - извлечь вложенную функцию и сделать ее нормальной функцией в той же области.

! functional approach, auxiliar recursive function and no loops
pure logical function has_at_least_n_repeated(line, n)
  integer, intent(in) :: line(:), n

  if(n < 1 .or. size(line) == 0) then
    has_at_least_n_repeated = .false.
  else if(n == 1) then
    has_at_least_n_repeated = .true.
  else
    has_at_least_n_repeated = aux(line)
  end if

contains
  ! on each iteration removes all entries of an element from array
  pure recursive function aux(section) result(out)
    integer, intent(in) :: section(:)
    logical :: out, mask(size(section))
    integer :: left
    mask = section /= section(1)
    left = count(mask)
    if(size(section) - left >= n) then
      out = .true.
    else if(n > left) then
      out = .false.
    else
      out = aux(pack(section, mask))
    end if
  end
end

---

Заключение

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