EmpiricalDistribution for Gini Coefficient Runs Slow

Question

I am repurposing code that I found in this blog post (http://datavoreconsulting.com/sports/gini-coefficients-and-the-olympic-medal-race/) to generate the Gini coefficient for other data sets I am working on. When I run the code it generates the coefficient, but seems to take an inordinate amount of time. Does anyone have suggestions for how I can speed this up?

Here is my code and the sample Olympic medal data from the site.

medals={{45, 19, 14, 11, 7, 7, 6, 5, 3, 3, 2},
{110, 48, 35, 16, 9, 8, 7, 6, 6, 5, 5, 5, 5, 4, 3, 2, 2, 2, 2, 1, 1}, 
{234, 13, 9, 6, 4, 2, 2, 2, 2, 1}, 
{142, 46, 25, 19, 16, 14, 9, 8, 8, 5, 5, 5, 4, 3, 3, 2, 2, 2,1}, 
{65, 63, 41, 26, 25, 16, 12, 9, 8, 8, 8, 7, 6, 6, 4, 4, 3, 2, 1, 1}, 
{94, 63, 43, 42, 42, 34, 32, 25, 14, 11, 11, 10, 10, 3, 3, 3, 2, 2, 2, 1, 1, 1}, 
{99, 40, 37, 36, 29, 25, 16, 13, 11, 11, 10, 10, 10, 6, 6, 6, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1}, 
{56, 39, 25, 25, 25, 23, 22, 20, 16, 15, 10, 9, 9, 7, 7, 5, 5, 5, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{110, 36, 25, 24, 24, 20, 18, 17, 16, 16, 9, 8, 8, 6, 5, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1}, 
{101, 57, 27, 21, 20, 20, 19, 18, 18, 17, 16, 14, 9, 9, 9, 7, 7, 6, 5, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1}, 
{84, 46, 32, 31, 27, 26, 22, 22, 22, 16, 14, 12, 11, 8, 7, 7, 7, 6, 5, 5, 4, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{76, 70, 42, 35, 24, 22, 21, 18, 14, 12, 11, 11, 10, 8, 7, 6, 5, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1}, 
{98, 74, 35, 26, 26, 25, 24, 19, 17, 15, 14, 13, 9, 7, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1}, 
{103, 71, 42, 36, 22, 21, 21, 20, 18, 10, 9, 8, 7, 6, 6, 6, 5, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{93, 90, 50, 29, 27, 23, 22, 18, 18, 15, 14, 12, 10, 10, 8, 6, 6, 5, 5, 5, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{107, 91, 32, 26, 25, 25, 19, 17, 15, 15, 15, 13, 13, 9, 9, 9, 8, 8, 7, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1}, 
{99, 95, 66, 40, 35, 29, 21, 21, 18, 17, 17, 16, 16, 13, 9, 8, 8, 8, 5, 5, 5, 5, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},     
{126, 94, 90, 39, 27, 25, 25, 22, 22, 14, 13, 13, 11, 9, 8, 8, 6, 6, 6, 5, 5, 5, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1}, 
{194, 126, 41, 32, 31, 25, 21, 20, 15, 14, 14, 12, 9, 9, 8, 6, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1}, 
{173, 59, 52, 46, 37, 32, 32, 31, 28, 23, 19, 19, 18, 13, 12, 11, 8, 8, 6, 6, 5, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{132, 102, 94, 40, 35, 33, 28, 24, 24, 23, 16, 16, 14, 14, 14, 13, 12, 11, 10, 9, 9, 8, 6, 5, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{112, 108, 82, 53, 31, 31, 29, 28, 27, 22, 22, 20, 19, 19, 18, 18, 16, 15, 12, 10, 9, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{102, 65, 63, 50, 41, 37, 35, 27, 25, 23, 22, 21, 19, 19, 17, 17, 15, 15, 15, 15, 14, 11, 11, 8, 8, 8, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{93, 89, 58, 58, 56, 38, 34, 29, 28, 28, 26, 25, 23, 18, 17, 17, 14, 14, 13, 13, 12, 12, 11, 10, 9, 9, 8, 8, 7, 7, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{102, 92, 63, 49, 49, 37, 33, 32, 30, 30, 27, 23, 22, 19, 19, 17, 16, 15, 12, 12, 10, 10, 10, 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{110, 100, 73, 47, 46, 41, 41, 31, 27, 27, 25, 24, 19, 18, 18, 16, 15, 14, 13, 10, 10, 10, 9, 9, 8, 8, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{104, 87, 82, 65, 44, 38, 35, 34, 28, 28, 20, 20, 18, 17, 17, 17, 14, 13, 13, 13, 12, 12, 11, 10, 10, 10, 9, 9, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

gini[list_] := Module[{d}, d = EmpiricalDistribution[list]; 

1 - Sum[( PDF[d, y]*(Sum[PDF[d, x]*x, {x, 0, y - 1}] + Sum[PDF[d, x]*x, {x, 0, y}]))/ Sum[PDF[d, x]*x, {x, 1, Max[list]}], {y, 1, Max[list]}] // N] 

ginicoefficient = ParallelMap[gini[#] &, medals];

I was able to get a 1.67 speedup by using ParallelMap. The speedup gets takes about about 30 seconds to run on my machine.

Other data sets I have tried have taken much longer. Here is the actual data I am using for my analysis:

dataA={27202226, 9706145, 8754168, 7768391, 7728354, 6619827, 6278530,5723010, 4572486, 3468553, 2578256, 2375609, 2103342, 1781526, 1748144, 1300719, 985237, 976930, 951310, 572229, 572035, 554326, 508000, 466145, 341955, 289557, 267754, 258240, 251059, 208431, 190313, 182377, 160547, 159761, 159619, 143532, 113995, 106034, 101413, 101138, 92257, 92226, 83332, 73705, 73529, 70442, 60404, 57552, 51019, 40933, 39887, 38273, 37720, 33268, 28769, 27047, 25113, 24071, 20321, 17362, 14005, 13301, 11358, 10762, 10262, 10000, 9972, 8714, 8218, 6918, 6592, 6097, 5200, 5004, 4600, 4147, 4000, 3629, 3074, 2532, 2511, 1955, 1926, 1742, 1682, 1547, 1410, 1266, 867, 747, 713, 672, 452, 438, 360, 248, 107, 80}

dataB={14017085, 13167607, 10682037, 10454713, 10165633, 8189166, 5750866, 4825388, 3608333, 3357039, 2230084, 1827165, 1684532, 1605366, 1481081, 1173900, 1125886, 971655, 716186, 645870, 634825, 550483, 522765, 470109, 370176, 296950, 289277, 263830, 213575, 212790, 202016, 143543, 140156, 137528, 133740, 122878, 70418, 69752, 63407, 56687, 55669, 55665, 54069, 49534, 47970, 39071, 36732, 36722, 35488, 33966, 32583, 27212, 22004, 20992, 20962, 20325, 20263, 20202, 19006, 16597, 15924, 15392, 13828, 12700, 12163, 11024, 9552, 9350, 9034, 7785, 5714, 5432, 3975, 3747, 3516, 3273, 2301, 2075, 2075, 1913, 1845, 1829, 1545, 1364, 1092, 977, 667, 327, 311, 228}

gini[list_] := Module[{d}, d = EmpiricalDistribution[list]; 

1 - Sum[( PDF[d, y]*(Sum[PDF[d, x]*x, {x, 0, y - 1}] + Sum[PDF[d, x]*x, {x, 0, y}]))/ Sum[PDF[d, x]*x, {x, 1, Max[list]}], {y, 1, Max[list]}] // N] 

ginicoefficient = ParallelMap[gini[#] &, {dataA, dataB}];

I am using two data sets dataA and dataB because if I run them one at a time I get an error that EmpiricalDistribution requires a rectangular array of data to work.

Any thoughts?

Answer 1

A slightly modified version of the function ginivalues from @SethChandler's Wolfram demonstration LorenzCurvesAndTheGiniCoefficient gives about 6000x speed-up.

Define

giniF[dt_List] :=  With[{sorted = Accumulate[Sort[dt]]}, 
N@Mean[2 MapThread[#1 - #2 &, {Range[1/Length[dt], 1, 1/Length[dt]], sorted/Last[sorted]}]]]

Using the medals dataset:

giniF /@ medals 

gives

{0.484352, 0.665653, 0.808364, 0.665567, 0.563968, 0.586252, 
 0.641705, 0.575891, 0.617181, 0.600399, 0.621172, 0.640249, 
 0.650118, 0.696559, 0.676793, 0.640202, 0.689444, 0.690395, 
 0.713346, 0.697871, 0.698735, 0.685428, 0.652485, 0.638607, 
 0.615032, 0.655403, 0.651779}

which is the same as ginicoefficient obtained in OP's code:

%==ginicoefficient
(* True *)

Timings:

AbsoluteTiming[ginicoefficient0 = gini /@ medals;]
(* {35.543554, Null} *)
AbsoluteTiming[ginicoefficient1 = ParallelMap[gini, medals];]
(* {21.961196, Null} *)
AbsoluteTiming[ginicoefficient2 = giniF /@ medals ;]
(* {0.006001, Null}  *)
ginicoefficient0 == ginicoefficient1 == ginicoefficient2
(* True *)

For datasets dataA and dataB:

AbsoluteTiming[giniF /@ {dataA, dataB}]
(* {0.001000, {0.867162, 0.854351}} *)