12
$\begingroup$

Let's say I have a list like this:

data = {{21, "Alice"}, {27, "Bob"}, {22, "Charles"}, {34, "Dora"}, {75, "Eliza"}}

containing ages and names of persons. What I would like is a list of e.g. 10-year age brackets, containing a list of {age,name}-pairs:

{
  {{21, "Alice"}, {27, "Bob"}, {22, "Charles"}}, (* 20-30 years *)
  {{34, "Dora"}}, (* 30-40 years *)
  {}, (* 40-50 years *)
  {}, (* 50-60 years *)
  {}, (* 60-70 years *)
  {{75, "Eliza"}} (* 70-80 years *)
}

GatherBy[data, Floor[First[#]/10]&] is close, but it leaves out empty bins.

BinLists[data[[All, 1]], 10] is also similar, but it only returns the list of ages, I can't get it to include the names as well.

Ideally, I'd like to have a function with similar syntax and performance to BinLists, i.e.: binListsBy[data, {10,70,10}, First]. And the function should be fast, because I'm going to use it on millions of entries (pixels of an image, in fact).

(Following Mr.Wizard's meta discussion, I'm not going to add "what have I tried" in my question - I'm really looking for better ideas, or maybe even a built-in function I haven't noticed. Instead I'll post my attempts as an answer.)

$\endgroup$
7
  • $\begingroup$ I think question is a duplicate as it seems very familiar, yet I'm too tired to find the original right now. $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 11:39
  • 1
    $\begingroup$ @Mr.Wizard, this one? $\endgroup$ Jun 11, 2014 at 12:01
  • $\begingroup$ @Simon It very well could be, though in my memory it is/was a little different. Thanks for finding that. There are probably several questions like this around. $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 12:07
  • $\begingroup$ (19357) is also related; despite my having the Accepted answer there jVincent posted the better method, which used priming of Tally much as my answer here does with GatherBy. $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 12:12
  • 2
    $\begingroup$ What kind of input data will you use it on precisely? Specifically: what opportunities are there to use packed arrays? $\endgroup$
    – Szabolcs
    Jun 11, 2014 at 13:01

5 Answers 5

9
$\begingroup$

I fear this question is a duplicate, but it's faster for me to answer than find the original (I briefly tried).

fn[data_, {m_, M_}, step_] :=
 Rest /@ GatherBy[Join[List /@ Range[m, M, step], data], Quotient[First@#, step] &]

fn[data, {20, 70}, 10] // Column
{{21, "Alice"}, {27, "Bob"}, {22, "Charles"}}
{{34, "Dora"}}
{}
{}
{}
{{75, "Eliza"}}

If you want the range (m, M) automatic that's a simple substitution. (Let me know.)

This is not written for ultimate speed but it should be pretty fast.


This is somewhat faster on your (packed) randomData; it uses a post-processing approach to zero-fill the GatherBy result.

Edit: now significantly faster.

fn2[data_, {m_, M_}, step_] :=
  Rest /@ GatherBy[
    Join[
      {{#}} & /@ Range[m, M, step],
      GatherBy[data, #[[1]] ~Quotient~ step &]
     ],
    #[[1, 1]] ~Quotient~ step &
  ] // Replace[#, {x_List} :> x, 1] &
$\endgroup$
9
$\begingroup$

This is my current version:

Clear[binSpecToIndexFn, binSpecToRange, binListsBy]

(* takes a "bin specification", returns a function that converts a 
   value to a bin index *)
binSpecToIndexFn[{low_, high_, step_}] := Floor[(# - low)/step] &
binSpecToIndexFn[step_] := Floor[#/step] &

(* takes a bin specification and data, returns a range of bin indices *)
binSpecToRange[bspec : {low_, high_, step_}, data_] := 
 Range @@ binSpecToIndexFn[bspec] /@ {low, high}
binSpecToRange[bspec_, data_] := 
 Range @@ Through[{Min, Max}[binSpecToIndexFn[bspec] /@ data]]

binListsBy[data_, bspec_, fn_] := Module[{binIndexFn, gathered},
  binIndexFn = binSpecToIndexFn[bspec];
  gathered = GatherBy[data, binIndexFn[fn[#]] &];
  binSpecToRange[bspec, fn /@ data] /. 
   Flatten[{binIndexFn[fn[#[[1]]]] -> # & /@ 
      gathered, _?IntegerQ -> {}}]]

I'm not particularly happy that I had to reinvent the "bin specification" logic that has to be somewhere in MMA (Histogram, BinCounts, BinLists all share the same logic). Also, the range/index replacement rules logic seems unnecessarily complex for such a simple task, but I couldn't come up with something simpler.

Usage:

data = {{21, "Alice"}, {27, "Bob"}, {22, "Charles"}, {34, "Dora"}, {75, "Eliza"}};
binListsBy[data, 10, First]

Timing:

Baseline: BinLists

randomData = RandomReal[{0, 1}, {10000000, 2}];
BinLists[randomData[[All, 1]], 10]; // Timing

0.593 s

@Mr. Wizard's version:

fn2[data_, {m_, M_}, step_, fn_] := 
 Rest /@ GatherBy[
    Join[{{#}} & /@ Range[m, M, step], 
     GatherBy[data, fn[#]~Quotient~step &]], #[[1, 1]]~Quotient~
      step &] // Replace[#, {x_List} :> x, 1] &

fn2[randomData, {0, 1}, 0.1, First]; // Timing

0.749 s

My original version

binListsBy[randomData, .1, First]; // Timing

1.279 s

@Murta's version:

binListByMurta[randomData, {0, 1, .1}, 1, First]; // Timing

7.22 s

@Kuba's version (using my binSpecTo*-Heplers)

binListsByKuba[data_, bspec_, fn_] := Module[{binIndexFn},
  binIndexFn = binSpecToIndexFn[bspec];
  Last@Reap[Scan[Sow[#, binIndexFn[fn[#]]] &, data], 
    binSpecToRange[bspec, fn /@ data]]]
binListsByKuba[randomData, .1, First]; // Timing

26.6 s

So @Mr. Wizard's version is the fastest by a large margin. And some day, I will understand how it works...

$\endgroup$
3
  • $\begingroup$ Perhaps BinningUtilities`BinCutOffs[fn /@ data, bspec] would help... It gives cut-offs instead of indices, though. $\endgroup$
    – Michael E2
    Jun 11, 2014 at 16:23
  • $\begingroup$ Are you going to add my functions to your timings? $\endgroup$
    – Mr.Wizard
    Jun 16, 2014 at 2:02
  • $\begingroup$ @Mr.Wizard: I'm trying to, but I honestly don't understand it well enough. To compare the timings, the function should take a function parameter, like the other versions. Yours (I think?) always gathers by the first subelement, which may or may not be faster than calling a user-supplied function. $\endgroup$ Jun 16, 2014 at 6:21
6
$\begingroup$

I miss a native implementation of this. Here's how I do this:

binListBy[data_List,binSize_,binIndex_Integer,aggrateFunctions_,nullValue_:Null]:=Module[{max,min},
    {min,max}=Floor[Through@{Min,Max}@data[[All,binIndex]],binSize];
    binListBy[data,{min,max,binSize},binIndex,aggrateFunctions,nullValue]
]

binListBy[data_List,{min_,max_,binSize_},binIndex_Integer,aggrateFunctions_,nullValue_:Null]:=
  Module[{intervals,findInterval,binRule},

    intervals=Partition[Range[min,max+binSize,binSize],2,1];
    findInterval={Floor[#,binSize],Floor[#,binSize]+binSize}&;
    binRule=findInterval@#[[1,binIndex]] -> {findInterval@#[[1,binIndex]],aggrateFunctions@Transpose@#}&/@GatherBy[data,findInterval[#[[binIndex]]]&];

    binRule=Dispatch@Join[binRule,{{a_,b_}:> {{a,b},nullValue}}];
    intervals/.binRule
]

Testing question data: binListBy[data, 10, 1, Last]

{{{20,30},{Alice,Bob,Charles}},{{30,40},{Dora}},{{40,50},Null},{{50,60},Null},{{60,70},Null},{{70,80},{Eliza}}}

Another test:

test = RandomInteger[{20,100}, {100, 2}];
binedList=binListBy[test,20,1,Total[#[[2]]]&,0]
$\endgroup$
4
$\begingroup$

This probably won't be the fastest but worth to add:

Last @ Reap[Scan[Sow[#, Floor[#[[ 1]]/10]] &, data], 
            Range[2, 7]]
{{ {{21, "Alice"}, {27, "Bob"}, {22, "Charles"}}}, 
   {{{34, "Dora"}}}, 
   {},
   {},
   {},
   {{{75, "Eliza"}}
}}

So at the end:

ClearAll[mybin];
mybin[data_, {min_, max_, dx_: 1}] := Reap[Scan[Sow[#, Floor[#[[1]]/dx]] &, data], 
                                           Range[Floor[min/dx], Floor[max/dx]]][[ 2]]
$\endgroup$
3
$\begingroup$

A simple alternative:

data = {{21, "Alice"}, {27, "Bob"}, {22, "Charles"}, {34, "Dora"}, {75, "Eliza"}};

result = Sort /@ 
   GatherBy[
    Join[Transpose[{Range[0, 100, 10], Table[" ", {11}]}], data], 
    Floor[First[#]/10] &] // TableForm

TableForm[result, TableSpacing -> {2, 2}]

enter image description here

$\endgroup$
6
  • $\begingroup$ The OP's example does not sort the values in the output lists; that may not be desired. $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 13:54
  • $\begingroup$ @Mr.Wizard this may or may not be done (see my update) $\endgroup$
    – eldo
    Jun 11, 2014 at 14:04
  • $\begingroup$ Why not simply use this?: result = GatherBy[Join[Transpose[{Range[0, 100, 10], Table[" ", {11}]}], data], Floor[First[#]/10] &]; That is essentially what I did in my answer (fn). $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 14:17
  • $\begingroup$ @Mr.Wizard - I didn't pretend to give a "better" answer but just wanted to know how I would write this myself. If you consider my answer as a duplicate of yours, please let me know and I delete it. $\endgroup$
    – eldo
    Jun 11, 2014 at 14:37
  • $\begingroup$ No, I didn't meant to imply that, and please do not think you are not welcome to post an answer unless you claim it is "better." Rather I was trying to guide or refine the answer you gave. I like the visual presentation but I didn't vote for the answer because I'm not sure it's helpful to the OP. Anyway, my apologies for stepping on your toes. $\endgroup$
    – Mr.Wizard
    Jun 11, 2014 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.