Jenks "natural breaks" implementation in rust, for the fun

jenks.rs

extern crate rustc_serialize;
extern crate time;

use time::PreciseTime;
use rustc_serialize::json;
use std::fs::File;
use std::io::Read;
use std::f64;

#[derive(RustcDecodable, RustcEncodable)]
pub struct TestStruct  {
    values: Vec<f64>
}

// Lets fake a 2D array (square shape matrix) with a 1D vector:
struct Matrix<T>{
    values: Vec<T>,
    dim: usize
}

// ... and implement getter and setter methods using 'unsafe' functions :
impl<T: PartialEq + Clone> Matrix<T> {
    pub fn new(init_value: T, dim: usize) -> Matrix<T> {
        Matrix { values: vec![init_value; dim * dim], dim: dim }
    }

    #[inline(always)]
    pub fn get(&self, ix: (usize, usize)) -> &T {
        unsafe { self.values.get_unchecked(ix.0 * self.dim + ix.1) }
    }

    #[inline(always)]
    pub fn set(&mut self, ix: (usize, usize), value: T) {
        let mut v = unsafe { self.values.get_unchecked_mut(ix.0 * self.dim + ix.1) };
        *v = value;
    }
}

// Slightly optimized version using the custom Matrix object :
fn get_breaks(values: &mut [f64], nb_class: u32) -> Vec<f64> {
    let k = nb_class as usize;
    let nb_elem: usize = values.len();
    let mut v1 = Matrix::new(1, nb_elem);
    let mut v2 = Matrix::new(f64::MAX, nb_elem);

    values.sort_by(|a, b| a.partial_cmp(b).unwrap());

    let (mut v, mut val, mut s1, mut s2, mut w, mut i3, mut i4):
            (f64, f64, f64, f64, f64, usize, usize);

    for l in 2..(nb_elem + 1) {
        s1 = 0.0; s2 = 0.0; w = 0.0;
        for m in 1..(l+1) {
            i3 = l - m + 1;
            val = unsafe { *values.get_unchecked(i3-1) };
            s2 += val * val;
            s1 += val;
            w += 1.0;
            v = s2 - (s1 * s1) / w;
            i4 = i3 - 1;
            if i4 != 0 {
                for j in 2..k+1 {
                    let _v = v + v2.get((i4-1, j-2));
                    if *v2.get((l-1, j-1)) >= _v {
                        v2.set((l-1, j-1), _v);
                        v1.set((l-1, j-1), i3);
                    }
                }
            }
            v1.set((l-1, 0), 1);
            v2.set((l-1, 0), v);
        }
    }
    let mut kclass = vec![0; k as usize];
    let mut k = nb_elem as u32;
    let mut j = nb_class;
    while j > 1 {
        k = *v1.get(((k-1) as usize, (j-1) as usize)) as u32 - 1;
        kclass[(j - 2) as usize] = k;
        j -= 1;
    }
    let mut breaks = Vec::with_capacity(nb_class as usize);
    breaks.push(values[0]);
    for i in 1..nb_class {
        breaks.push(values[(kclass[(i - 1) as usize] - 1) as usize]);
    }
    breaks.push(values[(nb_elem - 1)]);
    breaks
}

// Naive translation of jenks natural breaks method from :
// https://github.com/mthh/jenkspy/blob/master/jenkspy/src/_jenks.c
fn get_breaks_0(values: &mut [f64], nb_class: u32) -> Vec<f64> {
    let nb_elem: usize = values.len();
    let mut v1 = Vec::with_capacity(nb_elem);
    for _ in 0..nb_elem {
        v1.push(vec![1; nb_elem]);
    }
    let mut v2 = Vec::with_capacity(nb_elem);
    for _ in 0..nb_elem {
        v2.push(vec![f64::MAX; nb_elem]);
    }
    values.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let k = nb_class as usize;
    let (mut v, mut val, mut s1, mut s2, mut w, mut i3, mut i4): (f64, f64, f64, f64, f64, usize, usize);
    for l in 2..(nb_elem + 1) {
        s1 = 0.0; s2 = 0.0; w = 0.0;
        for m in 1..(l+1) {
            i3 = l - m + 1;
            val = values[(i3-1)];
            s2 += val * val;
            s1 += val;
            w += 1.0;
            v = s2 - (s1 * s1) / w;
            i4 = i3 - 1;
            if i4 != 0 {
                for j in 2..k+1 {
                    if v2[(l-1)][(j-1)] >= (v + v2[(i4-1)][(j-2)]) {
                        v1[(l-1)][(j-1)] = i3;
                        v2[(l-1)][(j-1)] = v + v2[(i4-1)][(j-2)];
                    }
                }
            }
            v1[(l-1)][0] = 1;
            v2[(l-1)][0] = v;
        }
    }

    let mut kclass = vec![0; k as usize];
    let mut k = nb_elem as u32;
    let mut j = nb_class;
    while j > 1 {
        k = v1[(k-1) as usize][(j-1) as usize] as u32 - 1;
        kclass[(j - 2) as usize] = k;
        j -= 1;
    }
    let mut breaks = Vec::with_capacity(nb_class as usize);
    breaks.push(values[0]);
    for i in 1..nb_class {
        breaks.push(values[(kclass[(i - 1) as usize] - 1) as usize]);
    }
    breaks.push(values[(nb_elem - 1)]);
    breaks
}


fn main() {
    let mut file = File::open("/tmp/values.json").unwrap();
    let mut raw_json = String::new();
    file.read_to_string(&mut raw_json).unwrap();
    let mut decoded: TestStruct = json::decode(&raw_json).unwrap();
    let start = PreciseTime::now();
    let breaks = get_breaks(decoded.values.as_mut_slice(), 5);
    let end = PreciseTime::now();
    println!("{:?}", breaks);
    println!("{:.5} s", start.to(end));
    let start = PreciseTime::now();
    let breaks = get_breaks_0(decoded.values.as_mut_slice(), 5);
    let end = PreciseTime::now();
    println!("{:?}", breaks);
    println!("{:.5} s", start.to(end));
}

values.json

{"values":[5.0051212497,6.7698845686,1.0215867334,9.3858864438,4.5483103534,6.3546030759,8.9762534946,5.1917132363,4.77156081,7.8637124482,6.6415011836,6.910042502,3.1715067266,0.8732599649,4.4886537432,8.2034412539,9.454990027,4.7438093321,2.5307508395,1.0617040214,5.6928063324,9.5963630127,8.7410023529,7.5697352435,9.6920031402,4.7011061828,0.2546724747,4.1838355712,8.2837072085,0.4071679199,0.8745960821,1.1438903492,8.0917591718,7.5315790134,3.8455851935,6.9376700348,9.1547342227,8.5312359128,0.5893597682,2.1916877176,8.5723504284,5.6544681499,4.8722819961,7.7743078629,3.4583821078,0.2145968121,5.6511488068,8.1706982269,3.7933325185,3.5380436806,5.2621948044,4.9069017754,7.5653072866,0.5521937623,3.6833292455,3.1848908961,3.2477069274,4.1955179046,2.6592070377,4.4231758523,9.5178354415,3.8378226245,4.352589515,2.3772501433,3.6055122875,3.7833979214,8.0005479488,6.7187818652,9.8877203278,8.0474645388,1.3808186585,1.1643479788,3.2511105994,7.064545583,6.0153465043,3.0592047097,0.1154045411,8.064222571,8.1501906761,7.3568894574,7.5550758583,8.8466105959,2.735012332,2.8688491881,5.7528817584,4.4839684712,3.128918393,1.8225139007,7.3200027226,7.3102148063,3.1840061769,7.5293671805,3.4418908251,0.6517991703,6.7385020503,8.9155908674,6.2767903972,2.6163079101,6.6293653147,5.1761860866,9.0197555698,8.8136379491,1.5809390135,8.6088461336,6.2970922934,3.3662802842,3.61570006,7.3856783984,3.0267058546,4.5121887722,8.1923996285,9.4054855243,9.2599294987,7.2863114346,3.1834652484,4.2787704291,5.7169532683,0.5789715587,3.8978533656,2.7586988173,5.0599757303,2.365149206,7.2583966795,8.9218597091,0.7392698503,5.230259886,7.8994352068,4.0961131454,4.3893147446,1.6261946969,5.4821873549,3.6197618814,6.7433681595,5.9372771229,7.2416702169,3.9092640253,3.0374779948,4.2955951928,6.5644671489,3.4312051092,7.9944204702,8.5763272946,9.3109349161,4.144410803,4.4723670627,4.2593774223,2.6667816914,2.458972868,7.6309060352,0.9030878497,0.832257201,4.516582794,6.8043793901,6.6036854777,8.6169670848,9.8976201122,3.5385293327,6.72315781,9.5025769388,1.9289991958,1.802149266,0.3319901507,2.8302988247,1.7497945065,8.6411198019,6.7531909607,5.0879396405,0.240972857,7.7737987298,0.0763043389,5.8311795513,1.9803082594,9.0211864538,6.743094665,1.1699359631,4.4256951823,4.4112041965,0.436347269,0.0162104936,5.219610997,1.8238594756,4.3910725624,1.6635660687,2.3273232579,3.8895407622,0.3493748629,4.9977824371,1.4709878433,5.1340171904,8.7248193007,8.4398504999,9.6176903066,8.4661753639,5.2613173937,5.368968558,0.6398360827,2.8225722164,8.9385000197,7.1471819771,8.1288773357,9.5355569641,3.1864461838,6.4882778493,9.0027410421,9.9266525498,2.0176753146,1.8869244936,7.8294691979,9.8774985457,8.0600334797,7.2248560702,1.2798929936,2.788669141,2.9158523772,8.7279706355,0.1009403518,1.2769153342,9.9171980121,3.9630167349,4.3052708521,0.390720109,1.423713034,7.4041171605,2.1246325527,5.7389115426,8.45550064,0.3971548076,0.3838036326,7.65138936,1.1605408695,9.0199161461,8.3913252666,0.251629774,3.8718667952,9.3640757375,8.0194267863,1.9251802214,1.6824836819,4.3521748832,6.440906967,5.6704554032,9.133556725,9.6745781391,3.5517720412,4.3583416776,0.5826962716,4.6187413856,3.460795274,6.2790876324,5.7070495025,1.2955440115,3.9778111945,6.0866498319,3.3673160942,7.9540996486,9.67517443,2.9813746945,6.1050392431,9.0727066947,1.0152084474,5.0129653653,4.4952176278,4.8282299633,2.8027904942,9.7262738179,8.3937160112,2.9691689159,0.5977230123,3.2966522267,1.9834079663,2.4438132974,9.3139135861,9.5932520623,9.5617715805,4.5655260584,3.5656980681,2.9371935944,0.2357974043,8.6475035874,5.5287191994,3.202123926,1.8626428116,7.1620868775,8.0092401663,2.8634931124,1.7266137595,1.3530070381,6.1247731652,0.3922454012,5.3899981198,7.7855574246,2.0238707634,4.9110972136,9.156511554,7.6986506651,5.1722732279,1.7033808166,0.2752389759,8.3660371322,4.0275136475,0.5095890816,2.6868695091,0.8549958374,8.3704469935,0.1689472864,9.1554383026,1.9793402008,3.9153014589,8.6760735814,7.2582098795,5.1052815118,0.3322519967,1.6601247829,0.5513627781,1.5807324997,7.9406681773,1.720573362,9.6036910452,2.8630179027,4.0472751227,9.3548159814,5.8941960149,8.8982731011,1.2117962702,3.4274517698,1.6751115024,7.4504411872,6.333751285,9.1910681222,4.7519521834,6.5078606433,3.5455762362,6.3690619939,3.5792935127,0.1988406247,9.8906866345,9.9031920917,1.2413786934,5.3228048235,8.168133283,7.9367644968,5.9427399933,0.9801914124,5.6340152677,6.3429148006,1.796745446,2.8216620442,9.0463081817,7.7341552754,6.8921452691,0.040803398,2.199298495,1.31714524,0.3238699678,8.6449077609,4.6675590915,3.7622552318,2.1254901192,2.846966621,8.9562551421,1.2864466198,5.9537597839,7.5466773566,9.9816392479,6.5303195384,1.8452655454,2.3217288847,2.8669062979,7.2996079107,3.2807708974,8.2992026256,5.9492160846,4.4606668036,3.553754522,5.6664344016,9.560894852,5.3472389746,0.3324538213,5.2127246093,4.8064121883,5.2229755535,1.4713243209,2.8643993102,8.9655557717,9.2829518812,1.2171179173,4.6082876041,0.5520726275,8.6759544048,7.7139904513,0.1357484772,3.2274405868,8.7829452986,6.045098491,8.6388255167,4.7335436195,4.0975441574,3.721517385,4.0211919229,6.2904489599,8.4663729463,4.7890860797,8.0299079069,7.9173163208,1.7982503399,9.0519179101,9.2198235774,8.3048032993,6.587984832,0.4525634693,9.2054766626,8.6919519561,3.1331573264,7.3399449629,4.3294527242,1.1765588284,6.4354366763,9.5293662534,5.6082141842,5.4227854824,4.2876495654,8.0587595701,8.2397920545,4.0511515946,8.4688519198,6.6855076631,4.9704337539,2.0520593179,9.2528506019,9.7653141082,9.1014114162,2.4982762104,2.5175985252,1.5851920936,3.5294777341,1.9903180748,7.2821984999,1.450364925,1.4495945163,4.4885895238,6.9701784849,3.2286071195,9.5088430867,5.9691388533,9.3602676038,8.2010316686,5.5044139503,0.4443631601,8.7943652086,6.4783376968,3.0571653158,4.6949605993,8.5105563654,5.7216062536,3.7706760084,7.1668785671,4.9770147656,5.109445441,9.1610179632,2.3393165739,4.1600928502,5.534558252,5.5712345941,5.8291490516,3.7799159717,4.4907212467,2.9286981048,7.8379463032,9.0973226493,5.2843802562,6.5691277408,0.1422423613,0.711256694,3.2313932688,8.6490881979,6.337066188,0.8665623586,0.5975108221,9.2250468745,7.0210172795,3.0328386324,0.8192361426,1.8364296993,6.6794746043,9.5007709996,5.66981507,0.4693304677,0.5351261119,2.2100798343,8.722575556,6.4983427431,1.0846159584,3.6406051205,2.3855150328,6.7600693228,5.3292645514,8.4477175935,5.7503915927,4.457062541,2.3979609739,1.4404313872,0.9434649488,3.8073990773,0.8290260541,6.0765785724,2.8896208457,1.7025700794,7.788806851,5.1250955323,2.2542439564,2.318345136,3.9721389511,0.41902625,9.2458194261,8.262916829,3.3151939441,5.9211458359,0.0350020546,7.3697825894,4.3838127772,5.8891779673,9.9238578696,2.3554238467,2.9555017827,3.7899259874,8.4105505259,9.4144649524,8.0093620834,0.7033347874,1.8303936417,5.8143423195,9.2485313094,4.3787982618,0.6746661966,1.0530447843,8.3368236758,0.2969857119,9.1749484418,5.1829547202,1.473905961,0.9499002108,6.4988583932,5.646643748,4.8816988408,8.3102695807,3.422914166,4.4309894252,9.8395845201,4.9321964337,9.5982127334,4.0786333871,2.124364418,6.2059289543,1.1621719203,2.0755003393,5.2476913016,9.6165024536,0.846674887,1.372740767,3.2300059544,3.739797147,6.974140224,7.6050244272,8.8588144165,3.020158275,8.5136887617,6.1404573219,9.818810618,4.8142493493,3.586849682,5.6919042789,0.085786297,8.1217115209,0.2463038545,0.6316715828,6.4054446877,1.2473343336,5.8771313797,7.1428144327,4.0841301228,5.3019098728,0.6986237247,5.5787741765,6.9220947078,3.1462549372,5.2410068247,7.2322906391,0.6026483444,1.3768058666,0.0800355617,3.0564850918,0.3639152017,9.6485299151,0.8321366808,4.8639202933,0.0472958409,4.5575349405,8.9540180913,2.7282340755,3.9430438704,8.676431994,7.0243494911,7.7064523823,7.4749768921,9.0132087539,3.9839014807,3.253230874,3.8566319575,0.6799420156,4.0719332267,3.9262308925,3.7392733758,1.5917768306,0.2792204847,1.5261770808,6.645503242,7.3958471068,5.8036507526,4.9262922769,3.2169264695,4.9417629931,6.1988979112,1.5975867538,8.3122632816,0.1483439165,2.0299306372,6.402105689,6.1132633896,1.9852822856,2.5057383953,8.1421350501,8.0301971873,0.9432496969,3.5533405188,1.2001235737,7.0014568768,0.8712048992,7.2181463894,3.1080481946,0.5959121184,8.9379042899,4.4350274233,5.265623217,9.983510403,7.9592666985,6.3203721377,6.3003423205,5.4631600995,3.3636903018,8.0741570168,6.806202936,8.2662410941,5.3701273864,6.1155871302,3.5212122928,3.62703213,9.3350736308,0.2766379411,3.497081555,6.3366824947,1.0654873517,2.2779573663,7.5455662352,5.95419741,5.8067312976,4.0156024043,9.5250505139,4.7715044115,2.7979273931,3.2749838871,9.455635848,0.0987981213,2.4449413153,5.5180201074,6.2960102805,1.5926192515,6.3276431197,3.2402966917,7.0537514868,1.5324516059,5.8819860662,6.6874419479,7.0112325251,5.2719692001,6.413867732,8.9238166925,9.0830893628,7.6749324985,8.7926184619,1.5498139733,4.9226353364,6.5072737681,5.2284947131,5.3516879468,2.0744572673,7.139236934,5.4091268126,0.9846348548,9.1324524465,9.7887055809,7.0625546831,4.3790810648,1.4590923139,8.8724365132,7.8242555773,1.9047077163,5.9130574437,3.9563180832,8.4150011721,6.5931602847,9.4657318946,1.5623756009,7.2310871887,7.9685638077,4.2409195984,9.750124081,9.5773246232,5.5242328555,8.8760567294,5.4196444713,3.8573184912,8.7106027128,7.3835266824,2.6232833858,2.1672166488,0.6891097198,1.5929507255,7.552667181,6.1127998214,3.2445063163,5.7613124023,1.4269530005,6.7576295254,9.0556223597,4.4906359632,3.0054055434,3.1100730877,3.3364752424,9.0204588114,6.6658121836,0.5622236524,0.244181233,6.4589992049,9.1136019095,5.3321219678,9.0514676529,2.5377386273,0.0661792886,8.953536253,9.6259054774,9.8712103814,0.0609339657,5.5009181844,6.1363986786,3.4552490246,7.0224037464,4.1860766872,9.4471835857,0.7258855388,4.1939826705,4.0737627912,3.4852795885,7.124344192,7.4344271957,2.0588918217,6.1080350121,9.7007781081,7.4055141816,4.4057040056,1.5880355379,8.6682892987,0.9236494894,0.5630778265,4.675268936,7.8915366856,8.9535788912,1.1104525882,1.1140574119,5.1482629194,2.810939888,8.9861274278,4.7421316663,1.7298473627,2.5206953078,4.1063871328,9.701968322,7.7596401982,5.740222258,0.2412085724,1.4410786494,8.0098978896,8.9365295018,0.952255954,3.4324977361,6.402885376,3.2343128999,8.3331641089,3.9870322682,0.9197108727,5.1286206581,2.3768175533,1.0331127932,8.4317527013,3.8787931437,7.1158621367,5.1293467148,9.4396273233,2.7304852381,3.11334525,7.3893925897,2.1368330112,6.7029131879,9.6704792581,1.3177918969,8.4388387902,5.0052375114,0.182511555,4.0377202444,6.4336102456,3.1418353994,0.7609018008,3.2746874215,9.8260477372,2.9710332467,7.2437911923,8.3906331635,4.1798886633,3.8754750136,6.6800550418,5.404357824,7.2096252139,0.3217452136,0.5552434921,4.3987709377,9.3277408974,1.0799965169,0.7827811805,6.2975780736,0.942754331,5.4021975538,9.3627410242,4.0488712094,8.3524423372,0.653125844,8.3224081527,0.4232423333,8.5295394063,8.8782728207,9.4755447353,9.2528028926,3.4703456797,7.4127009907,6.7453698814,8.362561122,9.6110628662,9.2469066172,1.7375518731,5.2800824214,2.023140504,0.2711749193,8.9907723735,2.1041698242,8.8307032688,5.4211460007,8.2417227328,3.0479990225,8.5892618564,9.1141714389,2.8966386034,7.7794482349,8.4051411715,2.2412185255,1.1118765827,0.1547526801,9.2196236202,2.338803187,6.7496290035,7.110002581,8.5826423718,9.6557070571,2.7770355204,9.1631856631,2.1187206404,7.4878419936,0.7285763696,3.8358826097,4.9580773292,3.3186359121,7.4941443815,9.8050617171,1.4622714277,1.2707394804,7.3727914132,6.7667090613,5.2200390282,2.0707297744,7.1552171605,9.5674396656,2.1715411195,3.0287244148,2.0935479691,5.7181795058,1.3374383771,1.4437670982,2.2299876017,5.629292957,4.4380802009,2.8963091038,3.231126254,9.2587701674,7.682583821,0.3442920558,7.5287919142,4.2851308663,3.3373237471,3.9863606193,2.7974618948,0.5093348119,8.1616713363,3.6710569193,0.1563941967,4.7857748368,4.3715804117,5.5947009264,4.1961866897,3.5285426397,7.6244664611,7.8219761048,7.6416059537,4.0900733299,9.3029518262,7.2078799736,4.9203983787,9.2906846083,5.7747784001,0.8102608169,6.0037497664,9.8650813242,9.61276046,7.5484587695,0.2787048486,3.6695049051,7.0469243941,4.7873572633,0.6901481701,1.3847953011,1.3659868157,5.8180590789,6.0368411872,7.2474203305,0.5867991876,7.9188463953,4.8168946709,9.7601638688,3.7618942652,9.6041162661,3.8879027497,2.6454447838,6.8812884646,3.4451603051,9.4800399896,6.9618002721,9.1760438867,3.7707790383,7.4324827502,7.6647729566,7.7939304872,2.525892132,8.5061654332,0.7726947125,7.1324224025,0.2727644006,6.2064317265,9.7078801924,4.9949804344,7.6187174721,1.5810609725,9.9109119456,8.3360318048,3.2491677604,0.0287311291,7.4275740236,8.3362739044,1.8594216602,1.4347189758,6.4753169636,6.3930609147,2.1497969236,0.3960242611,9.8048835783,5.756679147,7.7590328036,6.2752710842,0.6845211145,6.3028540462,8.5037713568,0.6995680905,4.5952068688,5.7395926048,8.9026730112,0.3918302967,7.7994551952,0.6336134649,0.5764604663,0.6564780651,4.4662311813,0.3632602771,0.979608295,5.0161297712,3.038275037,2.7278555394,9.5051830588,4.7300000768,8.8150920789,9.6614927216,2.2802249808,3.8568667253,2.2590105166,1.1880779057,6.3697996549,6.863516795,5.4717034544,2.6916230214,4.491359049,7.9602705478,9.1856046836,0.4053650307,3.9404865541,8.9940001001,0.2866260614,9.0608970704,8.8809234276,5.629572242,5.5957773468,7.7909958106,6.6403291398,3.8866658602,4.3929171027,0.8180146944,4.092508296,1.3150955271,3.2104334189,3.3437710279,0.7922920189,7.467067882,2.7943023411,7.3500467278,8.955614178,0.6924187858,2.9766863375,2.9829000798,5.1491635479,0.7587808021,5.4958090559,9.8957632016,1.998029775,5.680950589,0.2833250258,5.1608632877,3.306195545,6.1267066631,5.0927192252,3.4719966818,0.4084557015,8.8095458527,0.4124013521,0.700767946,4.644989185,5.4029572732,3.1835155142,8.8741686684,2.0051661506,3.6553915264,3.3422774379,0.7016782579,0.5557832704,2.1724525979,0.7305986527,5.1154872263,5.323966674,5.2801834792,9.2962589581,1.8281864934,1.5077325911,0.6386737898,9.8960546497,3.4317777283,5.6526692468,0.6770251715,2.5347269606,9.6335919132,5.1608078671,5.9131023893,2.773058149,7.7163035376,1.0102198226,7.5028596306,1.4081776724,1.2599345134,1.4842764963,7.3650927236,6.7169010499,1.1312897271,8.296968115,9.1033258196,8.5766872275,4.25838297,2.8992986982,4.5222068415,0.5454922491,4.3343088264,6.1733072111,8.5806481494,1.7529653269,1.5858782339,0.2874048753,5.118917292,9.3301194743,2.4076012988,5.6703683152,1.7356508831,0.1267453935,1.237001142,5.2237984631,8.840755166,8.2231729361,1.0479398724,9.1271570325,5.0065735867,0.5894318339,2.6026442065,1.0727001913,3.6778146261,0.6211163616,7.0653253119,4.7994065657,3.7542345491,2.2943412489,0.1220970694,4.2604147503,8.1831264147,9.9498044653,5.6013149605,4.2517894646,5.6607518601,0.7730075158,4.0066203289,7.100624938,9.8267077236,7.9794110474,2.9296512692,5.5398171791,2.1196571947,7.3895186326,3.0125506641,7.9953143117,0.3096372262,9.109576426,4.8500334029,5.8367372653,8.5672791093,6.9913769816,4.7195562115,9.2110670288,5.1373875537,9.1947404598,6.912961232,5.4660759587,4.4195722695,6.1711085401,9.8102781526,0.7726565748,3.3136177016,2.9208907369,9.491652071,2.2066241479,0.575649438,7.1542758564,8.2387069822,3.5841460759,5.0641900953,2.0595223363,2.1762049384,5.7350698858,0.854919171,7.8262191755,6.6133759404,1.7721033306,1.6580536519,3.311698013,9.7092302958,2.0702648,7.2538165329,4.2545690713,7.0067282277,9.3115217588,3.4660426667,3.0842236266,5.7374973432,5.7202368812,0.9332084935,1.9149792078,4.2891683197,7.0540537778,3.6747659929,3.7359976512,2.2716926644,3.9721812215,9.4676834252,0.5641223234,3.7870318675,6.8583650375,1.3455796614,1.6292286152,4.8217276018,7.9270855011,0.0480265706,7.2614683444,8.9201713889,6.5841389634,5.7973924745,5.5032587191,5.377397791,9.1806504666,7.6735916175,2.331472307,5.2716720314,4.652883606,7.241878286,4.0068393108,8.9045431511,5.7001449284,7.2534118569,5.5081171892,4.3101291033,7.2566920263,9.4905834063,3.8978980179,0.8199827094,2.2928559873,8.6331156804,4.0077870875,2.5361810485,9.1421984928,7.2743420419,7.0622575679,4.6163533721,5.7757222606,1.8128746725,6.1253989162,0.9765034425,8.0697299377,0.1609800407,6.8714286899,0.1227995194,1.5686771204,9.6414151462,1.5150466678,3.6231956002,3.2522113179,2.8438568139,2.1113350731,6.0729790898,5.3910699533,0.281396918,3.9535815502,3.1713187974,8.8959949999,6.2965340819,2.2934995848,2.0101520536,7.3172161495,2.7506412892,0.328289005,1.297422694,7.7871005982,5.9768268815,6.2007618509,8.1333896169,7.3426237865,0.3353470587,0.1401476446,0.6348051364,5.6264070026,6.8346286705,8.2874295674,8.7604798353,2.4641537177,9.9481901363,7.5185335707,2.4830759829,9.5255653909,8.2853147574,7.4465766666,6.3797453605,8.449977648,9.5021196362,9.1661645984,1.8496229942,2.5214252551,9.4749431149,7.4803135754,9.1857782425,9.5746395807,3.0873931502,3.9028288447,8.9557864657,1.8220553198,1.2770397728,9.0030445997,8.2324726181,4.20549514,6.6787325847,9.7053652373,3.3031111094,1.6291389521,4.6701311623,4.7830181778,7.7740695141,6.9188801385,0.0847647269,7.3104059813,6.0465683904,4.7166039702,8.7596987491,9.1626891121,4.72457889,8.7989237299,3.4097588481,9.6584176808,0.8257632004,9.1545524122,1.706976681,2.0297640306,0.3222060413,8.8702496048,0.8042637398,1.6107536457,2.8705728683,1.9276636979,1.8293870287,6.6381931351,0.1598592731,3.4692821861,4.6620230819,6.8221832509,0.0797306863,5.271770379,9.6020211722,0.3938668268,4.2415207508,9.4880321156,3.5663137236,6.4006705116,8.6592036532,1.9419052778,6.4766520355,2.567277418,8.8724003313,6.9803212141,0.5659185513,5.1587631018,0.1673995331,0.377174837,9.784399874,4.4597526873,3.7111810967,2.43107029,7.6744934847,5.5436587567,6.1781483516,1.1710951244,8.9064127509,3.9447872131,3.1614319538,6.2640175596,3.0730902427,6.7028201628,4.1139146476,1.9151894888,9.3583895825,2.2177910293,7.8063890827,5.2193417074,9.1168289375,7.9634024273,8.5725085856,3.7787352293,7.3732008738,3.7390939286,0.4619262973,1.9791384623,8.0059528141,3.562508754,3.9490386355,4.6210909821,7.6168948412,9.4117223052,8.9940795559,1.8118510814,4.4756964571,6.3445988786,9.3558575399,9.5378617221,2.5639420538,0.4753952892,6.0783330025,4.1584666283,2.1797239361,0.4499889398,7.5467889477,3.3266924694,0.4163886094,8.1804383663,2.8719682177,8.8539869967,1.7794578383,3.3300268999,2.2402186971,4.3616451044,8.7704319577,4.9370588595,1.3120547729,6.2867796072,1.4903844916,6.8114176835,0.5334125878,3.307583069,3.4162146691,3.838753046,0.7749398868,9.0484665963,5.2610052354,2.0465035108,8.260134419,9.4838513969,7.3133222293,1.1874781619,6.6263020504,9.7101945849,6.2388843508,8.5661508981,6.191658522,0.1667849417,2.9975258466,0.4015979636,9.0240848879,2.0678948821,1.7542802216,9.2874109466,7.0359586761,8.3885412803,5.0866307924,9.0882205567,3.7371065025,6.0871344083,4.6944716293,8.6588100716,4.7368857986,5.4438680178,0.2153190086,4.3287518667,8.7341009825,9.6918797679,0.6026311591,5.0918229623,2.4145042524,0.6562796026,8.0077451933,4.5613256958,6.456324032,1.0674994998,3.4377001994,7.7500452357,4.6083652508,6.1000909633,2.6345350174,8.1388475327,3.6951608909,9.0566710243,9.6697011776,6.6390090506,4.1955091828,9.8782723234,5.170153738,8.8522056444,4.5378721762,7.3028047173,2.9966838309,0.0850060279,0.3994589858,1.2676188396,9.2208322766,7.7429311653,5.8705389453,9.9979829323,3.7077138945,0.5426692753,5.3129471443,6.0403254232,8.9037346165,3.7200537347,8.8731749682,8.9105728618,1.3746650424,5.4522069753,4.9633985572,3.4488402586,5.8631320414,6.359814012,7.8693546774,9.3105396116,0.462407663,0.5028562015,7.3748859437,3.496617449,6.4660780411,0.612201856,9.1539562237,2.5850898796,3.5103771114,6.0719234101,0.6867449102,7.3726611328,6.1478027329,9.6093696938,2.1416593273,4.4545908459,6.0829020641,0.3092425899,5.0907987985,7.6942396513,3.8768380135,2.0571266441,3.0510861054,6.114556829,6.1450441577,9.7674668161,1.4528293302,1.8749052752,6.7039818061,8.4179868549,7.5478103431,5.3069854365,7.1609316976,5.7256553159,5.8889036858,4.7213760135,5.8482523705,9.9814453488,1.8746388657,7.2320152563,7.117245784,1.8556960346,1.3886801433,9.3058773549,2.2195201553,6.1300272029,5.4344094847,9.3686557561,0.010560411,2.9099863814,0.8472597343,5.5355009693,6.4975123154,3.2252346119,8.0363561376,1.1022535758,1.9288622332,1.5512380237,0.8913211129,4.4428992458,5.2221962577,6.0349663883,4.3194847018,0.2740642871,7.4866299401,6.5149042825,1.8699029321,1.2240075972,8.7091258215,0.858111491,7.2084341757,0.2330804826,8.2561737695,2.9991069576,1.4772750926,3.0763669987,8.8008266827,5.014731714,8.0336335185,9.0802629362,3.0561855715,5.205376565,1.0332584265,2.947180199,3.5533884796,7.3355174786,9.405087831,8.3241334883,2.836944377,4.5697274152,0.002810962,4.4917853759,4.1815152974,8.5791653092,9.5890587545,5.7100074389,0.7714147912,7.0760257845,4.8976820917,3.1093755364,8.528902228,0.8067928744,3.3393875603,2.7486888831,0.1834739069,0.1378684375,9.2251335992,4.1045288695,6.7182245175,9.042769731,6.7827539309,6.3593638455,3.2467037439,6.9566761656,1.0027327924,7.8785098926,6.5055959043,3.9875898301,9.4721781183,0.0332891801,2.1123246383,6.8983020354,2.7909638383,5.6092406367,6.5470425109,7.3320892709,1.6870127805,9.0507928259,4.5505000465,2.5084536104,8.3486207016,0.5174473068,2.3654949921,7.8418893297,7.9490615427,5.1846180856,4.135512996,6.0273677716,8.7866113032,7.2287139017,8.4000083292,5.6525641913,6.4858982805,1.5929361968,3.3511886932,6.9653209439,7.1733984421,6.459050565,3.3780623809,2.5373293483,7.0901076077,4.9373544008,0.1462509809,8.3269963856,6.0203876835,8.2110105245,0.6880706432,6.0927194008,7.7066361997,5.1241202629,8.5309002502,3.1917110435,7.2814586363,8.5415711137,4.788106638,0.8656909806,9.9507668987,3.7756799045,6.8723593093,6.466396288,5.7359102392,6.9306769036,0.0285830977,6.3627981697,3.4017293062,1.8991571153,9.1831746954,8.5270528542,3.9207092184,3.9081501053,0.5026421789,8.5771094682,3.2544350368,8.3812019764,6.0142323212,2.2734661517,3.8843900897,7.1689685597,3.1055986579,0.8504488063,0.6574258208,1.9687496964,1.2488291063,3.9164828951,3.5668431572,5.3034012904,3.5568285105,8.6366032297,2.2163238376,8.3285254217,7.965123977,2.5087332935,4.877198902,1.6969170142,5.8756440785,1.021572079,7.7421401115,3.8253072323,3.8279128796,5.0153932883,8.4976275917,9.0518270223,6.6639351263,2.689028671,4.6357620112,2.8451002948,1.3177746837,3.7477840181,7.005943777,6.8638761388,8.1960287644,2.7962804027,2.1653333493,0.3082891321,5.177921888,9.0811816533,5.5036728806,3.0221152096,8.7044512178,8.4093413199,5.4496456194,8.1309032207,4.6121709119,4.9740798096,8.6324632401,3.6019188771,4.8833049228,8.4108941676,0.1754862885,6.9699426321,6.4497952838,3.2386696618,6.8729386106,9.560737845,8.0159594771,4.8208105308,5.7667530165,5.9695888916,9.7108382732,6.2702818681,6.428803564,4.5403990778,1.2387830112,2.7012091153,2.4558584718,9.0875574946,7.4273339007,0.164599272,7.7925671008,5.3403166682,8.5509365425,3.6319944612,2.052635001,8.6386026512,2.9231304303,5.132332989,6.823800304,2.9727885197,4.9862782471,8.9025622536,9.7263278533,2.4262788869,5.704824233,0.4887069808,6.0452728416,4.6907046647,0.3353210841,8.0061770137,8.6807849351,2.0461021014,8.0612291861,5.9533673502,0.6149334507,3.3817240945,9.9171267613,7.5794518972,9.861289612,8.2550288015,6.4068640303,2.1936482145,4.3506846786,2.1863870765,4.1244410188,5.1352235954,8.0445095175,8.7143968698,1.2862475473,2.4010280403,3.2922549709,8.8392988546,0.4996850761,0.7018996053,0.4600142455,3.9470832003,2.6298547653,5.5269017606,3.6417731363,6.171250171,7.9582704674,4.3453288591,4.1139838286,8.2281861291,3.1365121948,0.8844565251,5.2315147384,7.2165561747,5.0469606323,3.8190950616,0.1530248206,0.6978752231,4.3839905597,3.0903446325,5.4319122271,1.5771419299,0.292285243,6.4315836621,0.2736739162,7.6201005117,3.9641580638,3.1821646634,1.7433763319,4.421210906,5.8035024279,7.1267360519,2.2367646033,9.8962822626,3.6362336203,0.4986137524,0.4306951235,2.2750253067,0.9063962195,2.0741806831,7.2938210168,2.6829330297,8.8582969434,6.7682947125,5.6073740264,6.9853516808,5.8498186944,4.769126873,3.6763801752,0.9810877964,5.2166743949,3.2992141182,4.3978313007,8.9398102392,1.2864493672,1.0702800797,7.3049967946,5.2474646876,4.8009952996,2.5238397368,9.3336141552,7.9041981627,5.8579364442,6.9838358392,0.1286074263,4.0678915265,5.0043778308,7.8112759907,7.5522240414,8.0879094754,9.6127591142,6.3559229509,1.9972981839,2.1470950893,7.5876016938,0.3507608105,3.2142408169,0.4481401271,8.5587163619,4.226938223,3.3966982551,0.6860379712,0.594250483,2.0161200338,0.0087707303,1.1269167135,1.1443942948,0.950607094,2.6806247607,3.1751575088,7.5500228931,0.5481684348,3.2760024793,0.6785353692,9.754259421,9.442907176,8.3906497783,7.1256533475,4.1378314304,9.0894515486,5.7786925719,3.9451290527,1.3508908171,9.1023366014,4.092890555,6.1715901364,8.5397282243,5.2017102973,4.2505381838,7.6669364423,8.032946114,3.0906258477,3.6614765995,5.1746382471,7.2805444081,8.87948032,3.5239889915,8.7685777899,0.5480092834,6.6448430647,1.0905100359,5.9083357221,3.8091140962,1.4898836473,1.9381182618,5.4684353573,4.8566022119,1.9279759983,0.9892736119,0.4142652988,9.6462709433,8.7819549884,7.620176489,7.0339414384,6.1000816594,9.5847381349,7.6452151709,8.7108218623,3.319179886,5.510850565,3.857299767,3.1595066795,9.0541076707,6.9994174084,9.8434844147,8.8396938727,4.4175667013,9.7113732575,3.5052315216,1.8646901124,5.5844724341,8.0796525604,4.3168413476,0.6563068926,4.3559580459,7.9521153611,1.6126889456,0.6541568553,3.6283174949,3.6298038601,5.1297246735,8.9238565019,4.3017713632,0.4323642538,6.7943119584,8.6531036743,1.4601672534,6.0968769295,4.5982605522,5.1004847116,9.6697254316,1.8093775935,8.6581160314,8.3556680311,1.1881286884,8.7667299388,4.8027647054,7.9023741116,4.1652621701,6.76527665,1.3222630834,1.2765076151,6.3167106942,2.398883726,5.2035188721,1.1172460136]}