package Ġchapter 3 . section 4 Ċ Ċ import Ġextensions . format Double Ċ import Ġextensions . random Ċ import Ġkotlin . math . sqrt Ċ Ċ /** Ċ Ġ* Ġ åį¡ æĸ¹ åĢ¼ ï¼Ī chi - square Ġstatistic ï¼ī Ċ Ġ* Ġä¸º Separ ate Ch aining Hash ST æ·»åĬł ä¸Ģä¸ª æĸ¹æ³ķ æĿ¥ è®¡ç®Ĺ æķ£ åĪĹè¡¨ çļĦ X Â² Ċ Ġ* Ġ å¯¹äºİ å¤§å°ı ä¸º M å¹¶ åĲ« æľī N ä¸ª åħĥç´ł çļĦ æķ£ åĪĹè¡¨ ï¼Į è¿Ļä¸ª åĢ¼çļĦ å®ļä¹ī ä¸º ï¼ļ Ċ Ġ* ĠX Â² Ġ= Ġ( M Ġ/ ĠN )(( f âĤ Ģ Ġ- ĠN Ġ/ ĠM ) Â² Ġ+ Ġ( f âĤģ Ġ- ĠN Ġ/ ĠM ) Â² Ġ+ Ġ... Ġ+ Ġ( f ( m - 1 ) Ġ- ĠN Ġ/ ĠM ) Â² ) Ċ Ġ* Ġ åħ¶ä¸Ń ï¼Į f ( i ) ä¸º æķ£ åĪĹ åĢ¼ä¸º i çļĦ éĶ® çļĦ æķ°éĩı Ċ Ġ* Ġ è¿Ļä¸ª ç»Łè®¡ æķ°æį® æĺ¯ æ£Ģæµĭ æĪĳä»¬çļĦ æķ£ åĪĹ åĩ½æķ° äº§çĶŁ çļĦ éļıæľº åĢ¼ æĺ¯åĲ¦ æ»¡è¶³ åģĩ è®¾ çļĦ ä¸Ģç§į æĸ¹æ³ķ Ċ Ġ* Ġå¦Ĥæŀľ æ»¡è¶³ ï¼Į å¯¹äºİ N > cM ï¼Į è¿Ļä¸ª åĢ¼ èĲ½ åľ¨ ĠM Ġ- Ġsqrt ( M ) ĠåĴĮ ĠM Ġ+ Ġsqrt ( M ) Ġ ä¹ĭéĹ´çļĦ æ¦Ĥ çİĩ ä¸º Ġ 1 Ġ- Ġ 1 / c Ċ Ġ* Ċ Ġ* Ġ è§£ ï¼ļ c ä¸º ä¸Ģä¸ª å°ı å¸¸ æķ° ï¼Į å¤§å°ı çŃīäºİ N / M ï¼Ī åĲĳ ä¸ĭ åıĸ æķ´ ï¼ī Ċ Ġ* Ġ éļıæľº çĶŁæĪĲ N ä¸ª éĶ® æıĴåħ¥ åĪ° Hash è¡¨ ä¸Ń ï¼Į è®¡ç®Ĺ åį¡ æĸ¹ åĢ¼ ï¼Į åĪ¤æĸŃ æĺ¯åĲ¦ åľ¨ ĠM Ġ- Ġsqrt ( M ) ĠåĴĮ ĠM Ġ+ Ġsqrt ( M ) Ġ ä¹ĭéĹ´ Ċ Ġ* Ġ éĩįå¤į å¤ļ æ¬¡ ï¼Į è®¡ç®Ĺ åį¡ æĸ¹ åĢ¼ åľ¨ èĮĥåĽ´ åĨħ çļĦ å®ŀéĻħ æ¦Ĥ çİĩ ï¼Į ä¸İ æľŁ æľĽ æ¦Ĥ çİĩ Ġ 1 Ġ- Ġ 1 / c Ġå¯¹ æ¯Ķ Ċ Ġ* Ġ åį¡ æĸ¹ åĢ¼ è¶Ĭ å°ı ï¼Į æķ°æį® åĪĨå¸ĥ è¶Ĭ åĿĩ åĮ Ģ Ċ Ġ*/ Ċ fun Ġ< K Ġ: ĠAny , ĠV Ġ: ĠAny > ĠSepar ate Ch aining Hash ST < K , ĠV >. chi Square Statistic (): ĠDouble Ġ{ ĊĠĠĠ Ġval Ġarray Ġ= ĠInt Array ( m ) ĊĠĠĠ Ġkeys (). forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġarray [ hash ( it )] ++ ĊĠĠĠ Ġ} ĊĠĠĠ Ġvar Ġsum Ġ= Ġ 0 . 0 ĊĠĠĠ Ġval Ġmn Ġ= Ġm . toDouble () Ġ/ Ġn ĊĠĠĠ Ġval Ġnm Ġ= Ġn . toDouble () Ġ/ Ġm ĊĠĠĠ Ġarray . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġsum Ġ+= Ġ( it Ġ- Ġnm ) Ġ* Ġ( it Ġ- Ġnm ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġmn Ġ* Ġsum Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġsize Ġ= Ġ 1 0 0 ĊĠĠĠ Ġval Ġmax Key Ġ= ĠInt . MAX _ VALUE ĊĠĠĠ Ġval Ġrepeat Times Ġ= Ġ 1 0 0 0 ĊĊĠĠĠ Ġval ĠN Ġ= Ġsize ĊĠĠĠ Ġvar ĠM Ġ= Ġ 4 ĊĠĠĠ Ġ// æł¹æį® N çļĦ å¤§å°ı ï¼Į è®¡ç®Ĺ åľ¨ åıª æıĴåħ¥ ä¸į åĪłéĻ¤ çļĦ æĥħåĨµä¸ĭ M çļĦ å¤§å°ı ĊĠĠĠ Ġwhile Ġ( N Ġ> Ġ 8 Ġ* ĠM ) Ġ{ ĊĠĠĠĠĠĠĠ ĠM Ġ*= Ġ 2 ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġc Ġ= ĠN Ġ/ ĠM ĊĠĠĠ Ġval Ġmin Ġ= ĠM Ġ- Ġsqrt ( M . toDouble ()) ĊĠĠĠ Ġval Ġmax Ġ= ĠM Ġ+ Ġsqrt ( M . toDouble ()) ĊĠĠĠ Ġprintln (" N =$ N Ġ ĠM =$ M Ġ Ġc =$ c ") ĊĠĠĠ Ġprintln (" min =${ format Double ( min , Ġ 2 )} ") ĊĠĠĠ Ġprintln (" max =${ format Double ( max , Ġ 2 )} ") ĊĠĠĠ Ġprintln (" Expected Ġprobability : Ġ( 1 - 1 / c ) Ġ= Ġ${ format Double ( 1 Ġ- Ġ 1 . 0 Ġ/ Ġc , Ġ 2 )} ") ĊĊĠĠĠ Ġvar Ġcount Ġ= Ġ 0 ĊĠĠĠ Ġrepeat ( repeat Times ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġst Ġ= ĠSepar ate Ch aining Hash ST < Int , ĠInt >() ĊĠĠĠĠĠĠĠ Ġwhile Ġ( st . size () Ġ< Ġsize ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġst . put ( random ( max Key ), Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġst . chi Square Statistic () ĊĠĠĠĠĠĠĠ Ġif Ġ( value Ġin Ġmin .. max ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcount ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" Actual Ġprobability : Ġ${ format Double ( count . toDouble () Ġ/ Ġrepeat Times , Ġ 2 )} ") Ċ Ċ }