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

Question

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

  #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;
  } 

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

Answer 1

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

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)];

Answer 2

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

Answer 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 [j-t], вы используете x [j-t], к которому вы только что добавили 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() функция нуждается в работе; значения, которые он возвращает, слишком велики, что не повлияет на результат частичной суммы в этом случае, но сделает это дольше.