Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: How to handle Arrays that has functional parameters:
  • Next by Date: Re: General--Difficulties in Understanding Mathematica Syntax
  • Previous by thread: Re: Re: position lists
  • Next by thread: Re: position lists