9
$\begingroup$

I need to track some objects, the simplified version something like this

Clear[f];
list1 = Table[Table[f[u], {u, 0., t, 2 Pi/360}], {t, 0., 2 Pi, 2 Pi/10000}]; // AbsoluteTiming

list2 = Module[{L = {}, i = 0, dt = 2 Pi/360.}, Table[If[i dt <= t, AppendTo[L, f[dt i++]]];  L,
 {t, 0., 2 Pi, 2 Pi/10000}]]; // AbsoluteTiming

list1 == list2

{0.518511, Null}
{0.0090028, Null}
True

In my impression, AppendTo is often relatively slow. I prefer the first Table based solution, but here Table is much worse than AppendTo, and the AppendTo based solution is a bit complicated, is there a simple and efficient way?

Background
equilateral-triangle-inscribed-in-an-ellipse Using Table to track point $M$ is simple, however it will cause a lot of repetition calculations, so I consider using Appendto

  1. Table based approach
Manipulate[Module[{a = 3, b = 2, P, Q, R, M, sol, α}, 
P = {a*Cos[α], b*Sin[α]};
Q = {a*Cos[β], b*Sin[β]}; 
R = RotationTransform[-Pi/3, Q][P];
M = (P + Q + R)/3; 
sol := NSolve[Function[{x, y}, x^2/a^2 + y^2/b^2==1] @@ R && 0<=α<β<6*Pi, β, Reals][[1]]; 
α = α1; 
Graphics[{{Circle[{0, 0}, {a, b}]}, 
 {Point[Table[M /. sol, {α, 0., α1, 2*Pi/180}]]}, 
 {Opacity[0.2], Polygon[{P, Q, R}]}, Disk[M, 0.05]} /. sol,
 PlotRange -> 1.1*Max[a, b], Axes -> True]], {α1, 0, 2*Pi}]
  1. AppendTo based approach
    More smoothly, but it also has some issue, like excess trajectory are generated when the slider goes back.
Manipulate[Module[{a = 3, b = 2, P, Q, R, M, sol}, 
P = {a*Cos[α], b*Sin[α]}; 
Q = {a*Cos[β], b*Sin[β]}; 
R = RotationTransform[-Pi/3, Q][P]; 
M = (P + Q + R)/3;
sol = NSolve[Function[{x, y}, x^2/a^2 + y^2/b^2 == 1] @@ R && 0<=α<β<6*Pi, β, Reals][[1]];
Graphics[{{Circle[{0, 0}, {a, b}]}, {Point[AppendTo[L, M /. sol]]}, 
{Opacity[0.2], Polygon[{P, Q, R}]}, Disk[M, 0.05]} /. sol,
 PlotRange -> 1.1*Max[a, b], Axes -> True]], {L, {}, None}, {α, 0, 2*Pi},
 TrackedSymbols :> {α}]
$\endgroup$
5
  • 2
    $\begingroup$ What's the definition of f[u]? $\endgroup$
    – Chris K
    Apr 9, 2022 at 17:15
  • 2
    $\begingroup$ I guess you may clean the memory first. Also, you can use this syntax: Table[xxx,{x,0,n},{y,0,m}] $\endgroup$ Apr 9, 2022 at 17:21
  • 1
    $\begingroup$ @ChrisK I think it's not important here. $\endgroup$
    – matrix42
    Apr 10, 2022 at 10:43
  • $\begingroup$ Why not just calculate the full list Table[f[u], {u, 0., 2 Pi, 2 Pi/360}] once and truncate it as required at the point of use? $\endgroup$ Apr 10, 2022 at 13:02
  • $\begingroup$ @SimonWoods This is a good approach for simplified versions, but I'm not sure its performance in Manipulate(last example), I hope to compute in real time smoothly. $\endgroup$
    – matrix42
    Apr 10, 2022 at 15:00

2 Answers 2

13
$\begingroup$

Both codes construct of a list of lists.

In the first code, the list in each entry of the result is constructed by Table.

If the second code, the list in each entry of the results is construct by adding an element to the list of the previous entry. [Update: I probably should have added: The element is added to the previous entry, only when needed, which is not every iteration.]

I think it's clear that adding one element, even in a slightly expensive way, is faster than adding an average of 180 elements. The AppendTo method is not 180 times† faster; rather, it's more like 50 times faster.

Update: I forgot to account for the fact that AppendTo is not called every iteration. In fact AppendTo is called only 361 times in all, which results in $\left({361 \atop 2}\right)= 65341$ elements being copied or added to L over all the times it is updated. Table, OTOH, adds 1.8M elements to the sublists in all. There are also other slightly slow operations, the comparison i dt <= t that is done each iteration and i++. Against that is something that is faster: When L is added to the list being constructed via a pointer and is not copied; the only copying happens when AppendTo is called. The data structure we end up with in the second code takes up a significantly smaller memory. The smaller size also represents less work needed to construct it. Sorting out the significance of each of these effects is beyond me at this point.

Here's a test (ten times the size of the OP's codes) if you are unfamiliar with this aspect of Mathematica (or if, like me, you forgot about it for a while):

First code:

Quit[]

list1 = Table[
    Table[f[u], {u, 0., t, 2 Pi/360}], {t, 0., 2 Pi, 
     2 Pi/100000}]; // AbsoluteTiming
(*  {3.09715, Null}  *)

ByteCount@list1
(*  1308034520  *)

MemoryInUse[]
(*  1399784184  *)

Second code:

Quit[]

list2 = Module[{L = {}, i = 0, dt = 2 Pi/360.}, 
    Table[If[i dt <= t, AppendTo[L, f[dt i++]]]; 
     L, {t, 0., 2 Pi, 2 Pi/100000}]]; // AbsoluteTiming
(*  {0.055307, Null}  *)

ByteCount@list2
(*  1308034520  <-- roughly the same! *)

MemoryInUse[]
(*    93447328  <-- 1/15 of the amount in the list 1 case *)

Note ByteCount returns how much memory it would take to store the whole expression and does not account for shared points to identical sublists.

$\endgroup$
2
$\begingroup$

For another way to go about this, we may turn to look at the result and apply Counts:

list1 // Counts /* Values
(*
{28, 28, 28, 28, 27, 28, 28, 28, 27, 28, 28, 28, 28, 27, 28, 28, 28, \
27, 28, 28, 28, 28, 27, 28, 28, 28, 27, 28, 28, 28,<<301>>, 28, 27, 28,\
28, 28, 28, 27, 28, 28, 28, 27, 28, 28, 28, 28, 27, 28, 28, 28, 27, 28, \
28, 28, 28, 27, 28, 28, 28, 27, 1 }
*)

We see that this is quite regular and simply depends on the divisibility of $t$ by $\frac{2\pi}{360}$, i.e., the step for the inner range of $u$. We may thus use these multiplicities and apply them to the list of lists with the $f[\cdot]$ that is rather simple to construct. Note that the FoldList[ List /* Flatten ] in the code below works a bit like Accumulate.

list3 = With[
    {
        repetitions = #/(2 Pi/360) & /@ Range[0, 2 Pi, 2 Pi/10000] // Floor/*Counts/*Values,
        elements = { f[#] } & /@  Range[0., 2. Pi, 2. Pi/360] // FoldList[ List/*Flatten ]
    }
    ,
    Flatten[ MapThread[ ConstantArray, { elements, repetitions } ], 1 ]

]; //AbsoluteTiming
(* {0.0648518, Null} *)

MemoryInUse[]
(* 106073744 *)

list3 == list2
(* True *)

So this is about six times slower than the AppendTo solution on my machine. Unfortunately, we need to use infinite precision (e.g., not use real numbers) for the repetitions as slight rounding errors will make the solution not match completely (albeit the difference is marginal).

Instead of MapThread one can also use Inner with about the same speed:

Flatten[ Inner[ ConstantArray, elements, repetitions, List ], 1 ]
$\endgroup$
1
  • $\begingroup$ If one could live with the marginal differences by using real numbers for repetitions, then this approach turns out to be about as fast as the AppendTo approach. $\endgroup$
    – gwr
    Apr 10, 2022 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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