1 /******************************************************************************* 2 3 Sliding Average Module 4 5 This module contains two classes to calculate the average of a fixed amount 6 of values. Once the fixed amount of values has been added, each time a new 7 value is added, the oldest is forgotten 8 9 SlidingAverage is very simple. You can add values to the list and you can 10 query the average at any time. 11 12 SlidingAverageTime offers a few more functions. It is for the use case when 13 you don't want to add one value at once, but instead add on top of the last 14 value until push() is called, which should be done periodically. The class 15 is aware of that period and adjusts the added values accordingly. You tell 16 it how much time a single completed value corresponds to and what time 17 output resultion you desire. 18 19 Copyright: 20 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 21 All rights reserved. 22 23 License: 24 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 25 Alternatively, this file may be distributed under the terms of the Tango 26 3-Clause BSD License (see LICENSE_BSD.txt for details). 27 28 *******************************************************************************/ 29 30 module ocean.math.SlidingAverage; 31 32 33 import ocean.core.Verify; 34 35 /******************************************************************************* 36 37 Sliding Average Class 38 39 SlidingAverage is very simple. You can add values to the list and you can 40 query the average at any time. 41 42 *******************************************************************************/ 43 44 public class SlidingAverage ( T ) 45 { 46 /*************************************************************************** 47 48 Sliding window, containing the values of the recent additions 49 50 ***************************************************************************/ 51 52 protected T[] window; 53 54 55 /*************************************************************************** 56 57 Current average value of the whole window 58 59 ***************************************************************************/ 60 61 protected real _average; 62 63 64 /*************************************************************************** 65 66 Index of the value that was updated most recently 67 68 ***************************************************************************/ 69 70 protected size_t index; 71 72 73 /*************************************************************************** 74 75 The number of values the sliding window currently contains 76 77 ***************************************************************************/ 78 79 protected size_t current_size; 80 81 82 /*************************************************************************** 83 84 Constructor 85 86 Params: 87 window_size = size of the sliding window 88 89 ***************************************************************************/ 90 91 public this ( size_t window_size ) 92 { 93 verify(window_size > 1, "SlidingAverage, window_size parameter must be > 1"); 94 95 this.window = new T[window_size]; 96 this.index = this.index.max; 97 } 98 99 100 /*************************************************************************** 101 102 Pushes another value to the sliding window, overwriting the oldest one 103 if the sliding window has reached its maximum size. 104 Calculates the new average, stores it, and returns it. 105 106 Params: 107 value = The value to into the sliding window 108 109 Returns: 110 new average 111 112 ***************************************************************************/ 113 114 public real push ( T value ) 115 { 116 this.index++; 117 // overwrite oldest value if max slider size has been reached 118 if ( this.index >= this.window.length ) 119 { 120 this.index = 0; 121 } 122 123 this.window[this.index] = value; 124 125 // only the filled indexes in the slider should be calculated 126 if ( this.current_size < this.window.length ) 127 { 128 this.current_size++; 129 } 130 131 this._average = 0.0; 132 133 foreach ( val; this.window[0 .. this.current_size] ) 134 { 135 this._average += val; 136 } 137 138 this._average /= this.current_size; 139 140 return this._average; 141 } 142 143 144 /*************************************************************************** 145 146 Returns the last value pushed 147 148 Returns: 149 the last value 150 151 ***************************************************************************/ 152 153 public T last ( ) 154 { 155 if ( this.index > this.window.length ) 156 { 157 return T.init; 158 } 159 160 return this.window[this.index]; 161 } 162 163 164 /*************************************************************************** 165 166 Returns the current average 167 168 Returns: 169 average 170 171 ***************************************************************************/ 172 173 public real average ( ) 174 { 175 return this._average; 176 } 177 178 179 /*************************************************************************** 180 181 Resets the average counter to the zero state: 182 183 - index is set to max so that it will be set to 0 once .push() is called 184 - average is set to 0.0 185 - all elements of window reset to T.init 186 - used window size set to 0 187 188 ***************************************************************************/ 189 190 public void clear ( ) 191 { 192 this.index = this.index.max; 193 this._average = 0.0; 194 this.current_size = 0; 195 this.window[] = T.init; 196 } 197 } 198 199 /******************************************************************************* 200 201 SlidingAverage unittests 202 203 *******************************************************************************/ 204 205 version (unittest) 206 { 207 import ocean.util.Convert: to; 208 import ocean.core.Test; 209 import ocean.meta.types.Qualifiers; 210 211 /******************************************************************************* 212 213 Runs a series of tests a SlidingAverage of the given type and size 214 Template function so no code will be generated unless in debug mode. 215 216 Params: 217 size = The number of values to fill the SlidingAverage with. 218 test_iteration = The current test iteration, for error messages. 219 220 *******************************************************************************/ 221 222 void runTests ( T ) ( uint size, int test_iteration ) 223 { 224 test!(">")(size, 2, "can only test SlidingAverages with at least 2 values"); 225 226 auto avg = new SlidingAverage!(T)(size); 227 228 istring err_prefix = "SlidingAverage assertion failed for iteration " ~ 229 to!(istring)(test_iteration) ~ ": "; 230 231 ulong sum; 232 233 for ( int i = 1; i <= size; i++ ) 234 { 235 avg.push(i); 236 test!("==")( avg.last, i, "last() didn't return last added value" ); // #220 237 sum += i; 238 } 239 240 // Test a full SlidingAverage 241 test!("==")(avg.average, cast(double)sum / size, err_prefix ~ "test 1"); 242 test!("==")( avg.last, size, "last() didn't return last added value" ); // #220 243 244 // Add size + 1 to the average, but only size to the sum 245 // Because at this point the first value of the average will be pushed out 246 avg.push(size + 1); 247 test!("==")( avg.last, size+1, "last() didn't return last added value" ); // #220 248 sum += size; 249 250 // Test a SlidingAverage where the oldest value has been replaced 251 test!("==")(avg.average, cast(double)sum / size, err_prefix ~ "test 2"); 252 253 avg.clear; 254 255 // Test if average is 0 upon clearing after filling it with values 256 test!("==")(avg.average, 0, err_prefix ~ "test 3"); 257 258 avg.push(2); 259 test!("==")( avg.last, 2 , "last() didn't return last added value" ); // #220 260 avg.push(4); 261 test!("==")( avg.last, 4 , "last() didn't return last added value" ); // #220 262 263 // Test a partially filled SlidingAverage 264 test!("==")(avg.average, 3, err_prefix ~ "test 4"); 265 } 266 } 267 268 unittest 269 { 270 runTests!(ulong)(100, 1); 271 runTests!(int)(50, 2); 272 runTests!(double)(1000, 3); 273 } 274 275 276 /******************************************************************************* 277 278 Sliding Average Time Class 279 280 SlidingAverageTime offers a few more functions. It is for the use case when 281 you don't want to add one value at once, but instead add on top of the last 282 value until push() is called, which should be done periodically. The class 283 is aware of that period and adjusts the added values accordingly. You tell 284 it how much time a single completed value corresponds to and what time 285 output resultion you desire. 286 287 Usage Example 288 ------------ 289 290 import ocean.math.SlidingAverage; 291 import ocean.io.select.EpollSelectDispatcher; 292 import ocean.io.select.client.TimerEvent; 293 294 import ocean.io.Stdout; 295 296 void main () 297 { 298 // One stat output for the amount of records 299 auto avg_stats = new SlidingAverageTime!(size_t)(100, 50, 1000); 300 // one stat output for the amount of bytes 301 auto avg_byte_stats = new SlidingAverageTime!(size_t)(100, 50, 1000); 302 303 // Called by the udpate_timer 304 bool update ( ) 305 { 306 // Push accumulated data to the list of values used for caluclation 307 // of average 308 avg_stats.push(); 309 return true; 310 } 311 312 // called by the display timer 313 bool display_stats ( ) 314 { 315 Stdout.formatln("Processed {} (avg {}) records,\n" 316 " {} bytes, (avg {} bytes)", 317 avg_stats.last(), avg_stats.average(), 318 avg_byte_stats.last, avg_byte_stats.average()); 319 } 320 321 auto epoll = new EpollSelectDispatcher; 322 auto update_timer = new TimerEvent(&update); 323 auto display_timer = new TimerEvent(&display_stats); 324 325 // Fire timer every 50ms 326 update_timer.set(0, 0, 0, 50); 327 328 // Fire timer every 1000ms 329 display_timer.set(0, 0, 1, 0); 330 331 epoll.register(update_timer); 332 epoll.register(display_stats); 333 334 // Assume that some epoll triggered handler calls this method every time 335 // the program has to process incoming data 336 void process_record ( ubyte[] data ) 337 { 338 do_important_stuff(); 339 avg_stats++; // one new record 340 avg_byte_stats += data.length; // that much new data was handled 341 } 342 343 epoll.eventLoop(); 344 } 345 ----- 346 347 *******************************************************************************/ 348 349 public class SlidingAverageTime ( T ) : SlidingAverage!(T) 350 { 351 /*************************************************************************** 352 353 Contains the latest value to which new values are currently being added 354 355 ***************************************************************************/ 356 357 public T current; 358 359 360 /*************************************************************************** 361 362 Resolution that the output needs to be multiplied with 363 364 ***************************************************************************/ 365 366 protected real resolution; 367 368 369 /*************************************************************************** 370 371 Constructor 372 373 Params: 374 window_size = size of the sliding window 375 resolution = how much milli seconds one completed value 376 corresponds to. Push needs to be called every 377 <resolution> ms 378 output_resolution = desired resolution for output in milliseconds 379 380 ***************************************************************************/ 381 382 public this ( size_t window_size, size_t resolution, 383 size_t output_resolution = 1000 ) 384 { 385 super(window_size); 386 387 this.resolution = cast(real) output_resolution / cast(real) resolution; 388 } 389 390 391 /*************************************************************************** 392 393 Adds current value to the time window history. 394 Calculates the new average and returns it 395 396 This pushes the data accumulated using opUnary!"++", opOpAssign!"+" 397 and opAssign to the list of values used to calculate the average. 398 399 Note: This should be called by a timer periodically according to the 400 resolution given in the constructor 401 402 The parents class' push() method is not required or planned to be 403 called when this class is used, none the less there might be rare 404 usecases where it could be desired. 405 406 Returns: 407 new average 408 409 ***************************************************************************/ 410 411 public real push ( ) 412 { 413 super._average = super.push(this.current) * this.resolution; 414 415 this.current = 0; 416 417 return super._average; 418 } 419 420 421 /*************************************************************************** 422 423 Returns the last finished value 424 425 Returns: 426 the latest complete value 427 428 ***************************************************************************/ 429 430 public override T last ( ) 431 { 432 return super.last() * cast(T) this.resolution; 433 } 434 435 436 /*************************************************************************** 437 438 Sets the current value to val 439 440 Params: 441 val = value to set current value to 442 443 Returns: 444 new current value 445 446 ***************************************************************************/ 447 448 public T opAssign ( T val ) 449 { 450 return this.current = val; 451 } 452 453 454 /*************************************************************************** 455 456 Increments the current value by one 457 458 Params: 459 op = operation to perform 460 461 Returns: 462 new current value 463 464 ***************************************************************************/ 465 466 public T opUnary ( string op ) ( ) if (op == "++") 467 { 468 return this.current++; 469 } 470 471 472 /*************************************************************************** 473 474 Adds the given value to the current value 475 476 Params: 477 op = operation to perform 478 val = value to add to the current value 479 480 Returns: 481 new current value 482 483 ***************************************************************************/ 484 485 public T opOpAssign ( string op ) ( T val ) if (op == "+") 486 { 487 return this.current += val; 488 } 489 } 490 491 unittest 492 { 493 auto avg_stats = new SlidingAverageTime!(size_t)(100, 50, 1000); 494 495 test!("==")(avg_stats.current, 0, "Failed SlidingAverageTime initial value"); 496 497 avg_stats++; 498 test!("==")(avg_stats.current, 1, "Failed SlidingAverageTime increment value"); 499 500 avg_stats += 3; 501 test!("==")(avg_stats.current, 4, "Failed SlidingAverageTime add value"); 502 503 }