Я не уверен, как именно адаптировать следующую технику к вашей проблеме, но если вы работали только в одном измерении, существует алгоритм O (k 3 log n) для вычисления n-го члена из серии. Это называется линейным повторением и может быть решено с использованием математической математики. Идея состоит в том, чтобы предположить, что у вас есть рецидив, определенный как
- F (1) = x_1
- F (2) = x_2
- ...
- F (k) = x_k
- F (n + k + 1) = c_1 F (n) + c_2 F (n + 1) + ... + c_k F (n + k)
Например, последовательность Фибоначчи определяется как
- F (0) = 0
- F (1) = 1
- F (n + 2) = 1 x F (n) + 1 x F (n + 1)
Есть способ просмотреть это вычисление как работающее с матрицей. В частности, предположим, что у нас есть вектор x = (x_1, x_2, ..., x_k) ^ T. Мы хотим найти матрицу А такую, что
Ax = (x_2, x_3, ..., x_k, x_ {k + 1}) ^ T
То есть мы начинаем с вектора слагаемых 1 ... k последовательности, а затем после умножения на матрицу A заканчиваем вектором слагаемых 2 ... k + 1 последовательности. Если затем умножить этот вектор на A, мы бы хотели получить
A (x_2, x_3, ..., x_k, x_ {k + 1}) ^ T = (x_3, x_4, ..., x_k, x_ {k + 1}, x_ {k + 2})
Короче говоря, учитывая k последовательных членов ряда, умножение этого вектора на A дает нам следующий член ряда.
Трюк использует тот факт, что мы можем сгруппировать умножения по A. Например, в вышеупомянутом случае мы умножили наш исходный x на A, чтобы получить x '(слагаемые 2 ... k + 1), затем умножили x «по A, чтобы получить x» (термины 3 ... k + 2). Однако вместо этого мы могли бы просто умножить x на A 2 , чтобы получить x '', вместо двух умножений матрицы. В более общем смысле, если мы хотим получить член n последовательности, мы можем вычислить A n x, а затем проверить соответствующий элемент вектора.
Здесь мы можем использовать тот факт, что матричное умножение ассоциативно, для эффективного вычисления A n . В частности, мы можем использовать метод повторного возведения в квадрат для вычисления A n в сумме O (log n) умножений матриц. Если матрица имеет размер k x k, то для каждого умножения требуется время O (k 3 ) для общей работы O (k 3 log n) для вычисления n-го члена.
Таким образом, все, что остается, - это на самом деле найти эту матрицу А. Ну, мы знаем, что мы хотим отобразить из (x_1, x_2, ..., x_k) в (x_1, x_2, ..., x_k, x_ {k) + 1}), и мы знаем, что x_ {k + 1} = c_1 x_1 + c_2 x_2 + ... + c_k x_k, поэтому получаем следующую матрицу:
| 0 1 0 0 ... 0 |
| 0 0 1 0 ... 0 |
A = | 0 0 0 1 ... 0 |
| ... |
| c_1 c_2 c_3 c_4 ... c_k |
Подробнее об этом см. В статье Википедии о решении линейных рекуррент с помощью линейной алгебры или моего собственного кода, который реализует описанный выше алгоритм.
Единственный вопрос сейчас заключается в том, как вы адаптируете это, когда работаете в нескольких измерениях. Конечно, это можно сделать, рассматривая вычисление каждой строки как ее собственную линейную повторяемость, а затем переходить к одной строке за раз. Более конкретно, вы можете вычислить n-й член первых k строк за O (k 3 log n), в общей сложности за O (k 4 log n) время до вычислить первые k строк. С этого момента вы можете вычислять каждую последующую строку в терминах предыдущей строки, повторно используя старые значения. Если есть n строк для вычисления, это дает алгоритм O (k 4 n log n) для вычисления окончательного значения, которое вас волнует. Если это мало по сравнению с работой, которую вы выполняли раньше (O (n 2 k 2 ), я считаю), это может быть улучшением. Поскольку вы говорите, что n порядка миллиона, а k около десяти, кажется, что это должно быть намного быстрее, чем наивный подход.
Тем не менее, я не удивлюсь, если бы существовал гораздо более быстрый способ решения этой проблемы, если бы не обрабатывать строку за строкой, а вместо этого использовать аналогичный матричный прием в нескольких измерениях.
Надеюсь, это поможет!