Re: position lists
- To: mathgroup at smc.vnet.net
- Subject: [mg68956] Re: position lists
- From: "rych" <rychphd at gmail.com>
- Date: Fri, 25 Aug 2006 05:35:12 -0400 (EDT)
- References: <ebujvu$6lu$1@smc.vnet.net><200608180711.DAA01933@smc.vnet.net> <ecej36$qjs$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Thank you, Daniel and the others
I meant double brackets. I use esc[[esc to make them and I din't know
how to copy in to the newsgroup, so I did Edit-CopyAs-Text(with
witespaces). Now I'll be doing Cell-ConvertTo-InputForm, and then
copy-paste.
Summarizing the topic, the PositionListsC is much faster but it
produces a linked list. In order to use it I have to retreat to
element-wise, Do-While programming, because there're no built-in
functions, no faster ways to to work with Knuth linked lists.
Igor
Daniel Lichtblau wrote:
> rych wrote:
> > 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