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>
- Re: Re: position lists