Re: position lists

*To*: mathgroup at smc.vnet.net*Subject*: [mg68748] Re: position lists*From*: "rych" <rychphd at gmail.com>*Date*: Fri, 18 Aug 2006 03:11:48 -0400 (EDT)*References*: <ebujvu$6lu$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

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.

**Follow-Ups**:**Re: Re: position lists***From:*Daniel Lichtblau <danl@wolfram.com>