/* Ċ Ġ* ĠCopyright Ġ 2 0 1 8 - 2 0 2 1 ĠK Math Ġcontributors . Ċ Ġ* ĠUse Ġof Ġthis Ġsource Ġcode Ġis Ġgoverned Ġby Ġthe ĠApache Ġ 2 . 0 Ġlicense Ġthat Ġcan Ġbe Ġfound Ġin Ġthe Ġlicense / LICENSE . txt Ġfile . Ċ Ġ*/ Ċ Ċ package Ġspace . k science . k math . samp lers Ċ Ċ import Ġspace . k science . k math . chains . Chain Ċ import Ġspace . k science . k math . internal . Internal Utils Ċ import Ġspace . k science . k math . stat . Random Generator Ċ import Ġspace . k science . k math . stat . Sampler Ċ import Ġspace . k science . k math . stat . chain Ċ import Ġkotlin . math . ceil Ċ import Ġkotlin . math . max Ċ import Ġkotlin . math . min Ċ Ċ /** Ċ Ġ* ĠDistribution Ġsampler Ġthat Ġuses Ġthe ĠAlias Ġmethod . ĠIt Ġcan Ġbe Ġused Ġto Ġsample Ġfrom Ġn Ġvalues Ġeach Ġwith Ġan Ġassociated Ċ Ġ* Ġprobability . ĠThis Ġimplementation Ġis Ġbased Ġon Ġthe Ġdetailed Ġexplanation Ġof Ġthe Ġalias Ġmethod Ġby ĠKe ith ĠS chart z Ġand Ċ Ġ* Ġimplements ĠV ose 's Ġalgorithm . Ċ Ġ* Ċ Ġ* ĠV ose , ĠM . D ., ĠA Ġlinear Ġalgorithm Ġfor Ġgenerating Ġrandom Ġnumbers Ġwith Ġa Ġgiven Ġdistribution , ĠIEEE ĠTransactions Ġon Ċ Ġ* ĠSoftware ĠEngineering , Ġ 1 7 , Ġ 9 7 2 - 9 7 5 , Ġ 1 9 9 1 . Ġhe Ġalgorithm Ġwill Ġsample Ġvalues Ġin ĠO ( 1 ) Ġtime Ġafter Ġa Ġpre - processing Ġstep Ċ Ġ* Ġof ĠO ( n ) Ġtime . Ċ Ġ* Ċ Ġ* ĠThe Ġalias Ġtables Ġare Ġconstructed Ġusing Ġfraction Ġprobabilities Ġwith Ġan Ġassumed Ġdenominator Ġof Ġ 2 5 3 . ĠIn Ġthe Ġgeneric Ċ Ġ* Ġcase Ġsampling Ġuses ĠUniform Random Provider . nextInt ( int ) Ġand Ġthe Ġupper Ġ 5 3 - bits Ġfrom ĠUniform Random Provider . next Long (). Ċ Ġ* Ċ Ġ* ĠZero Ġpadding Ġthe Ġinput Ġprobabilities Ġcan Ġbe Ġused Ġto Ġmake Ġmore Ġsampling Ġmore Ġefficient . ĠAny Ġzero Ġentry Ġwill Ġalways Ġbe Ċ Ġ* Ġali ased Ġremoving Ġthe Ġrequirement Ġto Ġcompute Ġa Ġlong . ĠIncrease d Ġsampling Ġspeed Ġcomes Ġat Ġthe Ġcost Ġof Ġincreased Ġstorage Ċ Ġ* Ġspace . ĠThe Ġalgorithm Ġrequires Ġapproximately Ġ 1 2 Ġbytes Ġof Ġstorage Ġper Ġinput Ġprobability , Ġthat Ġis Ġn Ġ* Ġ 1 2 Ġfor Ġsize Ġn . Ċ Ġ* ĠZero - padding Ġonly Ġrequires Ġ 4 Ġbytes Ġof Ġstorage Ġper Ġpadded Ġvalue Ġas Ġthe Ġprobability Ġis Ġknown Ġto Ġbe Ġzero . Ċ Ġ* Ċ Ġ* ĠAn Ġoptim isation Ġis Ġperformed Ġfor Ġsmall Ġtable Ġsizes Ġthat Ġare Ġa Ġpower Ġof Ġ 2 . ĠIn Ġthis Ġcase Ġthe Ġsampling Ġuses Ġ 1 Ġor Ġ 2 Ċ Ġ* Ġcalls Ġfrom ĠUniform Random Provider . nextInt () Ġto Ġgenerate Ġup Ġto Ġ 6 4 - bits Ġfor Ġcreation Ġof Ġan Ġ 1 1 - bit Ġindex Ġand Ġ 5 3 - bits Ċ Ġ* Ġfor Ġthe Ġlong . ĠThis Ġoptim isation Ġrequires Ġa Ġgenerator Ġwith Ġa Ġhigh Ġcycle Ġlength Ġfor Ġthe Ġlower Ġorder Ġbits . Ċ Ġ* Ċ Ġ* ĠL arger Ġtable Ġsizes Ġthat Ġare Ġa Ġpower Ġof Ġ 2 Ġwill Ġbenefit Ġfrom Ġfast Ġalgorithms Ġfor ĠUniform Random Provider . nextInt ( int ) Ċ Ġ* Ġthat Ġexploit Ġthe Ġpower Ġof Ġ 2 . Ċ Ġ* Ċ Ġ* ĠBased Ġon ĠCommons ĠR NG Ġimplementation . Ċ Ġ* ĠSee Ġ[ https :// commons . apache . org / proper / commons - rng / commons - rng - sampling / apid ocs / org / apache / commons / rng / sampling / distribution / Alias Method Discrete Sampler . html ]. Ċ Ġ*/ Ċ public Ġopen Ġclass ĠAlias Method Discrete Sampler Ġprivate Ġconstructor ( ĊĠĠĠ Ġ// ĠDel iber ate Ġdirect Ġstorage Ġof Ġinput Ġarrays ĊĠĠĠ Ġprotected Ġval Ġprobability : ĠLong Array , ĊĠĠĠ Ġprotected Ġval Ġalias : ĠInt Array , Ċ ) Ġ: ĠSampler < Int > Ġ{ ĊĊĠĠĠ Ġprivate Ġclass ĠSmall Table Alias Method Discrete Sampler ( ĊĠĠĠĠĠĠĠ Ġprobability : ĠLong Array , ĊĠĠĠĠĠĠĠ Ġalias : ĠInt Array , ĊĠĠĠ Ġ) Ġ: ĠAlias Method Discrete Sampler ( probability , Ġalias ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠAssume Ġthe Ġtable Ġsize Ġis Ġa Ġpower Ġof Ġ 2 Ġand Ġcreate Ġthe Ġmask ĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġmask : ĠInt Ġ= Ġalias . size Ġ- Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġsample ( generator : ĠRandom Generator ): ĠChain < Int > Ġ= Ġgenerator . chain Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbits Ġ= Ġgenerator . nextInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠI sol ate Ġlower Ġbits ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġbits Ġand Ġmask ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠOptim isation Ġfor Ġzero - padded Ġinput Ġtables ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( j Ġ>= Ġprobability . size ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNo Ġprobability Ġmust Ġuse Ġthe Ġalias ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn @ chain Ġalias [ j ] ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCreate Ġa Ġuniform Ġrandom Ġde vi ate Ġas Ġa Ġlong . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġreplic ates Ġfunctionality Ġfrom Ġthe Ġo . a . c . rng . core . utils . Number Factory . make Long ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlong Bits Ġ= Ġgenerator . nextInt (). to Long () Ġshl Ġ 3 2 Ġor Ġ( bits . to Long () Ġand Ġhex _ ffffffff ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠChoose Ġbetween Ġthe Ġtwo . ĠUse Ġa Ġ 5 3 - bit Ġlong Ġfor Ġthe Ġprobability . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( long Bits Ġ ush r Ġ 1 1 Ġ< Ġprobability [ j ]) Ġj Ġelse Ġalias [ j ] ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval Ġhex _ ffffffff Ġ= Ġ 4 2 9 4 9 6 7 2 9 5 L ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġoverride Ġfun Ġsample ( generator : ĠRandom Generator ): ĠChain < Int > Ġ= Ġgenerator . chain Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠThis Ġimplements Ġthe Ġalgorithm Ġas Ġper ĠV ose Ġ( 1 9 9 1 ): ĊĠĠĠĠĠĠĠ Ġ// Ġv Ġ= Ġuniform () Ġ Ġin Ġ[ 0 , Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ// Ġj Ġ= Ġuniform ( n ) Ġin Ġ[ 0 , Ġn ) ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġv Ġ< Ġprob [ j ] Ġthen ĊĠĠĠĠĠĠĠ Ġ// ĠĠ Ġreturn Ġj ĊĠĠĠĠĠĠĠ Ġ// Ġelse ĊĠĠĠĠĠĠĠ Ġ// ĠĠ Ġreturn Ġalias [ j ] ĊĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġgenerator . nextInt ( alias . size ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠOptim isation Ġfor Ġzero - padded Ġinput Ġtables ĊĠĠĠĠĠĠĠ Ġ// ĠNo Ġprobability Ġmust Ġuse Ġthe Ġalias ĊĠĠĠĠĠĠĠ Ġif Ġ( j Ġ>= Ġprobability . size ) Ġreturn @ chain Ġalias [ j ] ĊĊĠĠĠĠĠĠĠ Ġ// ĠNote : ĠWe Ġcould Ġcheck Ġthe Ġprobability Ġbefore Ġcomputing Ġa Ġde vi ate . ĊĠĠĠĠĠĠĠ Ġ// Ġp ( j ) Ġ== Ġ 0 Ġ Ġ=> Ġalias [ j ] ĊĠĠĠĠĠĠĠ Ġ// Ġp ( j ) Ġ== Ġ 1 Ġ Ġ=> Ġj ĊĠĠĠĠĠĠĠ Ġ// ĠHowever Ġit Ġis Ġassumed Ġthese Ġedge Ġcases Ġare Ġrare : ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġprobability Ġtable Ġwill Ġbe Ġ 1 Ġfor Ġapproximately Ġ 1 / n Ġsamples , Ġi . e . Ġonly Ġthe ĊĠĠĠĠĠĠĠ Ġ// Ġlast Ġun paired Ġprobability . ĠThis Ġis Ġonly Ġworth Ġchecking Ġfor Ġwhen Ġthe Ġtable Ġsize Ġ( n ) ĊĠĠĠĠĠĠĠ Ġ// Ġis Ġsmall . ĠBut Ġin Ġthat Ġcase Ġthe Ġuser Ġshould Ġzero - pad Ġthe Ġtable Ġfor Ġperformance . ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġprobability Ġtable Ġwill Ġbe Ġ 0 Ġwhen Ġan Ġinput Ġprobability Ġwas Ġzero . ĠWe ĊĠĠĠĠĠĠĠ Ġ// Ġwill Ġassume Ġthis Ġis Ġalso Ġrare Ġif Ġmode lling Ġa Ġdiscrete Ġdistribution Ġwhere ĊĠĠĠĠĠĠĠ Ġ// Ġall Ġsamples Ġare Ġpossible . ĠThe Ġedge Ġcase Ġfor Ġzero - padded Ġtables Ġis Ġhandled Ġabove . ĊĊĠĠĠĠĠĠĠ Ġ// ĠChoose Ġbetween Ġthe Ġtwo . ĠUse Ġa Ġ 5 3 - bit Ġlong Ġfor Ġthe Ġprobability . ĊĠĠĠĠĠĠĠ Ġif Ġ( generator . next Long () Ġ ush r Ġ 1 1 Ġ< Ġprobability [ j ]) Ġj Ġelse Ġalias [ j ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġoverride Ġfun ĠtoString (): ĠString Ġ= Ġ" Alias Ġmethod " ĊĊĠĠĠ Ġpublic Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠDEFAULT _ ALPHA Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠZERO Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠONE _ AS _ NUM ER ATOR Ġ= Ġ 1 L Ġshl Ġ 5 3 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠCON VERT _ TO _ NUM ER ATOR : ĠDouble Ġ= ĠONE _ AS _ NUM ER ATOR . toDouble () ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠMAX _ SMALL _ POWER _ 2 _ SIZE Ġ= Ġ 1 Ġshl Ġ 1 1 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġfill Remaining Indices ( length : ĠInt , Ġindices : ĠInt Array , Ġsmall : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġupdated Small Ġ= Ġsmall ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( length Ġuntil Ġindices . size ). forEach Ġ{ Ġi Ġ-> Ġindices [ updated Small ++] Ġ= Ġi Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġupdated Small ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġfind Last Non Zero Index ( prob abilities : ĠDouble Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNo Ġbounds Ġcheck Ġis Ġperformed Ġwhen Ġdecrement ing Ġas Ġthe Ġarray Ġcontains Ġat Ġleast Ġone ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġvalue Ġabove Ġzero . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnon Zero Index Ġ= Ġprobabilities . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( prob abilities [ non Zero Index ] Ġ== ĠZERO ) Ġnon Zero Index -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnon Zero Index ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġcompute Size ( length : ĠInt , Ġalpha : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIf ĠNo Ġpadding ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( alpha Ġ< Ġ 0 ) Ġreturn Ġlength ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUse Ġthe Ġnumber Ġof Ġleading Ġzeros Ġfunction Ġto Ġfind Ġthe Ġnext Ġpower Ġof Ġ 2 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġi . e . Ġceil ( log 2 ( x )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpow 2 Ġ= Ġ 3 2 Ġ- ĠnumberOf Leading Z eros ( length Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIncrease Ġby Ġthe Ġalpha . ĠClip Ġthis Ġto Ġlimit Ġto Ġa Ġpositive Ġinteger Ġ( 2 ^ 3 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpow 2 Ġ= Ġmin ( 3 0 , Ġpow 2 Ġ+ Ġalpha ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUse Ġmax Ġto Ġhandle Ġa Ġlength Ġabove Ġthe Ġhighest Ġpossible Ġpower Ġof Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġmax ( length , Ġ 1 Ġshl Ġpow 2 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġfill Table ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprobability : ĠLong Array , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġalias : ĠInt Array , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindices : ĠInt Array , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstart : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġend : ĠInt , ĊĠĠĠĠĠĠĠ Ġ) Ġ= Ġ( start Ġuntil Ġend ). forEach Ġ{ Ġi Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġindices [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprobability [ index ] Ġ= ĠONE _ AS _ NUM ER ATOR ĊĠĠĠĠĠĠĠĠĠĠĠ Ġalias [ index ] Ġ= Ġindex ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġis Small Power Of 2 ( n : ĠInt ): ĠBoolean Ġ= Ġn Ġ<= ĠMAX _ SMALL _ POWER _ 2 _ SIZE Ġ&& Ġn Ġand Ġn Ġ- Ġ 1 Ġ== Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun ĠnumberOf Leading Z eros ( i : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmut I Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mut I Ġ<= Ġ 0 ) Ġreturn Ġif Ġ( mut I Ġ== Ġ 0 ) Ġ 3 2 Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġn Ġ= Ġ 3 1 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mut I Ġ>= Ġ 1 Ġshl Ġ 1 6 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn Ġ-= Ġ 1 6 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmut I Ġ= Ġmut I Ġ ush r Ġ 1 6 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mut I Ġ>= Ġ 1 Ġshl Ġ 8 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn Ġ-= Ġ 8 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmut I Ġ= Ġmut I Ġ ush r Ġ 8 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mut I Ġ>= Ġ 1 Ġshl Ġ 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn Ġ-= Ġ 4 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmut I Ġ= Ġmut I Ġ ush r Ġ 4 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mut I Ġ>= Ġ 1 Ġshl Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmut I Ġ= Ġmut I Ġ ush r Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġn Ġ- Ġ( mut I Ġ ush r Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" FunctionName ") ĊĠĠĠ Ġpublic Ġfun ĠAlias Method Discrete Sampler ( ĊĠĠĠĠĠĠĠ Ġprobabilities : ĠDouble Array , ĊĠĠĠĠĠĠĠ Ġalpha : ĠInt Ġ= ĠDEFAULT _ ALPHA , ĊĠĠĠ Ġ): ĠSampler < Int > Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠThe ĠAlias Ġmethod Ġbalances ĠN Ġcategories Ġwith Ġcounts Ġaround Ġthe Ġmean Ġinto ĠN Ġsections , ĊĠĠĠĠĠĠĠ Ġ// Ġeach Ġallocated Ġ' mean ' Ġobservations . ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// ĠConsider Ġ 4 Ġcategories Ġwith Ġcounts Ġ 6 , 3 , 2 , 1 . ĠThe Ġhistogram Ġcan Ġbe Ġbal anced Ġinto Ġa ĊĠĠĠĠĠĠĠ Ġ// Ġ 2 D Ġarray Ġas Ġ 4 Ġsections Ġwith Ġa Ġheight Ġof Ġthe Ġmean : ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 3 ĠĠ Ġ=> Ġ 6 3 6 6 ĠĠ Ġ-- ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 3 2 ĠĠĠĠĠ 6 3 2 6 ĠĠĠ Ġ|-- Ġmean ĊĠĠĠĠĠĠĠ Ġ// Ġ 6 3 2 1 ĠĠĠĠ 6 3 2 1 ĠĠ Ġ-- ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// Ġsection Ġab cd ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// ĠEach Ġsection Ġis Ġdivided Ġas : ĊĠĠĠĠĠĠĠ Ġ// Ġa : Ġ 6 = 1 / 1 ĊĠĠĠĠĠĠĠ Ġ// Ġb : Ġ 3 = 1 / 1 ĊĠĠĠĠĠĠĠ Ġ// Ġc : Ġ 2 = 2 / 3 ; Ġ 6 = 1 / 3 ĠĠ Ġ( 6 Ġis Ġthe Ġalias ) ĊĠĠĠĠĠĠĠ Ġ// Ġd : Ġ 1 = 1 / 3 ; Ġ 6 = 2 / 3 ĠĠ Ġ( 6 Ġis Ġthe Ġalias ) ĊĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġsample Ġis Ġobtained Ġby Ġrandomly Ġselecting Ġa Ġsection , Ġthen Ġchoosing Ġwhich Ġcategory ĊĠĠĠĠĠĠĠ Ġ// Ġfrom Ġthe Ġpair Ġbased Ġon Ġa Ġuniform Ġrandom Ġde vi ate . ĊĠĠĠĠĠĠĠ Ġval Ġsum Prob Ġ= ĠInternal Utils . validate Prob abilities ( prob abilities ) ĊĠĠĠĠĠĠĠ Ġ// ĠAllow Ġzero - padding ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġcompute Size ( prob abilities . size , Ġalpha ) ĊĠĠĠĠĠĠĠ Ġ// ĠPartition Ġinto Ġsmall Ġand Ġlarge Ġby Ġsplitting Ġon Ġthe Ġaverage . ĊĠĠĠĠĠĠĠ Ġval Ġmean Ġ= Ġsum Prob Ġ/ Ġn ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġcardinality Ġof Ġsmall Size Ġ+ Ġlarge Size Ġ= Ġn . ĊĠĠĠĠĠĠĠ Ġ// ĠSo Ġfill Ġthe Ġsame Ġarray Ġfrom Ġeither Ġend . ĊĠĠĠĠĠĠĠ Ġval Ġindices Ġ= ĠInt Array ( n ) ĊĠĠĠĠĠĠĠ Ġvar Ġlarge Ġ= Ġn ĊĠĠĠĠĠĠĠ Ġvar Ġsmall Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġprobabilities . indices . forEach Ġ{ Ġi Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prob abilities [ i ] Ġ>= Ġmean ) Ġindices [ -- large ] Ġ= Ġi Ġelse Ġindices [ small ++] Ġ= Ġi ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġsmall Ġ= Ġfill Remaining Indices ( prob abilities . size , Ġindices , Ġsmall ) ĊĠĠĠĠĠĠĠ Ġ// ĠThis Ġmay Ġbe Ġsmaller Ġthan Ġthe Ġinput Ġlength Ġif Ġthe Ġprobabilities Ġwere Ġalready Ġpadded . ĊĠĠĠĠĠĠĠ Ġval Ġnon Zero Index Ġ= Ġfind Last Non Zero Index ( prob abilities ) ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġprobabilities Ġare Ġmodified Ġso Ġuse Ġa Ġcopy . ĊĠĠĠĠĠĠĠ Ġ// ĠNote : Ġprobabilities Ġare Ġrequired Ġonly Ġup Ġto Ġlast Ġnon Zero Index ĊĠĠĠĠĠĠĠ Ġval Ġremaining Prob abilities Ġ= Ġprobabilities . copyOf ( non Zero Index Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ// ĠAllocate Ġthe Ġfinal Ġtables . ĊĠĠĠĠĠĠĠ Ġ// ĠProb ability Ġtable Ġmay Ġbe Ġtruncated Ġ( when Ġzero Ġpadded ). ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġalias Ġtable Ġis Ġfull Ġlength . ĊĠĠĠĠĠĠĠ Ġval Ġprobability Ġ= ĠLong Array ( remaining Prob abilities . size ) ĊĠĠĠĠĠĠĠ Ġval Ġalias Ġ= ĠInt Array ( n ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠThis Ġloop Ġuses Ġeach Ġlarge Ġin Ġturn Ġto Ġfill Ġthe Ġalias Ġtable Ġfor Ġsmall Ġprobabilities Ġthat ĊĠĠĠĠĠĠĠ Ġ// Ġdo Ġnot Ġreach Ġthe Ġrequirement Ġto Ġfill Ġan Ġentire Ġsection Ġalone Ġ( i . e . Ġp Ġ< Ġmean ). ĊĠĠĠĠĠĠĠ Ġ// ĠSince Ġthe Ġsum Ġof Ġthe Ġsmall Ġshould Ġbe Ġless Ġthan Ġthe Ġsum Ġof Ġthe Ġlarge Ġit Ġshould Ġuse Ġup ĊĠĠĠĠĠĠĠ Ġ// Ġall Ġthe Ġsmall Ġfirst . ĠHowever Ġfloating Ġpoint Ġround - off Ġcan Ġresult Ġin ĊĠĠĠĠĠĠĠ Ġ// Ġmis classification Ġof Ġitems Ġas Ġsmall Ġor Ġlarge . ĠThe ĠV ose Ġalgorithm Ġhandles Ġthis Ġusing ĊĠĠĠĠĠĠĠ Ġ// Ġa Ġwhile Ġloop Ġcondition ed Ġon Ġthe Ġsize Ġof Ġboth Ġsets Ġand Ġa Ġsubsequent Ġloop Ġto Ġuse ĊĠĠĠĠĠĠĠ Ġ// Ġun paired Ġitems . ĊĠĠĠĠĠĠĠ Ġwhile Ġ( large Ġ!= Ġn Ġ&& Ġsmall Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIndex Ġof Ġthe Ġsmall Ġand Ġthe Ġlarge Ġprobabilities . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġindices [ -- small ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġindices [ large ++] ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠOptim isation Ġfor Ġzero - padded Ġinput : ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġp ( j ) Ġ= Ġ 0 Ġabove Ġthe Ġlast Ġnon Zero Index ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( j Ġ> Ġnon Zero Index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġentire Ġamount Ġfor Ġthe Ġsection Ġis Ġtaken Ġfrom Ġthe Ġalias . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremaining Prob abilities [ k ] Ġ-= Ġmean ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpj Ġ= Ġremaining Prob abilities [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠItem Ġj Ġis Ġa Ġsmall Ġprobability Ġthat Ġis Ġbelow Ġthe Ġmean . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCompute Ġthe Ġweight Ġof Ġthe Ġsection Ġfor Ġitem Ġj : Ġpj Ġ/ Ġmean . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġis Ġscaled Ġby Ġ 2 ^ 5 3 Ġand Ġthe Ġce iling Ġfunction Ġused Ġto Ġround - up ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġprobability Ġto Ġa Ġnum erator Ġof Ġa Ġfraction Ġin Ġthe Ġrange Ġ[ 1 , 2 ^ 5 3 ]. ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCe iling Ġensures Ġnon - zero Ġvalues . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprobability [ j ] Ġ= Ġceil ( CONVERT _ TO _ NUM ER ATOR Ġ* Ġ( pj Ġ/ Ġmean )). to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġremaining Ġamount Ġfor Ġthe Ġsection Ġis Ġtaken Ġfrom Ġthe Ġalias . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠEffect ively : Ġprobabilities [ k ] Ġ-= Ġ( mean Ġ- Ġpj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremaining Prob abilities [ k ] Ġ+= Ġpj Ġ- Ġmean ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIf Ġnot Ġj Ġthen Ġthe Ġalias Ġis Ġk ĊĠĠĠĠĠĠĠĠĠĠĠ Ġalias [ j ] Ġ= Ġk ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAdd Ġthe Ġremaining Ġprobability Ġfrom Ġlarge Ġto Ġthe Ġappropriate Ġlist . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( remaining Prob abilities [ k ] Ġ>= Ġmean ) Ġindices [ -- large ] Ġ= Ġk Ġelse Ġindices [ small ++] Ġ= Ġk ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠFinal Ġloop Ġconditions Ġto Ġconsume Ġun paired Ġitems . ĊĠĠĠĠĠĠĠ Ġ// ĠNote : ĠThe Ġlarge Ġset Ġshould Ġnever Ġbe Ġnon - empty Ġbut Ġthis Ġcan Ġoccur Ġdue Ġto Ġround - off ĊĠĠĠĠĠĠĠ Ġ// Ġerror Ġso Ġconsume Ġfrom Ġboth . ĊĠĠĠĠĠĠĠ Ġfill Table ( probability , Ġalias , Ġindices , Ġ 0 , Ġsmall ) ĊĠĠĠĠĠĠĠ Ġfill Table ( probability , Ġalias , Ġindices , Ġlarge , Ġn ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠChange Ġthe Ġalgorithm Ġfor Ġsmall Ġpower Ġof Ġ 2 Ġsized Ġtables ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( is Small Power Of 2 ( n )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠSmall Table Alias Method Discrete Sampler ( probability , Ġalias ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠAlias Method Discrete Sampler ( probability , Ġalias ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ