Рассчитать сумму префикса

У меня есть следующий код для выполнения задачи сумма префикса:

  #include <iostream>
  #include<math.h>
  using namespace std;

  int Log(int n){
      int count=1;
      while (n!=0){
          n>>=1;
          count++;

      }
      return count;
  }
  int main(){
    int x[16]={39,21,20,50,13,18,2,33,49,39,47,15,30,47,24,1};
    int n=sizeof(x)/sizeof(int );
    for (int i=0;i<=(Log(n)-1);i++){
          for (int j=0;j<=n-1;j++){
              if (j>=(std::powf(2,i))){
                  int t=powf(2,i);
                  x[j]=x[j]+x[j-t];

              }
          }
     }
     for (int i=0;i<n;i++)
          cout<<x[i]<< "  ";

     return 0;
  }

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

Источник

3 ответа

Решение

Самый быстрый способ заставить ваш алгоритм работать: отбросить внешний for(i...) петля, вместо установки i до 0, и использовать только внутренний for (j...) петля.

int main(){
    ...
    int i=0;
    for (int j=0;j<=n-1;j++){
        if (j>=(powf(2,i))){
            int t=powf(2,i);
            x[j]=x[j]+x[j-t];
        }
    }
    ...
}

Или эквивалентно:

for (int j=0; j<=n-1; j++) {
    if (j>=1)
        x[j] = x[j] + x[j-1];
}

... который является интуитивно понятным способом суммирования префиксов, а также, вероятно, самым быстрым непараллельным алгоритмом.

Алгоритм Википедии разработан для параллельной работы, так что все дополнения полностью независимы друг от друга. Он считывает все значения, добавляет их, затем записывает их обратно в массив, все параллельно. В вашей версии, когда вы выполняете x[j]=x[j]+x[jt], вы используете x [jt], к которому вы только что добавили, t итерации назад

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

int main() {
    int x[16]={39,21,20,50,13,18,2,33,49,39,47,15,30,47,24,1};
    int y[16];
    int n=sizeof(x)/sizeof(int);

    for (int i=0;i<=(Log(n)-1);i++){
        for (int j=0;j<=n-1;j++){
            y[j] = x[j];
            if (j>=(powf(2,i))){
                int t=powf(2,i);
                y[j] += x[j-t];
            }
        }
        for (int j=0;j<=n-1;j++){
            x[j] = y[j];
        }
    }

    for (int i=0;i<n;i++)
        cout<<x[i]<< "  ";
    cout<<endl;
}

Примечание: вы можете использовать 1<<i вместо powf(2,i), для скорости. И, как упоминал ergosys, ваш Log() функция нуждается в работе; значения, которые он возвращает, слишком высоки, что не повлияет на результат частичной суммы в этом случае, но заставит это занять больше времени.

Источник

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

template <typename It, typename F, typename T>
inline void prescan(It front, It back, F op, T const& id) {
    if (front == back) return;
    typename iterator_traits<It>::value_type accu = *front;
    *front++ = id;
    for (; front != back; ++front) {
        swap(*front, accu);
        accu = op(accu, *front);
    }
}

Это соответствует стилю интерфейса алгоритмов стандартной библиотеки C++.

Чтобы использовать его из своего кода, вы можете написать следующее:

prescan(x, x + n, std::plus<int>());

Вы пытаетесь реализовать параллельную сумму префикса? Это имеет смысл только тогда, когда вы фактически распараллеливаете свой код. В настоящее время ваш код выполняется последовательно и не получает ничего от более сложной логики "разделяй и властвуй", которую вы, похоже, используете.

Кроме того, в вашем коде действительно есть ошибки. Самый важный из них:

for(int i=0;i<=(Log(n)-1);i++)

Здесь вы повторяете до floor(log(n)) - 1, Но псевдокод утверждает, что вам на самом деле нужно повторять до ceil(log(n)) - 1,

Кроме того, учтите это:

 for (int j=0;j<=n-1;j++)

Это не очень обычно. Обычно вы пишете такой код следующим образом:

for (int j = 0; j < n; ++j)

Обратите внимание, что я использовал < вместо <= и скорректировал границы от j - 1 в j, То же самое относится и к внешнему циклу, поэтому вы получите:

for (int i = 0; i < std::log(n); ++i)

Наконец, вместо std::powf, вы можете использовать тот факт, что pow(2, x) такой же как 1 << x (то есть используя тот факт, что операционная база 2 эффективно реализована как битовые операции). Это означает, что вы можете просто написать:

if (j >= 1 << i)
    x[j] += x[j - (1 << i)];
Источник

Я думаю, что std:: частичный_сум делает то, что вы хотите http://www.sgi.com/tech/stl/partial_sum.html

Источник
Другие вопросы по тегам