Re: list manipulation
- To: mathgroup at smc.vnet.net
- Subject: [mg20639] Re: list manipulation
- From: "Atul Sharma" <atulksharma at yahoo.com>
- Date: Thu, 4 Nov 1999 02:13:44 -0500
- References: <7vm3ud$q8r@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
This is a good example of where built in list operations can be more
efficient than procedural code.
First, let's clean up the procedural code to identify those events[[i]]
which don't fall in any of the intervals in gaps i.e. If the list returned
by Select is empty, we will append that particular element to our new list
eout. You will need to explore whether using e instead of ei is actually
faster, as I find the results are sometimes counter intuitive, unlike the
case with compiled and rigidly typed languages.
tmp1={};
eout={};
max=Length[events];
Do[
tmp1={};
ei = events[[i]];
tmp1 = Select[ gaps,( #[[1]] <=ei && #[[2]] >= ei)&];
If[(tmp1=={}),AppendTo[eout,ei]],
{i, 1,max}
]
The Mathematica functions Interval returns an interval object when applied to a two element list:
intervalObject=Interval[1,5.5}];
IntervalMemberQ[intervalObject, 2.3]
Out[3]: True
Here's the trick. We want to turn your list gap into an interval object which encompasses the Union of all the intervals. Although 'the book' seems to imply that Interval[gaps] will do the trick, what you need to do is change the Head of gaps (which is List, if you use FullForm to view it) to Interval. We 'swap' heads using Apply.You will notice that some of the intervals are grouped together in the process, making for fewer comparisons.
gaps//FullForm
List[List[1,5.5],List[2,4.3],List[2.7,3.1],List[3.002,4.007],
List[10.001,10.007],List[10.101,11.001],List[11.007,12]]
Apply[Interval,gaps]//FullForm
Interval[List[1,5.5],List[10.001,10.007],List[10.101,11.001],List[11.007,12]]
Then we Map IntervalMemberQ over this interval object to test if each element of events falls in any of the intervals.By adding the Not operator, the procedure returns True for those events not included in any of the intervals, which is what you sought.
In[2]:=
testQ[x_List]:=Map[IntervalMemberQ[Apply[Interval,gaps],#]&,x];
We can turn this into a short function. Since your list of events << list of gaps, a simple
procedural code will create your desired output.
In[3]:=
keepEvents[x_List]:=Module[{newEvents,tq},
newEvents={};
tq=testQ[events];
Do[If[!tq[[i]],AppendTo[newEvents,events[[i]]]],{i,1,Length[events]}];
newEvents
];
keepEvents[events]
{6.7,8.9,10,0.002}
The advantage of this is clear when you compare speeds on a randomly
generated larger datasets.
In[4]:=events=Table[Random[Real,{0,1000}],{1000}];
gapStart=Table[Random[Integer,{0,500}],{3000}];
gaps=Table[{gapStart[[i]],gapStart[[i]]+10},{i,1,Length[gapStart]}];
Out[6]={390.35 Second}events=Table[Random[Real,{0,1000}],{100}];
gapStart=Table[Random[Integer,{0,500}],{300}];
gaps=Table[{gapStart[[i]],gapStart[[i]]+10},{i,1,Length[gapStart]}];
Length[keepEvents[events]]//Timing
{5.45 Second,36}
In this case (on an antique laptop with insufficient RAM), the procedural
code takes five times longer to run
{27.8833 Second}
jim leddon wrote in message <7vm3ud$q8r at smc.vnet.net>...
>
>Hi Folks,
>
>The program below takes the each value of the list,"events" , finds
>which of these values falls within the intervals {x,y} which comprise
>the list, "gaps" , then removes these values from the events list and
>outputs this modified list which is called "eout". I'm getting an error
>for incomplete expression, although I'm not sure if the algorithm itself
>is doing the job. These reason why I wrote the loop to cue on the
>integer parts of both lists is because these lists will eventually be
>quite large, about 3000 elements each in which case I wanted to make the
>process more efficient.
>
>Thanks if anyone can help.
>Debbie L.
>
>gaps = {{1,5.5}, {2,4.3}, {2.7, 3.1}, {3.002, 4.007}, {10.001,
>10.007}, {10.101, 11.001}, {11.007, 12.0}};
>
>events ={6.7, 8.9, 2.3, 2.789, 10, 11.002, 10.115, 3.02, 2.75};
>eout = {0};
>max = Length[events];
>Do[e = IntegerPart[events[[i]]; ei = events[[i]]; tmp1 =
>Select[gaps,
>
>#[[1]] >= IntegerPart[e] && #[[2]] <= IntegerPart[e] &];
> For[ j=1, j<= Length[tmp1], j++,
> If[ ei <= tmp1[[j,2]] && ei .=
tmp1[[j,1]],
> AppendTo[eout,ei]]
> ],
> {i,max}
> ]
>Delete[eout,1];
>eout
>
>