1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Empirical Cumulative Distribution Function</title> 5<link rel="stylesheet" href="../../../math.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Math Toolkit 2.12.0"> 8<link rel="up" href="../dists.html" title="Distributions"> 9<link rel="prev" href="chi_squared_dist.html" title="Chi Squared Distribution"> 10<link rel="next" href="exp_dist.html" title="Exponential Distribution"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="chi_squared_dist.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../dists.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="exp_dist.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="math_toolkit.dist_ref.dists.empirical_cdf"></a><a class="link" href="empirical_cdf.html" title="Empirical Cumulative Distribution Function">Empirical 28 Cumulative Distribution Function</a> 29</h4></div></div></div> 30<h6> 31<a name="math_toolkit.dist_ref.dists.empirical_cdf.h0"></a> 32 <span class="phrase"><a name="math_toolkit.dist_ref.dists.empirical_cdf.synopsis"></a></span><a class="link" href="empirical_cdf.html#math_toolkit.dist_ref.dists.empirical_cdf.synopsis">Synopsis</a> 33 </h6> 34<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">distributions</span><span class="special">/</span><span class="identifier">empirical_cumulative_distribution_function</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 35 36<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span> 37 38<span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">RandomAccessContainer</span><span class="special">></span> 39<span class="keyword">class</span> <span class="identifier">empirical_cumulative_distribution_function</span> 40<span class="special">{</span> 41<span class="keyword">public</span><span class="special">:</span> 42 <span class="keyword">using</span> <span class="identifier">Real</span> <span class="special">=</span> <span class="keyword">typename</span> <span class="identifier">RandomAccessContainer</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">;</span> 43 <span class="identifier">empirical_cumulative_distribution_function</span><span class="special">(</span><span class="identifier">RandomAccessContainer</span> <span class="special">&&</span> <span class="identifier">v</span><span class="special">,</span> <span class="keyword">bool</span> <span class="identifier">sorted</span> <span class="special">=</span> <span class="keyword">false</span><span class="special">);</span> 44 45 <span class="keyword">auto</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">Real</span> <span class="identifier">t</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 46 47 <span class="identifier">RandomAccessContainer</span><span class="special">&&</span> <span class="identifier">return_data</span><span class="special">();</span> 48<span class="special">};</span> 49 50<span class="special">}}</span> 51</pre> 52<h6> 53<a name="math_toolkit.dist_ref.dists.empirical_cdf.h1"></a> 54 <span class="phrase"><a name="math_toolkit.dist_ref.dists.empirical_cdf.empirical_cumulative_distributio"></a></span><a class="link" href="empirical_cdf.html#math_toolkit.dist_ref.dists.empirical_cdf.empirical_cumulative_distributio">Empirical 55 Cumulative Distribution Function</a> 56 </h6> 57<p> 58 The empirical cumulative distribution function is a step function constructed 59 from observed data which converges to the true cumulative distribution 60 function in the limit of infinite data. This function is a basic building 61 block of hypothesis testing workflows that attempt to answer the question 62 "does my data come from a given distribution?" These tests require 63 computing quadratures over some function of the empirical CDF and the supposed 64 CDF to create a distance measurement, and hence it is occasionally useful 65 to construct a continuous callable from the data. 66 </p> 67<p> 68 An example usage is demonstrated below: 69 </p> 70<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 71<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">random</span><span class="special">></span> 72<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">distributions</span><span class="special">/</span><span class="identifier">empirical_cumulative_distribution_function</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 73<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">empirical_cumulative_distribution_function</span><span class="special">;</span> 74<span class="identifier">std</span><span class="special">::</span><span class="identifier">random_device</span> <span class="identifier">rd</span><span class="special">;</span> 75<span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span> <span class="identifier">gen</span><span class="special">{</span><span class="identifier">rd</span><span class="special">()};</span> 76<span class="identifier">std</span><span class="special">::</span><span class="identifier">normal_distribution</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span> <span class="identifier">dis</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">1</span><span class="special">);</span> 77<span class="identifier">size_t</span> <span class="identifier">n</span> <span class="special">=</span> <span class="number">128</span><span class="special">;</span> 78<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span> <span class="identifier">v</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> 79<span class="keyword">for</span> <span class="special">(</span><span class="identifier">size_t</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">n</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{</span> 80 <span class="identifier">v</span><span class="special">[</span><span class="identifier">i</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">dis</span><span class="special">(</span><span class="identifier">gen</span><span class="special">);</span> 81<span class="special">}</span> 82 83<span class="keyword">auto</span> <span class="identifier">ecdf</span> <span class="special">=</span> <span class="identifier">empirical_cumulative_distribution_function</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">v</span><span class="special">));</span> 84<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"ecdf(0.0) = "</span> <span class="special"><<</span> <span class="identifier">ecdf</span><span class="special">(</span><span class="number">0.0</span><span class="special">)</span> <span class="special"><<</span> <span class="string">"\n"</span><span class="special">;</span> 85<span class="comment">// should print approximately 0.5 . . .</span> 86</pre> 87<p> 88 The empirical distribution function requires sorted data. By default, the 89 constructor sorts it for you at O(Nlog(N)) cost. 90 </p> 91<p> 92 If your data is already sorted, you can specify this and the constructor 93 simply moves your data into the class: 94 </p> 95<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 96<span class="keyword">auto</span> <span class="identifier">ecdf</span> <span class="special">=</span> <span class="identifier">empirical_cumulative_distribution_function</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">v</span><span class="special">),</span> <span class="comment">/* already sorted = */</span> <span class="keyword">true</span><span class="special">);</span> 97</pre> 98<p> 99 If you want your data back after being done with the object, use 100 </p> 101<pre class="programlisting"><span class="identifier">v</span> <span class="special">=</span> <span class="identifier">ecdf</span><span class="special">.</span><span class="identifier">return_data</span><span class="special">();</span> 102</pre> 103<p> 104 This operation invalidates <code class="computeroutput"><span class="identifier">ecdf</span></code>; 105 it can no longer be used. 106 </p> 107<p> 108 The call operator complexity is O(log(N)), as it requires a call to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">upper_bound</span></code>. 109 </p> 110<p> 111 Works with both integer and floating point types. If the input data consists 112 of integers, the output of the call operator is a double. Requires C++17. 113 </p> 114<p> 115 <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../../graphs/empiricial_cumulative_distribution_gauss.svg"></object></span> 116 </p> 117<p> 118 <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../../graphs/empiricial_cumulative_distribution_uniform.svg"></object></span> 119 </p> 120<h6> 121<a name="math_toolkit.dist_ref.dists.empirical_cdf.h2"></a> 122 <span class="phrase"><a name="math_toolkit.dist_ref.dists.empirical_cdf.performance"></a></span><a class="link" href="empirical_cdf.html#math_toolkit.dist_ref.dists.empirical_cdf.performance">Performance</a> 123 </h6> 124<pre class="programlisting"><span class="special">------------------------------------------------------</span> 125<span class="identifier">Benchmark</span> <span class="identifier">Time</span> 126<span class="special">------------------------------------------------------</span> 127<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8</span> <span class="number">4.52</span> <span class="identifier">ns</span> 128<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16</span> <span class="number">5.20</span> <span class="identifier">ns</span> 129<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32</span> <span class="number">5.22</span> <span class="identifier">ns</span> 130<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">64</span> <span class="number">7.37</span> <span class="identifier">ns</span> 131<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">128</span> <span class="number">7.16</span> <span class="identifier">ns</span> 132<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">256</span> <span class="number">8.97</span> <span class="identifier">ns</span> 133<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">512</span> <span class="number">8.44</span> <span class="identifier">ns</span> 134<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">1024</span> <span class="number">9.07</span> <span class="identifier">ns</span> 135<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2048</span> <span class="number">11.4</span> <span class="identifier">ns</span> 136<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4096</span> <span class="number">12.6</span> <span class="identifier">ns</span> 137<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8192</span> <span class="number">11.4</span> <span class="identifier">ns</span> 138<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16384</span> <span class="number">16.0</span> <span class="identifier">ns</span> 139<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32768</span> <span class="number">17.0</span> <span class="identifier">ns</span> 140<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">65536</span> <span class="number">19.5</span> <span class="identifier">ns</span> 141<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">131072</span> <span class="number">15.8</span> <span class="identifier">ns</span> 142<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">262144</span> <span class="number">17.9</span> <span class="identifier">ns</span> 143<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">524288</span> <span class="number">26.7</span> <span class="identifier">ns</span> 144<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">1048576</span> <span class="number">29.5</span> <span class="identifier">ns</span> 145<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2097152</span> <span class="number">31.8</span> <span class="identifier">ns</span> 146<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4194304</span> <span class="number">32.8</span> <span class="identifier">ns</span> 147<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8388608</span> <span class="number">35.4</span> <span class="identifier">ns</span> 148<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16777216</span> <span class="number">30.4</span> <span class="identifier">ns</span> 149<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_BigO</span> <span class="number">1.27</span> <span class="identifier">lgN</span> 150<span class="identifier">ECDFConstructorSorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_RMS</span> <span class="number">20</span> <span class="special">%</span> 151<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8</span> <span class="number">155</span> <span class="identifier">ns</span> 152<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">64</span> <span class="number">2095</span> <span class="identifier">ns</span> 153<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">512</span> <span class="number">22212</span> <span class="identifier">ns</span> 154<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4096</span> <span class="number">220821</span> <span class="identifier">ns</span> 155<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32768</span> <span class="number">1996380</span> <span class="identifier">ns</span> 156<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">262144</span> <span class="number">18916039</span> <span class="identifier">ns</span> 157<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2097152</span> <span class="number">194250013</span> <span class="identifier">ns</span> 158<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16777216</span> <span class="number">2281469424</span> <span class="identifier">ns</span> 159<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_BigO</span> <span class="number">5.65</span> <span class="identifier">NlgN</span> 160<span class="identifier">ECDFConstructorUnsorted</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_RMS</span> <span class="number">6</span> <span class="special">%</span> 161<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8</span> <span class="number">82.4</span> <span class="identifier">ns</span> 162<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">64</span> <span class="number">731</span> <span class="identifier">ns</span> 163<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">512</span> <span class="number">5876</span> <span class="identifier">ns</span> 164<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4096</span> <span class="number">46864</span> <span class="identifier">ns</span> 165<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32768</span> <span class="number">385265</span> <span class="identifier">ns</span> 166<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">262144</span> <span class="number">4663866</span> <span class="identifier">ns</span> 167<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2097152</span> <span class="number">54686332</span> <span class="identifier">ns</span> 168<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16777216</span> <span class="number">875309099</span> <span class="identifier">ns</span> 169<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_BigO</span> <span class="number">2.16</span> <span class="identifier">NlgN</span> 170<span class="identifier">Shuffle</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_RMS</span> <span class="number">12</span> <span class="special">%</span> 171<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8</span> <span class="number">48.6</span> <span class="identifier">ns</span> 172<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">64</span> <span class="number">61.3</span> <span class="identifier">ns</span> 173<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">512</span> <span class="number">85.1</span> <span class="identifier">ns</span> 174<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4096</span> <span class="number">105</span> <span class="identifier">ns</span> 175<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32768</span> <span class="number">131</span> <span class="identifier">ns</span> 176<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">262144</span> <span class="number">196</span> <span class="identifier">ns</span> 177<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2097152</span> <span class="number">391</span> <span class="identifier">ns</span> 178<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16777216</span> <span class="number">715</span> <span class="identifier">ns</span> 179<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_BigO</span> <span class="number">18.19</span> <span class="identifier">lgN</span> 180<span class="identifier">ECDFEvaluation</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_RMS</span> <span class="number">60</span> <span class="special">%</span> 181</pre> 182<p> 183 The call to the unsorted constructor is in fact a little faster than indicated, 184 as the data must be shuffled after being sorted in the benchmark. This 185 is itself a fairly expensive operation. 186 </p> 187</div> 188<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 189<td align="left"></td> 190<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 191 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 192 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 193 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 194 Daryle Walker and Xiaogang Zhang<p> 195 Distributed under the Boost Software License, Version 1.0. (See accompanying 196 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 197 </p> 198</div></td> 199</tr></table> 200<hr> 201<div class="spirit-nav"> 202<a accesskey="p" href="chi_squared_dist.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../dists.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="exp_dist.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 203</div> 204</body> 205</html> 206
