<s> from bintrees import FastRBTree as RBTree <EOL> import pytest <EOL> from numpy import random <EOL> from tdigest . tdigest import TDigest , Centroid <EOL> @ pytest . fixture ( ) <EOL> def empty_tdigest ( ) : <EOL> return TDigest ( ) <EOL> @ pytest . fixture ( ) <EOL> def example_positive_centroids ( ) : <EOL> return RBTree ( [ <EOL> ( <NUM_LIT:0.5> , Centroid ( <NUM_LIT:0.5> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ] ) <EOL> @ pytest . fixture ( ) <EOL> def example_centroids ( ) : <EOL> return RBTree ( [ <EOL> ( - <NUM_LIT> , Centroid ( - <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ( - <NUM_LIT:0.5> , Centroid ( - <NUM_LIT:0.5> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT:0.1> , Centroid ( <NUM_LIT:0.1> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ] ) <EOL> @ pytest . fixture ( ) <EOL> def example_random_data ( ) : <EOL> return random . randn ( <NUM_LIT:100> ) <EOL> class TestTDigest ( ) : <EOL> def test_add_centroid ( self , empty_tdigest , example_positive_centroids ) : <EOL> empty_tdigest . C = example_positive_centroids <EOL> new_centroid = Centroid ( <NUM_LIT> , <NUM_LIT:1> ) <EOL> empty_tdigest . _add_centroid ( new_centroid ) <EOL> assert ( empty_tdigest . C - RBTree ( [ <EOL> ( <NUM_LIT:0.5> , Centroid ( <NUM_LIT:0.5> , <NUM_LIT:1> ) ) , <EOL> ( new_centroid . mean , new_centroid ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ] ) ) . is_empty ( ) <EOL> last_centroid = Centroid ( <NUM_LIT> , <NUM_LIT:1> ) <EOL> empty_tdigest . _add_centroid ( last_centroid ) <EOL> assert ( empty_tdigest . C - RBTree ( [ <EOL> ( <NUM_LIT:0.5> , Centroid ( <NUM_LIT:0.5> , <NUM_LIT:1> ) ) , <EOL> ( new_centroid . mean , new_centroid ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ( last_centroid . mean , last_centroid ) , <EOL> ] ) ) . is_empty ( ) <EOL> def test_add_centroid_if_key_already_present ( self , empty_tdigest , example_positive_centroids ) : <EOL> empty_tdigest . C = example_positive_centroids <EOL> new_centroid = Centroid ( <NUM_LIT> , <NUM_LIT:5> ) <EOL> empty_tdigest . _add_centroid ( new_centroid ) <EOL> assert ( empty_tdigest . C - RBTree ( [ <EOL> ( <NUM_LIT:0.5> , Centroid ( <NUM_LIT:0.5> , <NUM_LIT:1> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> + <NUM_LIT:5> ) ) , <EOL> ( <NUM_LIT> , Centroid ( <NUM_LIT> , <NUM_LIT:1> ) ) , <EOL> ] ) ) . is_empty ( ) <EOL> def test_compute_centroid_quantile ( self , empty_tdigest , example_centroids ) : <EOL> empty_tdigest . C = example_centroids <EOL> empty_tdigest . n = <NUM_LIT:4> <EOL> assert empty_tdigest . _compute_centroid_quantile ( example_centroids [ - <NUM_LIT> ] ) == ( <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:0> ) / <NUM_LIT:4> <EOL> assert empty_tdigest . _compute_centroid_quantile ( example_centroids [ - <NUM_LIT:0.5> ] ) == ( <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:1> ) / <NUM_LIT:4> <EOL> assert empty_tdigest . _compute_centroid_quantile ( example_centroids [ <NUM_LIT:0.1> ] ) == ( <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:2> ) / <NUM_LIT:4> <EOL> assert empty_tdigest . _compute_centroid_quantile ( example_centroids [ <NUM_LIT> ] ) == ( <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:3> ) / <NUM_LIT:4> <EOL> def test_find_closest_centroids_works_with_positive_values ( self , empty_tdigest , example_positive_centroids ) : <EOL> empty_tdigest . C = example_positive_centroids <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT:0.0> ) == [ example_positive_centroids [ <NUM_LIT:0.5> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT> ) == [ example_positive_centroids [ <NUM_LIT> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT> ) == [ example_positive_centroids [ <NUM_LIT> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT> ) == [ example_positive_centroids [ <NUM_LIT> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT> ) == [ example_positive_centroids [ <NUM_LIT> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT> ) == [ example_positive_centroids [ <NUM_LIT> ] , <EOL> example_positive_centroids [ <NUM_LIT> ] ] <EOL> def test_get_closest_centroids_works_with_negative_values ( self , empty_tdigest , example_centroids ) : <EOL> empty_tdigest . C = example_centroids <EOL> assert empty_tdigest . _find_closest_centroids ( <NUM_LIT:0.0> ) == [ example_centroids [ <NUM_LIT:0.1> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( - <NUM_LIT> ) == [ example_centroids [ - <NUM_LIT> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( - <NUM_LIT> ) == [ example_centroids [ - <NUM_LIT:0.5> ] ] <EOL> assert empty_tdigest . _find_closest_centroids ( - <NUM_LIT> ) == [ example_centroids [ - <NUM_LIT:0.5> ] ] <EOL> def test_compress ( self , empty_tdigest , example_random_data ) : <EOL> empty_tdigest . batch_update ( example_random_data ) <EOL> precompress_n , precompress_len = empty_tdigest . n , len ( empty_tdigest ) <EOL> empty_tdigest . compress ( ) <EOL> postcompress_n , postcompress_len = empty_tdigest . n , len ( empty_tdigest ) <EOL> assert postcompress_n == precompress_n <EOL> assert postcompress_len <= precompress_len <EOL> def test_data_comes_in_sorted_does_not_blow_up ( self , empty_tdigest ) : <EOL> t = TDigest ( ) <EOL> for x in range ( <NUM_LIT> ) : <EOL> t . update ( x , <NUM_LIT:1> ) <EOL> assert len ( t ) < <NUM_LIT> <EOL> t = TDigest ( ) <EOL> t . batch_update ( range ( <NUM_LIT> ) ) <EOL> assert len ( t ) < <NUM_LIT:1000> <EOL> def test_extreme_percentiles_return_min_and_max ( self , empty_tdigest ) : <EOL> t = TDigest ( ) <EOL> data = random . randn ( <NUM_LIT> ) <EOL> t . batch_update ( data ) <EOL> assert t . percentile ( <NUM_LIT:0> ) == data . min ( ) <EOL> assert t . percentile ( <NUM_LIT> ) == data . max ( ) <EOL> def test_adding_centroid_with_exisiting_key_does_not_break_synchronicity ( self , empty_tdigest , example_centroids ) : <EOL> td = empty_tdigest <EOL> td . C = example_centroids <EOL> assert - <NUM_LIT> in td . C <EOL> td . _add_centroid ( Centroid ( - <NUM_LIT> , <NUM_LIT:10> ) ) <EOL> assert all ( [ k == centroid . mean for k , centroid in td . C . items ( ) ] ) <EOL> class TestStatisticalTests ( ) : <EOL> def test_uniform ( self ) : <EOL> t = TDigest ( ) <EOL> x = random . random ( size = <NUM_LIT> ) <EOL> t . batch_update ( x ) <EOL> assert abs ( t . percentile ( <NUM_LIT:50> ) - <NUM_LIT:0.5> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT:10> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT:1> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT:0.1> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> assert abs ( t . percentile ( <NUM_LIT> ) - <NUM_LIT> ) < <NUM_LIT> <EOL> def test_ints ( self ) : <EOL> t = TDigest ( ) <EOL> t . batch_update ( [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> assert t . percentile ( <NUM_LIT:50> ) == <NUM_LIT:2> <EOL> t = TDigest ( ) <EOL> x = [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:3> ] <EOL> t . batch_update ( x ) <EOL> assert t . percentile ( <NUM_LIT:50> ) == <NUM_LIT:2> <EOL> assert sum ( [ c . count for c in t . C . values ( ) ] ) == len ( x ) <EOL> class TestCentroid ( ) : <EOL> def test_update ( self ) : <EOL> c = Centroid ( <NUM_LIT:0> , <NUM_LIT:0> ) <EOL> value , weight = <NUM_LIT:1> , <NUM_LIT:1> <EOL> c . update ( value , weight ) <EOL> assert c . count == <NUM_LIT:1> <EOL> assert c . mean == <NUM_LIT:1> <EOL> value , weight = <NUM_LIT:2> , <NUM_LIT:1> <EOL> c . update ( value , weight ) <EOL> assert c . count == <NUM_LIT:2> <EOL> assert c . mean == ( <NUM_LIT:2> + <NUM_LIT:1.> ) / <NUM_LIT> <EOL> value , weight = <NUM_LIT:1> , <NUM_LIT:2> <EOL> c . update ( value , weight ) <EOL> assert c . count == <NUM_LIT:4> <EOL> assert c . mean == <NUM_LIT:1> * <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:2> * <NUM_LIT:1> / <NUM_LIT> + <NUM_LIT:1> * <NUM_LIT:2> / <NUM_LIT> </s>
