Самый быстрый способ перебора n-мерного массива произвольных экстентов?

Question

Самый быстрый способ перебора n-мерного массива произвольных экстентов?

В C ++ я хочу итерировать n-мерный массив с произвольными экстентами в диапазоне от min [n] до max [n] соответственно, сохраняя, соответственно, ординаты в ord [n].

То есть. общее решение для:

for (int x = 0; x < 10; x++)
for (int y = 3; y < 20; y++)
for (int z = -2; z < 5; z++)
...
doSomething(x, y, z ...)

Формы:

int min[n] {0,  3, -2 ...}
int max[n] {10, 20, 5 ...}
int ord[n] {0,  0,  0 ...};

int maxIterations = (max[0] - min[0]) * (max[1] - min[1]) * ....
for (int iteration = 0; iteration < maxIterations; iteration++)
doSomething(ord)
iterate(n, ord, min, max)

Самый быстрый алгоритм для iterate (), который я могу придумать:

inline void iterate(int dimensions, int* ordinates, int* minimums, int* maximums)
{
// iterate over dimensions in reverse...
for (int dimension = dimensions - 1; dimension >= 0; dimension--)
{

if (ordinates[dimension] < maximums[dimension])
{
// If this dimension can handle another increment... then done.
ordinates[dimension]++;
break;
}

// Otherwise, reset this dimension and bubble up to the next dimension to take a look
ordinates[dimension] = minimums[dimension];
}
}

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

Есть ли более быстрый алгоритм?

4

algorithm c++multidimensional-array n-dimensional optimization

Решение

Другие решения

Источник

Accepted Answer

Если вы не начнете делать что-то аналогичное Серые коды который изменит порядок вашего обхода (и, возможно, будет очень сложным), вы в значительной степени находитесь в точке, в которой он так же хорош, как и собирается. На самом деле, амортизированное время iterate уже O(1)при условии, что каждое измерение имеет минимум, который не равен его максимуму.

Худший случай, когда все d размеры имеют maximum = minimum + 1, То есть, любое другое приращение любого конкретного измерения будет перетекать в следующее измерение (я). Однако обратите внимание, что общее количество изменений цифр, необходимых для определенного измерения x (от 1 в d) является 2^(d + 1 - x) - 1, Это явно меньше чем 2^(d + 1 - x), Суммируя это по всем измерениям (1 через d) простая геометрическая сумма, которая дает 2^(d + 1) - 2 что явно меньше 2^(d + 1), Обратите внимание, что количество итераций 2^dи, следовательно, среднее время за итерацию является константой: 2^(d + 1) / 2^d = 2,

Если вам действительно нужно снизить скорость, вероятно, лучшее, что он получит, это низкоуровневые настройки:

Является ли число измерений известным и меньше, чем маленькое (скажем, 20 или меньше) постоянным? Тогда вы можете устранить for цикл, развернув цикл. Ваш компилятор может быть достаточно умен, чтобы сделать это уже, если он может сделать вывод, что dimensions является постоянным, или вам может потребоваться создать несколько версий iterate с постоянным размером или с петлей, развернутой вручную. (Вы можете использовать шаблоны, если хотите дать ему хороший API.)
Вы можете на самом деле избавиться от ваших проверок maxIterations / итераций в большой внешний цикл (тот, который имеет doSomething вызовите его) и позвольте вашей итеративной функции изменять логическое значение, когда у него заканчиваются измерения, которые он может увеличить. Это уменьшает ваш for цикл до while (keepGoing) { ... },
Передача массива структур с минимальным и максимальным значением каждого измерения может быть немного быстрее, но я ожидаю, что кэш почти полностью уменьшит преимущества.

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

3