Использование таблиц Hash в Leu многомерного массива

Question

EDIT: Найденное решение! Как и комментаторы, использование memset - это безумно лучший подход. Замените весь цикл с

memset(lookup->n, -3, (dimensions*sizeof(signed char)));

где

long int dimensions = box1 * box2 * box3 * box4 * box5 * box6 * box7 * box8 * memvara * memvarb * memvarc * memvard * adirect * tdirect * fs * bs * outputnum;

Введение

Прямо сейчас, я смотрю на зверя для цикла:

for (j = 0;j < box1; j++) 
     { 
      for (k = 0; k < box2; k++) 
      { 
       for (l = 0; l < box3; l++) 
       { 
        for (m = 0; m < box4; m++) 
        { 
         for (x = 0;x < box5; x++) 
         { 
          for (y = 0; y < box6; y++) 
          { 
           for (xa = 0;xa < box7; xa++) 
           { 
            for (xb = 0; xb < box8; xb++) 
            { 
             for (nb = 0; nb < memvara; nb++) 
             { 
              for (na = 0; na < memvarb; na++) 
              { 
               for (nx = 0; nx < memvarc; nx++) 
               { 
                for (nx1 = 0; nx1 < memvard; nx1++) 
                { 
                 for (naa = 0; naa < adirect; naa++) 
                 { 
                  for (nbb = 0; nbb < tdirect; nbb++) 
                  { 
                   for (ncc = 0; ncc < fs; ncc++) 
                   { 
                    for (ndd = 0; ndd < bs; ndd++) 
                    { 
                     for (o = 0; o < outputnum; o++) 
                     { 
                      lookup->n[j][k][l][m][x][y][xa][xb][nb][na][nx][nx1][naa][nbb][ncc][ndd][o] = -3;  //set to default value 

                     } 
                    } 
                   } 
                  } 
                 } 
                } 
               } 
              } 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 

Задача

Этот цикл вызывается каждый цикл в главном прогоне для сброса значений в исходное состояние. К сожалению, для структуры программы необходимо, чтобы это множество значений хранилось в единой структуре данных.

Вот кикер: на каждые 60 секунд времени выполнения программы 57 секунд переходит на эту функцию только.

Вопрос

Мой вопрос заключается в следующем: будет ли хэш-таблицы будет подходящей заменой для линейного массива? Этот массив имеет мощность O (n^17), но хэш-таблицы имеют идеал O (1).

• Если да, то какую хэш-библиотеку вы бы порекомендовали? Эта программа находится в C и не имеет встроенной поддержки хеширования.
• Если нет, что бы вы рекомендовали вместо этого?
• Можете ли вы предоставить некоторый псевдокод о том, как вы думаете, что это должно быть реализовано?

Примечания

1. OpenMP использовалась в попытке Распараллеливать эту петлю. Многочисленные реализации привели лишь к значительному увеличению времени выполнения.
2. Использование памяти не является особой проблемой - эта программа предназначена для запуска на безумно высокоспециализированном компьютере.
3. Мы студенческие исследователи, соваться в доселе неизвестный мир оптимизации и распараллеливания - пожалуйста, медведь с нами, и спасибо за любую помощь

Answer 1

Hash против массива

Как уточнили комментарии, массив не должен быть проблемой здесь. Поиск в массиве с известным смещением равен O (1).

Узким

Мне кажется, что основная часть работы здесь (и причина, он медленный) является количество стрелочных де ссылок во внутреннем контуре.

Чтобы объяснить в немного более подробно рассмотрим myData[x][y][z] в следующем коде:

for (int x = 0; x < someVal1; x++) { 
    for (int y = 0; y < someVal2; y++) { 
     for (int z = 0; z < someVal3; z++) { 
     myData[x][y][z] = -3; // x and y only change in outer-loops. 
     } 
    } 
} 

Чтобы вычислить местоположение для -3, мы делаем поиск и добавить значение - один раз для myData[x], а затем снова до myData[x][y], и еще раз, наконец, для myData[x][y][z].

Поскольку этот поиск находится в самой внутренней части цикла, у нас есть избыточные чтения. myData[x] и myData[x][y] пересчитываются, даже если изменяется только значение z. Поиск выполнялся во время предыдущей итерации, но результаты не сохранялись.

Для вашей петли, Есть много слоев поисков вычисляемого каждую итерацию, даже тогда, когда только значение o меняется в этом внутреннем контуре.

Уточнения для Узкого

Для того, чтобы сделать один поиск, на итерацию цикла, на уровень петли, просто хранить промежуточный поиск. Использование int* как косвенность (хотя любой тип будет работать здесь), пример кода выше (с myData) стала бы:

int **a, *b; 
for (int x = 0; x < someVal1; x++) { 
    a = myData[x]; // Store the lookup. 
    for (int y = 0; y < someVal2; y++) { 
     b = a[y]; // Indirection based on the stored lookup. 
     for (int z = 0; z < someVal3; z++) { 
     b[z] = -3; // This can be extrapolated as needed to deeper levels. 
     } 
    } 
} 

Это просто пример кода, небольшие корректировки могут быть необходимы, чтобы получить его для компиляции (слепки и так далее). Обратите внимание, что, вероятно, нет никакого преимущества в использовании этого подхода с 3-мерным массивом. Однако для 17-мерного большого набора данных с простыми операциями с внутренним контуром (например, назначение) этот подход должен помочь совсем немного.

Наконец, я предполагаю, что вы фактически не назначаете значение -3. Вы можете использовать memset для достижения этой цели гораздо эффективнее.