Skip to main content

performance tuning - Lazy form of Tuples/Outer to loop over list of lists



This is less a question and more asking if someone has implemented this already, with more skill.


I need to perform the Outer-like generalized outer product of a list of lists (also a form of Tuples). I need to do it in a lazy way because the lists will become very large (many tens of thousands of elements).


I am using a Module to hold state as iterate over the products


loopOver[list0_]:=Module[
{len0,index,get,increment,isDoneQ,doneB},
len0=Length[list0];
Do[index[j]=1,{j,len0}];
doneB=False;
get[]:=Table[list0[[j,index[j]]],{j,len0}];
increment[]:=Block[

{stack,p},
If[doneB,Return[]];
stack={len0};
While[Length[stack]>0,
p=First@stack;
stack=Rest@stack;
index[p]=index[p]+1;
If[index[p]>Length[list0[[p]]],
(
If[p===1,doneB=True;Return[]];

index[p]=1;stack=Append[stack,p-1]
)
]
]
];
isDoneQ[]:=doneB;
{
"get"->get,
"increment"->increment,
"isDoneQ"->isDoneQ

}
]

And you use it as such:


Block[
{a, get, increment, isDoneQ},
a = {
{"11", "12", "13"},
{"21", "22"},
{"31"},

{"41", "42"}
};
{get,increment,isDoneQ}=loopOver[a][[All,2]];
While[!isDoneQ[],
Print[get[]];
increment[]
]
]

outputting the expected outer of 3*2*1*2=12 products:



{11,21,31,41}
{11,21,31,42}
{11,22,31,41}
{11,22,31,42}
{12,21,31,41}
{12,21,31,42}
{12,22,31,41}
{12,22,31,42}
{13,21,31,41}
{13,21,31,42}

{13,22,31,41}
{13,22,31,42}

Code review would be appreciated too. I hope my code is high on self documentation where it is low on performance and use of MMA functional coding style.



Answer



The implementation of lazy tuples here pretty much contains the solution to the lazy Outer problem. I will take the relevant parts from that code.


The following code constructs a function take, which would, given the start and end positions in the flat list of the resulting combinations, extract the elements:


ClearAll[next];
next[{left_, _}, dim_] :=
{left - dim*(# - 1), #} &[IntegerPart[(left - 1)/dim] + 1];


ClearAll[multiDims];
multiDims[dims_] := Rest @ Reverse @ FoldList[Times, 1, Reverse @ dims];

ClearAll[multiIndex];
multiIndex[pos_, dims : {__Integer}] :=
Rest@FoldList[next, {pos, 0}, multiDims@dims][[All, 2]]

ClearAll[take];
take[lists : {__List}, {start_, end_}] :=

With[{rend = Min[end, Times @@ Map[Length, lists]]},
Transpose @ MapThread[
Part,
{lists, multiIndex[Range[start, rend], Length /@ lists]}
]
];

For example,


take[{{1, 2, 3}, {4, 5, 6}}, {3, 7}] == Tuples[{{1, 2, 3}, {4, 5, 6}}][[3 ;; 7]]


(* True *)

The difference is of course, that take only computes those elements that have been requested, so can be used as a basis for a lazy implementation.


Here is then an implementation of an iterator, that would return consecutive combinations in chunks of specified length:


ClearAll[makeTupleIterator];
makeTupleIterator[lists:{__List}, chunkSize_Integer?Positive]:=
With[{len=Times @@ Length /@ lists},
Module[{ctr = 0},
If[ctr >= len,
{},

(* else *)
With[{taken = take[lists,{ctr+1, Min[ctr+chunkSize,len]}]},
ctr += Length[taken];
taken
]
]&
]
];

Here is an example: we construct an iterator with the chunk size of 10 elements:



iter = makeTupleIterator[{{"11", "12", "13"}, {"21", "22"}, {"31"}, {"41", "42"}}, 10];

Now we use it:


iter[]

(*
{
{"11","21","31","41"},
{"11","21","31","42"},
{"11","22","31","41"},

{"11","22","31","42"},
{"12","21","31","41"},
{"12","21","31","42"},
{"12","22","31","41"},
{"12","22","31","42"},
{"13","21","31","41"},
{"13","21","31","42"}
}
*)


iter[]

(* {{"13", "22", "31", "41"}, {"13", "22", "31", "42"}} *)

iter[]

(* {} *)

When we get an empty list, this tells us that the iterator has been exhausted.


This basically implements lazy tuples, and therefore also lazy Outer, more or less. You gain efficiency by picking large enough chunks, since chunk extraction (take function) is pretty fast, compared to the top-level iteration that would be needed to extract element by element.



Comments

Popular posts from this blog

plotting - How to draw lines between specified dots on ListPlot?

I would like to create a plot where I have unconnected dots and some connected. So far, I have figured out how to draw the dots. My code is the following: ListPlot[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4,13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full] I have thought using ListLinePlot command, but I don't know how to specify to the command to draw only selected lines between the dots. Do have any suggestions/hints on how to do that? Thank you. Answer One possibility would be to use Epilog with Line : ListPlot[ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4, 13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full, Epilog -> { Line[ ...

calculus and analysis - Integral of the Sinc product

Let us consider the following integral $$ B_n = \int_0^\infty \prod_{k=1,3,5,\dots}^n\frac{\sin (x/k)}{x/k}dx $$ By definition, Sinc[x] == Sin[x]/x , therefore B[n_?OddQ] := Integrate[Product[Sinc[x/k], {k, 1, n, 2}], {x, 0, Infinity}] B /@ Range[1, 13, 2] {Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2} OK, everything is fine. But... B[15] 467807924713440738696537864469 Pi/935615849440640907310521750000 What's going on? Answer As Eckhard wrote in comments B[n] is the n-th Borwein integral . (The letter B was not accidental :) ) This funny properties of Borwein integrals is related to the Fourier transform of Sinc function FourierTransform[Sinc[x], x, k] 1/2 Sqrt[Pi/2] (Sign[1 - k] + Sign[1 + k]) Plot[%, {k, -2, 2}, Filling -> 0] which is the box function. The result is $\pi/2$ while the sum $$ 1/3+1/5+\dots+1/n $$ B_n = \frac{\pi}{2} - \pi \bigg(\sum_{k=3,5,\ldots}^n\frac{1}{k} -1\biggr)^\frac{n-1}{2}\prod_{k=3,5,\dots}^n\frac{k}{k-1}. $$ For $n=15$ it is equal to $$ \frac{46780...

list manipulation - Selecting multiple columns from a matrix?

Sample data: data = { {{2013, 1, 1}, 24.13, 167.67, 231.82}, {{2013, 1, 2}, 32.15, 170.92, 225.99}, {{2013, 1, 3}, 35.43, 172.68, 221.67}, {{2013, 1, 4}, 36.73, 173.05, 218.32}, {{2013, 1, 5}, 58.19, 165.96, 197.05}, {{2013, 1, 6}, 69.99, 163.50, 187.52}, {{2013, 1, 7}, 71.37, 154.21, 175.58}, {{2013, 1, 8}, 72.51, 149.66, 163.25}}; I want a DateListPlot with three graphs, so for a matrix formed by columns 1 and 2, one for columns 1 and 3, and 1 for columns 1 and 4. At the moment I'm using this code: data2 = Transpose[{data[[All, 1]], data[[All, 2]]}]; data3 = Transpose[{data[[All, 1]], data[[All, 3]]}]; data4 = Transpose[{data[[All, 1]], data[[All, 4]]}]; DateListPlot[{data2, data3, data4}, Joined -> True, Filling -> {3 -> {1}}] but I have a hunch that this can be done more efficiently. I don't like the Transpose s in particular. Any ideas? edit (for extra credit) What if I need to multiply the second column by 2, which in my solution is simp...