Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.)

share|improve this question
    
I think question is a duplicate as it seems very familiar, yet I'm too tired to find the original right now. –  Mr.Wizard Jun 11 at 11:39
1  
@Mr.Wizard, this one? –  Simon Woods Jun 11 at 12:01
    
@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. –  Mr.Wizard Jun 11 at 12:07
    
(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. –  Mr.Wizard Jun 11 at 12:12
2  
What kind of input data will you use it on precisely? Specifically: what opportunities are there to use packed arrays? –  Szabolcs Jun 11 at 13:01

5 Answers 5

up vote 9 down vote accepted

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] &
share|improve this answer

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...

share|improve this answer
    
Perhaps BinningUtilities`BinCutOffs[fn /@ data, bspec] would help... It gives cut-offs instead of indices, though. –  Michael E2 Jun 11 at 16:23
    
Are you going to add my functions to your timings? –  Mr.Wizard Jun 16 at 2:02
    
@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. –  nikie Jun 16 at 6:21

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

share|improve this answer
    
The OP's example does not sort the values in the output lists; that may not be desired. –  Mr.Wizard Jun 11 at 13:54
    
@Mr.Wizard this may or may not be done (see my update) –  eldo Jun 11 at 14:04
    
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). –  Mr.Wizard Jun 11 at 14:17
    
@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. –  eldo Jun 11 at 14:37
    
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. –  Mr.Wizard Jun 11 at 15:09

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]]
share|improve this answer

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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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