Оптимизировать суммирование массива (проблема подмножества) - PullRequest
Новая
       5

Оптимизировать суммирование массива (проблема подмножества)

3 голосов
/ 16 мая 2011

В самой горячей части моей программы (90% времени в соответствии с gprof) мне нужно сложить один массив A в другой B. Оба массива имеют размер 2 ^ n (n равно 18..24) и содержат целое число (для простоты на самом деле хранится элемент mpz_t или небольшой массив int). Правило суммирования: для каждого i в 0..2 ^ n-1 задайте B[i] = sum (A[j]), где j - битовый вектор, а j & ~ i == 0 (другими словами, k-й бит любого j может не будет установлен в 1, если k-й бит i не равен 1).

Мой текущий код (это тело самого внутреннего цикла) делает это за время 2 ^ (1,5 * n) сумм, потому что я буду повторять для каждого i на (в среднем) 2 ^ (n / 2) элементов А. 

  int A[1<<n]; // have some data
  int B[1<<n]; // empty
  for (int i = 0; i < (1<<n); i++ ) {
    /* Iterate over subsets */
    for (int j = i; ; j=(j-1) & i ) {
      B[i] += A[j];  /* it is an `sum`, actually it can be a mpz_add here */
      if(j==0) break;
    }
  }

Я уже упоминал, что практически любая сумма пересчитывается из значений, суммированных ранее. Предлагаю, может быть код, выполняющий ту же задачу во время n* 2^n сумм.

Моя первая идея заключается в том, что B[i] = B[i_without_the_most_significant_bit] + A[j_new]; где j_new - это только то, что j имеет самый значимый бит из i в состоянии «1». Это вдвое сокращает мое время, но этого недостаточно (по-прежнему часы и дни при реальном размере проблемы): 

  int A[1<<n];
  int B[1<<n];
  B[0] = A[0]; // the i==0 will not work with my idea and clz()
  for (int i = 1; i < (1<<n); i++ ) {
    int msb_of_i = 1<< ((sizeof(int)*8)-__builtin_clz(i)-1);
    int i_wo_msb = i & ~ msb;
    B[i] = B[i_wo_msb];
    /* Iterate over subsets */
    for (int j_new = i; ; j_new=(j_new-1) & i ) {
      B[i] += A[j_new];  
      if(j_new==msb) break; // stop, when we will try to unset msb
    }
  }

Можете ли вы предложить лучший алгоритм?

Дополнительное изображение, список i и j, суммированных для каждого i для n = 4: 

i  j`s summed
0  0
1  0 1
2  0 2
3  0 1 2 3
4  0 4
5  0 1 4 5
6  0 2 4 6
7  0 1 2 3 4 5 6 7
8  0                8
9  0 1              8 9
a  0 2              8 a
b  0 1 2 3          8 9 a b
c  0 4              8 c
d  0 1 4 5          8 9 c d
e  0 2 4 6          8 a c e
f  0 1 2 3 4 5 6 7  8 9 a b c d e f

Обратите внимание на сходство цифр

PS Магия MSB отсюда: Сброс старшего значащего бита в слове (int32) [C]

1 Ответ

4 голосов
/ 16 мая 2011

Разделяй и властвуй кого-нибудь?Сейчас не на месте. 

void sums(int *a, int n, int *b) {
  if (n <= 0) {
    *b = *a;
    return;
  }
  int m = 1 << (n - 1);
  sums(a, n - 1, b);
  sums(a + m, n - 1, b + m);
  for (int i = 0; i < m; i++) {
    b[m + i] += b[i];
  }
}
...