12
$\begingroup$

I would like to know what would be the most efficient way to shift numerical 2D arrays along its dimensions as follows:

(A = Partition[Range[9], 3])//TableForm

$$\left( \begin{array}{ccc} 1. & 2. & 3. \\ 4. & 5. & 6. \\ 7. & 8. & 9. \\ \end{array} \right)$$

(AR = PadLeft[A, {3, 4}][[All, ;; -2]]) // TableForm
(AL = PadRight[A, {3, 4}][[All, 2 ;;]]) // TableForm
(AD = PadLeft[A, {4, 3}][[;; -2, All]]) // TableForm
(AU = PadRight[A, {4, 3}][[2 ;;, All]]) // TableForm

$$\begin{align}AL&=\left( \begin{array}{ccc} 0. & 1. & 2. \\ 0. & 4. & 5. \\ 0. & 7. & 8. \\ \end{array} \right),& AR&=\left( \begin{array}{ccc} 2. & 3. & 0. \\ 5. & 6. & 0. \\ 8. & 9. & 0. \\ \end{array} \right),\\ AD&=\left( \begin{array}{ccc} 0. & 0. & 0.\\ 1. & 2. & 3. \\ 4. & 5. & 6. \\ \end{array} \right),& AU&=\left( \begin{array}{ccc} 4. & 5. & 6. \\ 7. & 8. & 9. \\ 0. & 0. & 0. \\ \end{array} \right). \end{align}$$

In this post a question of array rotation has been asked. I am asking for the efficient numerical shift. Actually, I need to achieve even a simpler goal of computing the sum

(B = AL + AR + AU + AD) // TableForm

$$\begin{align}B&=\left( \begin{array}{ccc} 6. & 9. & 8. \\ 13. & 20. & 17. \\ 12. & 21. & 14. \\ \end{array} \right) \end{align}.$$


In real application, the dimensions are not $3\times3$ but $201\times201$, and this operation needs to be performed repeatedly. As an answer, I am expecting some super efficient function ArraySpread defined as follows:

ArraySpread[a_?ArrayQ] := Module[{...},
  ....
  ]

such that

B=ArraySpread[A]

My current implementation:

ArraySpread[a_?ArrayQ] := Module[{al, ar, au, ad, dim},
  dim = Length[a];
  ar = PadLeft[a, {dim, dim + 1}][[All, ;; -2]];
  al = PadRight[a, {dim, dim + 1}][[All, 2 ;;]];
  ad = PadLeft[a, {dim + 1, dim}][[;; -2, All]];
  au = PadRight[a, {dim + 1, dim}][[2 ;;, All]];
  al + ar + ad + au
  ]

performs as

an = RandomReal[{0., 1.}, {201, 201}]
RepeatedTiming[ArraySpread[an]]

(*0.036*)

But can one achieve a better performance?

$\endgroup$
2
  • $\begingroup$ Some of you outputs show Real arrays, but all the inputs seem to be Integer arrays. $\endgroup$ – Michael E2 Jun 19 at 13:46
  • $\begingroup$ @MichaelE2 Good catch, in the process of typing I realized that for me only real case is of interest, but I overlooked that some results were obtained with the previous command. I will correct it now. $\endgroup$ – yarchik Jun 19 at 15:13
14
$\begingroup$

Here's an approach using ArrayPad. It's not a lot faster, but doesn't need the dimension to be explicitly determined:

ArraySpread2[a_] := ArrayPad[a, {{1, -1}, 0}] 
                  + ArrayPad[a, {{-1, 1}, 0}] 
                  + ArrayPad[a, {0, {1, -1}}]
                  + ArrayPad[a, {0, {-1, 1}}]

an = RandomReal[{0., 1.}, {201, 201}];
RepeatedTiming[ArraySpread[an];]
(* {0.023, Null} *)

RepeatedTiming[ArraySpread2[an];]
(* {0.020, Null} *)

After some tinkering with the parameters, here is another approach using ListConvolve that is more than 10 times faster:

ArraySpread3[a_] := ListConvolve[{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, {2, -2}, 0]

RepeatedTiming[ArraySpread3[an];]
(* {0.0017, Null} *)

ArraySpread[an] == ArraySpread2[an] == ArraySpread3[an]
(* True *)
$\endgroup$
3
  • $\begingroup$ Around 10% faster. Not bad! $\endgroup$ – yarchik Jun 19 at 9:16
  • $\begingroup$ @yarchik Now it's 10x faster :) $\endgroup$ – Lukas Lang Jun 19 at 9:22
  • 1
    $\begingroup$ Amazing, really amazing! I should not have forgotten the FFT approach. $\endgroup$ – yarchik Jun 19 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.