Skip to main content

performance tuning - 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?



Answer



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 Compile`GetElement 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 Compile`GetElement[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]

enter image description here


Comments

Popular posts from this blog

front end - keyboard shortcut to invoke Insert new matrix

I frequently need to type in some matrices, and the menu command Insert > Table/Matrix > New... allows matrices with lines drawn between columns and rows, which is very helpful. I would like to make a keyboard shortcut for it, but cannot find the relevant frontend token command (4209405) for it. Since the FullForm[] and InputForm[] of matrices with lines drawn between rows and columns is the same as those without lines, it's hard to do this via 3rd party system-wide text expanders (e.g. autohotkey or atext on mac). How does one assign a keyboard shortcut for the menu item Insert > Table/Matrix > New... , preferably using only mathematica? Thanks! Answer In the MenuSetup.tr (for linux located in the $InstallationDirectory/SystemFiles/FrontEnd/TextResources/X/ directory), I changed the line MenuItem["&New...", "CreateGridBoxDialog"] to read MenuItem["&New...", "CreateGridBoxDialog", MenuKey["m", Modifiers-...

How to thread a list

I have data in format data = {{a1, a2}, {b1, b2}, {c1, c2}, {d1, d2}} Tableform: I want to thread it to : tdata = {{{a1, b1}, {a2, b2}}, {{a1, c1}, {a2, c2}}, {{a1, d1}, {a2, d2}}} Tableform: And I would like to do better then pseudofunction[n_] := Transpose[{data2[[1]], data2[[n]]}]; SetAttributes[pseudofunction, Listable]; Range[2, 4] // pseudofunction Here is my benchmark data, where data3 is normal sample of real data. data3 = Drop[ExcelWorkBook[[Column1 ;; Column4]], None, 1]; data2 = {a #, b #, c #, d #} & /@ Range[1, 10^5]; data = RandomReal[{0, 1}, {10^6, 4}]; Here is my benchmark code kptnw[list_] := Transpose[{Table[First@#, {Length@# - 1}], Rest@#}, {3, 1, 2}] &@list kptnw2[list_] := Transpose[{ConstantArray[First@#, Length@# - 1], Rest@#}, {3, 1, 2}] &@list OleksandrR[list_] := Flatten[Outer[List, List@First[list], Rest[list], 1], {{2}, {1, 4}}] paradox2[list_] := Partition[Riffle[list[[1]], #], 2] & /@ Drop[list, 1] RM[list_] := FoldList[Transpose[{First@li...

functions - Get leading series expansion term?

Given a function f[x] , I would like to have a function leadingSeries that returns just the leading term in the series around x=0 . For example: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x)] x and leadingSeries[(1/x + 2 + (1 - 1/x^3)/4)/(4 + x)] -(1/(16 x^3)) Is there such a function in Mathematica? Or maybe one can implement it efficiently? EDIT I finally went with the following implementation, based on Carl Woll 's answer: lds[ex_,x_]:=( (ex/.x->(x+O[x]^2))/.SeriesData[U_,Z_,L_List,Mi_,Ma_,De_]:>SeriesData[U,Z,{L[[1]]},Mi,Mi+1,De]//Quiet//Normal) The advantage is, that this one also properly works with functions whose leading term is a constant: lds[Exp[x],x] 1 Answer Update 1 Updated to eliminate SeriesData and to not return additional terms Perhaps you could use: leadingSeries[expr_, x_] := Normal[expr /. x->(x+O[x]^2) /. a_List :> Take[a, 1]] Then for your examples: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x), x] leadingSeries[Exp[x], x] leadingSeries[(1/x + 2 + (1 - 1/x...