Re: Overlapping binning of differences of two lists
- To: mathgroup at smc.vnet.net
- Subject: [mg92648] Re: Overlapping binning of differences of two lists
- From: Ray Koopman <koopman at sfu.ca>
- Date: Thu, 9 Oct 2008 06:37:39 -0400 (EDT)
- References: <gci2hv$t8$1@smc.vnet.net>
On Oct 8, 3:37 am, Art <grenan... at gmail.com> wrote:
> Given two sorted vectors a and b of different lengths, what is the
> best way to count the number of elements in the set of all differences
> between elements of a and b that fall in overlapping bins of [-bsize -
> i, bsize - i) for i in Range[-n, n], where bsize >= 1.
>
> Below are 2 implementations I've tried which are two slow and memory
> intensive. I haven't quite been able to do it using BinCounts,
> Partition, and ListCorrelate.
>
> Was wondering if there is a faster way.
>
> (* Generate random a, b *)
> T = 500; bsize = 10; n = 20;
> r := Rest@FoldList[Plus, 0, RandomReal[ExponentialDistribution[0.01],
> {T}]]
> a = r; b = r;
>
> bindiff1[a_, b_, bsize_, n_] :=
> With[{d = Flatten@Outer[Subtract, a, b]},
> Table[Count[d, _?(-bsize <= # - i < bsize &)], {i, -n, n}]]
>
> bindiff2[a_, b_, bsize_, n_] :=
> Module[{os, i, j, s, tmp,
> d = Sort@Flatten@Outer[Subtract, a, b],
> c = ConstantArray[0, {2 n + 1}]},
> For[os = 0; j = 1; i = -n, i <= n, i++; j++,
> s = Flatten@Position[Drop[d, os], _?(# >= -bsize + i &), 1, 1];
> If[s == {}, Break[],
> os += s[[1]] - 1;
> tmp = Flatten@Position[Drop[d, os], _?(# > bsize + i &), 1, 1];
> c[[j]] = If[tmp == {}, Length[d] - os, First@tmp - 1]]];
> Return[c]]
>
> First@Timing@bindiff[a,b, bsize, n] is about 36 seconds.
>
> First@Timing@bindiff2[a, b, bsize, n] is about 3 seconds but still too
> slow and d uses up too much memory.
>
> Thanks!
This is a little faster, but it still uses Outer[Subtract,a,b].
bindiff3[a_, b_, bsize_, n_] := Block[{c = Table[0,{2n+1}],
w = Interval/@Transpose@{Range[-n,n]-bsize, Range[-n,n]+bsize}, u},
Scan[Do[If[IntervalMemberQ[w[[i]],#],c[[i]]++],{i,2n+1}]&,
u = IntervalUnion@@w;
Select[Flatten@Outer[Subtract,a,b],IntervalMemberQ[u,#]&]]; c]
First@Timing[c1 = bindiff1[a, b, bsize, n]]
First@Timing[c2 = bindiff2[a, b, bsize, n]]
First@Timing[c3 = bindiff3[a, b, bsize, n]]
c1 === c2 === c3
77.08 sec
3.69 sec
1.14 sec
True