Re: Re: position lists
- To: mathgroup at smc.vnet.net
- Subject: [mg68887] Re: [mg68748] Re: position lists
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 22 Aug 2006 05:20:24 -0400 (EDT)
- References: <ebujvu$6lu$1@smc.vnet.net> <200608180711.DAA01933@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
rych wrote:
> Yes, thanks to everyone who replied, this indeed does it:
> In[469]:=
> a={1,1,2,2,1,4};
> Flatten@Position[a,#]&/@Range[4]
>
> Out[470]=
> {{1,2,5},{3,4},{},{6}}
>
> But it grows linear with the "number of bins" (=4). It searches for
> each bin among all the positions, even those that have been previously
> identified as belonging to differetn bins.
>
> A more effective solution is to use linked-list arrays:
> In[473]:=
> PositionListsC=Compile[{{a,_Integer,1},{nBins,_Integer}},
> Module[{heads =
> Table[0,{nBins}],linkedlist=Table[0,{Length@a}],bin},
> Do[
> bin = a[i];
> linkedlist[i]=heads[bin];
> heads[bin]=i,
> {i,Length@a}];
> (*To avoid the "Non-tensor object generated;proceeding with
> uncompiled evaluation"*)
> Join[heads,linkedlist]]
> ];
> (joined=PositionListsC[a,4] ;{Take[joined,4],Take[joined,-Length@a]})
> Out[474]=
> {{5,4,0,6},{0,1,0,3,2,0}}
> It gives two lists: heads -- the last point that fell in the bin and a
> linked list of all the other points in the same bin (terminated by 0).
> For example in the bin #1 we have 5->2->1. So we do get the same
> information, but in a different structure.
>
> Let's see their performance
> In[478]:=
> nBins = 1000; b = Table[Random[Integer, {1, nBins}], {100000}];
> (joined = PositionListsC[b, nBins] ; {
> Take[joined, nBins], Take[joined, -Length@b]};) // Timing
> Flatten@Position[b, #] & /@ Range[nBins]; // Timing
> Out[479]=
> {0.031 Second, Null}
> Out[480]=
> {15.329 Second, Null}
>
> My questions was whether there's such a built-in list function. Or
> perhaps a package that could give lists of points sorted into bins.
I'm not sure what you actually did but the code you show above will not
work as advertised. Array indexing requires double brackets, not single.
Below is code that will give {{5,4,0,6},{0,1,0,3,2,0}} for your simple
example.
PositionListsC = Compile[{{a,_Integer,1},{nBins,_Integer}},
Module[
{heads=Table[0,{nBins}], linkedlist=Table[0,{Length[a]}], bin},
Do [
bin = a[[i]];
linkedlist[[i]] = heads[[bin]];
heads[[bin]] = i
, {i,Length[a]}
];
Join[heads,linkedlist]]
];
Now the question is how to convert this to the same representation as is
given by the slower code:
positionLists2[ll_List, n_Integer] :=
Flatten@Position[ll,#]& /@ Range[n]]
Offhand I don't know, partly because I have not decrypted this form of
result from PositionListsC.
[I will remark that I utterly despise this construct
Flatten at Position[...]& ... because it is quite unobvious how the binding
goes. Is it equivalent to
positionLists2b[ll_List, n_Integer] :=
Flatten[Position[ll,#]]& /@ Range[n]
or to
positionLists2c[ll_List, n_Integer] :=
Flatten[Position[ll,#]& /@ Range[n]]
??
It's the former, but really, who knew?]
Anyway, I advocate circumventing the whole thing using Reap[Sow[...]] as
below.
positionLists3[ll_List, n_Integer] :=
Map[Flatten,Last[Reap[MapIndexed[Sow[#2[[1]],#1]&, ll], Range[n]]]]
nBins = 1000;
b = Table[Random[Integer, {1, nBins}], {100000}];
Your reference timing:
In[55]:= Timing[(joined = PositionListsC[b, nBins] ; {
Take[joined, nBins], Take[joined, -Length@b]};)]
Out[55]= {0.032002, Null}
The pedestrian method:
In[56]:= Timing[res2 = positionLists2[b,nBins];]
Out[56]= {11.8007, Null}
The Reap[Sow[]] method:
In[59]:= Timing[res3 = positionLists3[b,nBins];]
Out[59]= {0.452028, Null}
In[60]:= res2===res3
Out[60]= True
So it is 15x slower than your PositionListsC but requires no
post-processing to get it into an explicit set of bins.
Daniel Lichtblau
Wolfram Research
- References:
- Re: position lists
- From: "rych" <rychphd@gmail.com>
- Re: position lists