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}},
Do[
bin = a[i];
{i,Length@a}];
(*To avoid the "Non-tensor object generated;proceeding with
uncompiled evaluation"*)
];
(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.

```

• Prev by Date: Re: calculate Recurrence Equations
• Next by Date: Beginner--Beginner: Calculating Ave Intensity in a domain of n points
• Previous by thread: Re: position lists
• Next by thread: Re: Re: position lists