# Can I generate a “piecewise” list from a list in a fast and elegant way?

Suppose we have a number list a:

n = 1000000;
a = RandomReal[{0, 1}, {n}];


We want to generate a list c with the same dimension of a and the relationship between the elements of a and c is:

$c[[i]] == 2 a[[i]] +3$

I think there will be no doubt that the best way to get this c is:

c = 2 a + 3


However, what if c is a "piecewise" list i.e. elements in different part of c are generated by different formula? For example, n/2 of the elements right in the middle of c are 0. while others still follow the formula above.

The most direct way I can think out is:

c1 = Table[If[n/4 + 1 <= i <= 3 n/4, 0., 2 a[[i]] + 3 ], {i, n}]; // AbsoluteTiming


{7.7380000, Null}

It's simple, but too slow.

While these 2 approaches are fast:

(c2 = 2 a + 3 ;
c2[[n/4 + 1 ;; 3 n/4]] = ConstantArray[0., {n/2}];) // AbsoluteTiming
(c3 = ConstantArray[0., {n}];
c3[[1 ;; n/4]] = 2 a[[1 ;; n/4]] + 3 ;
c3[[3 n/4 + 1 ;; -1]] = 2 a[[3 n/4 + 1 ;; -1]] + 3;) // AbsoluteTiming


{0.0760000, Null}

{0.0580000, Null}

But they are so dirty… And things will be worse when the dimension of the list becomes higher:

n=100;
b = RandomReal[{0, 1}, {n, n, n}]

d1 = Table[
If[n/4 + 1 <= i <= 3 n/4 && n/4 + 1 <= j <= 3 n/4 &&
n/4 + 1 <= k <= 3 n/4, 0., 2 b[[i, j, k]] + 3 ], {i, n}, {j,
n}, {k, n}]; // AbsoluteTiming
(d3 = ConstantArray[0., {n, n, n}];
d3[[1 ;; n/4]] = 2 b[[1 ;; n/4]] + 3;
d3[[3 n/4 + 1 ;; -1]] = 2 b[[3 n/4 + 1 ;; -1]] + 3;
d3[[n/4 + 1 ;; 3 n/4, 1 ;; n/4]] =
2 b[[n/4 + 1 ;; 3 n/4, 1 ;; n/4]] + 3;
d3[[n/4 + 1 ;; 3 n/4, 3 n/4 + 1 ;; -1]] =
2 b[[n/4 + 1 ;; 3 n/4, 3 n/4 + 1 ;; -1]] + 3;
d3[[n/4 + 1 ;; 3 n/4, n/4 + 1 ;; 3 n/4, 1 ;; n/4]] =
2 b[[n/4 + 1 ;; 3 n/4, n/4 + 1 ;; 3 n/4, 1 ;; n/4]] + 3;
d3[[n/4 + 1 ;; 3 n/4, n/4 + 1 ;; 3 n/4, 3 n/4 + 1 ;; -1]] =
2 b[[n/4 + 1 ;; 3 n/4, n/4 + 1 ;; 3 n/4, 3 n/4 + 1 ;; -1]] + 3;); // AbsoluteTiming


{12.8440000, Null}

{0.0930000, Null}

And a nightmare when the region are irregular:

f1 = Table[If[i^2 + j^2 + k^2 <= n^2, 0., 2 b[[i, j, k]] + 3 ],
{i, n}, {j, n}, {k, n}]; // AbsoluteTiming


{7.4530000, Null}

A fast f3 with the method shown in c3 and d3 is of course possible, but I'd like to skip it now.

So my question is, as the title said, is there an approach that's both elegant as c1 and fast as c3? Or at least not that slow as c1 and not that dirty as c3? Or, I can't have my cake and eat it too?

Well, to be honest, I knew that Compile together with Module can somewhat help (thanks for the help of @chyaong!):

c11 = Compile[{}, Module[{a = a, n = n},
Table[If[n/4 + 1 <= i <= 3 n/4, 0., 2 a[[i]] + 3], {i, n}]]][]; // AbsoluteTiming


{0.3590000, Null}

But I still look forward to a better solution: maybe a little greed?

I'd like to point out that, though I chose "$f(a)$ and $0$" to generate list in the example above for the sake of simplicity, this question is more general, the generated list may be formed by "$f(a)$ and $g(a)$", or even by "$f(a1,a2)$ and $g(a1,a2)$". Still, I appreciated and will appreciate those answers that focus on special cases since the "$f(a)$ and $0$" cases are simple but also common.

I added the tag "difference-equations" because this question generated when exploring finite difference method (FDM). I believe it's a inevitable issue when programming FDM.

Here are two existed post that can be optimized or answered with the outcome of this discussion:

How to discretize a nonlinear PDE fast?

How do I solve a PDE with a strange boundary condition?

• Is there always be 0 or f(a) or it is more general question? – Kuba Oct 26 '13 at 10:39
• @Kuba Well, I should say it's more general… maybe the new list is generated by $f(a)$ and $g(a)$, or even $f(a1, a2)$ and $g(a1, a2)$… – xzczd Oct 26 '13 at 11:43
• If you have a C compiler installed you can get better speed up by calling that compiler. See my updated answer. – RunnyKine Oct 26 '13 at 12:12
• c2[[n/4 + 1 ;; 3 n/4]] = 0. is OK, no need ConstantArray[0., {n/2}]. – chyanog Oct 26 '13 at 12:19

EDIT: chyaong says this doesn't auto-compile within Array in Mathematica 9 and is therefore much slower. My timings were performed in version 7.

This isn't going to be as fast as methods that compile to C, but using Function and Array provides a nice improvement and is very direct:

n = 100;
b = RandomReal[{0, 1}, {n, n, n}];

r1 =
Table[If[i^2 + j^2 + k^2 <= n^2, 0., 2 b[[i, j, k]] + 3], {i, n}, {j, n}, {k, n}];//
AbsoluteTiming

r2 =
Array[{i, j, k} \[Function] If[i^2 + j^2 + k^2 <= n^2, 0., 2 b[[i, j, k]] + 3], {n, n, n}];//
AbsoluteTiming

r1 === r2

{1.8391052, Null}

{0.2390137, Null}

True

• r2 is faster on v7, but on v9 about 15 times slower. – chyanog Oct 26 '13 at 16:14
• @chyaong That's surprising and disappointing! :-O Could you try setting SetSystemOptions["CompileOptions" -> {"ArrayCompileLength" -> 5}] and timing it again? I can't understand why this would be de-optimized in v9. – Mr.Wizard Oct 26 '13 at 16:32
• I just tried that，but the elapsed time almost the same, I also think it's very strange. – chyanog Oct 26 '13 at 16:42
• cf = Compile[{{n, _Integer}, {b, _Real, 3}}, Array[{i, j, k} \[Function] If[i^2 + j^2 + k^2 <= n^2, 0., 2 b[[i, j, k]] + 3], {n, n, n}]]; r2 = cf[n, b]; // AbsoluteTiming ,On v9, I found this would be two times faster than v7. – chyanog Oct 26 '13 at 16:54
• @chyaong Thanks. One shouldn't have to manually compile -- this is a regression that makes no sense to me. Since I'm (still!) not using v9 it doesn't seem appropriate for me to ask it, but I'd like to open a Question on this subject. Would you mind posting a question asking why this code doesn't auto-compile in v9? – Mr.Wizard Oct 26 '13 at 17:35
n = 10^6;
a = RandomReal[1, n];

First @ AbsoluteTiming @ MapIndexed[If[n/4 + 1 <= #2[[1]] <= 3 n/4, 0, #1] &, 2 a + 3];


3.390631

Well, we can speed this up dramatically by compiling to C:

pp = Compile[{{n, _Integer}, {a, _Real, 1}}, MapIndexed[If[n/4 + 1 <= #2[[1]] <= 3 n/4, 0., #1] &,
2 a + 3], CompilationTarget -> "C", RuntimeOptions -> "Speed"]


Then:

First @ AbsoluteTiming @ pp[n, a];


0.031226

• I'm sorry but this approach is even slower than my c1 and no simpler than it. – xzczd Oct 26 '13 at 11:49
• @xzczd. How about now? – RunnyKine Oct 26 '13 at 11:58
• About 3 times faster than my c11 now :). – xzczd Oct 26 '13 at 12:44
n = 2 10^6;
a = RandomReal[{0, 1}, {n}];
k = UnitStep[# - n/4 - 1]~BitAnd~UnitStep[3 n/4 - #] &@Range[n];

k2 = With[{n = n}, Compile[x, n/4 + 1 <= x <= 3 n/4 // Not // Boole,
RuntimeAttributes -> Listable]]@Range[n];

r1 = (2 a + 3) BitXor[k, 1] // Hash // AbsoluteTiming
r2 = (2 a + 3) k2 // Hash // AbsoluteTiming


{0.232013, 1123183045}

{0.189011, 1123183045}

n = 100;
b = RandomReal[{0, 1}, {n, n, n}];

With[{n = n, b = b},
Compile[{},
Table[If[i^2 + j^2 + k^2 <= n^2, 0., 2 b[[i, j, k]] + 3],
{i, n}, {j, n}, {k, n}]]][] // Hash // AbsoluteTiming

(k2 = With[{n = n},
Table[UnitStep[n^2 - (i^2 + j^2 + k^2)], {i, n}, {j, n}, {k, n}]];
(2 b + 3) BitXor[k2, 1] // Hash
) // AbsoluteTiming

(k3 = With[{n = n, k = Range@n},
Table[UnitStep[n^2 - (i^2 + j^2 + k^2)], {i, n}, {j, n}]];
(2 b + 3) BitXor[k3, 1] // Hash
) // AbsoluteTiming


{0.359021, 985443966}

{0.294017, 985443966}

{0.169010, 985443966}

• Also faster than my c11, but maybe a little hard to extend to more general cases? – xzczd Oct 26 '13 at 12:54

For the irregular region you can use

n = 100;
b = RandomReal[{0, 1}, {n, n, n}];

(2 b + 3) UnitStep[Outer[Plus, Range@n^2, Range@n^2, Range@n^2] - n^2] //
Hash // AbsoluteTiming


{0.084204, 6870340127317983824}

For comparison, chyaong's k3 returns

{0.101144, 6870340127317983824}

OK, now let me make use of the experience got from this answer.

With the help of CompilationTarget -> "C" and RuntimeOptions -> "Speed" (both are indispensable), the Table approach turns out to be the most elegant and fast and universal. The 1D case:

n = 10^6;
a = RandomReal[1, n];

pxz = Compile[{{n, _Integer}, {a, _Real, 1}},
Table[If[n/4 + 1 <= i <= 3 n/4, 0., 2 a[[i]] + 3], {i, n}],
CompilationTarget -> "C", RuntimeOptions -> "Speed"];

pxz[n, a]; // AbsoluteTiming

{0.0430000, Null}


Timings of other solutions in my machine:

(* RunnyKine's solution *)
pp[n, a]; // AbsoluteTiming
(* chyaong's two solutions *)
r1 = (2 a + 3) BitXor[k, 1] // Hash // AbsoluteTiming
r2 = (2 a + 3) k2 // Hash // AbsoluteTiming

{0.0970000, Null}
{0.0890000, 65118127}
{0.0850000, 65118127}


The CompileGetElement trick doesn't show its power in this simple 1D case, but when it comes to the 3D irregular region:

o = 2 10^2;
b = RandomReal[1, {o, o, o}];

(* ybeltukov's approach, notice the tiny change *)
(2 b + 3)(1 - UnitStep[Outer[Plus,Range@o^2, Range@o^2, Range@o^2]- o^2]); // AbsoluteTiming

pxz3d1 = Compile[{{n, _Integer}, {a, _Real, 3}},
Table[If[i^2 + j^2 + k^2 > n^2, 0., 2 a[[i, j, k]] + 3],
{i, n}, {j, n}, {k, n}],
CompilationTarget -> "C", RuntimeOptions -> "Speed"];

pxz3d2 = Compile[{{n, _Integer}, {a, _Real, 3}},
Table[If[i^2 + j^2 + k^2 > n^2, 0., 2 CompileGetElement[a, i, j, k] + 3],
{i, n}, {j, n}, {k, n}],
CompilationTarget -> "C", RuntimeOptions -> "Speed"];

AbsoluteTiming[pxz3d1[o, b];]
AbsoluteTiming[data = pxz3d2[o, b];]

{1.314000, Null}
{0.3870000, Null}
{0.2650000, Null}

Image3D[data]