4a88884b39
* Add ranges * Initial Hugo setup * Work in progress * Added selection for local or remote site * Updated to 'light' theme * Changed to using Hextra Hugo theme * Changed to using Hextra Hugo theme * Changed to Hextra Hugo theme * Change to Hextra Hugo theme * Updated Hugo setup. * Updated Hugo setup. # Conflicts: # docs/releases/_index.md * Work in progress * Added new fonts Added new documentation * Latest documentation updates * Latest documentation updates # Conflicts: # docs/containers/array.md # docs/containers/array_view.md # docs/containers/array_wrapper.md # docs/containers/bip_buffer_spsc_atomic.md # docs/containers/bitset.md # docs/containers/indirect_vector.md # docs/containers/vector.md # docs/getting-started/compilers.md * Added bloom_filter markdown doc * Added more documentation Updated CSS for light and dark modes * Fixed some menus Added mode documentation files * Updated CSS rules Added badges to home page Added uniqur_ptr + pool tutorial * Fixed formatting on the home page markdown Modified light amd dark code formatting * Updated unique_ptr-with-pool * Added container and shared message tutorials * Updates to documentation * Added const_multimap * Updated source-formatting.md * Added initial raw text files form Web site editor * Innore coverage build directory * Exported raw text documentation files from the web site editor * Hugo updates * Added Hugo intalation and markdown descriptions * More addition to the documentation * Added closure.md and updates to delegate.md * Added format.md * Added documentation for etl::delegate_observable, etl::function, Base64 codec * Added io_port documentation * Added basic_format_spec * Added documentation for string_stream and string utilities. * Added more documentation Updated the documentation CSS * Added documentation for clocks, day, duration * Added more documentation for chrono classes Updated callouts * More chrono documentation * Completed chrono documentation * Maths functions documentation * Completed maths documentation * Completed maths documentation * Completed maths documentation * Completed maths documentation * Added multiple documentation files * Added iterator.md * Added debug_count.md and versions.md * Added debug_count.md and versions.md * Added more documentation * More documentation * Added some design pattern documentation Modified some of the layout files Modified the About documentation * Converted more documentation pages Modified the site CSS * Added more documentation Moced some documentation files to new directories * Added more documentation Tweaks to CSS * Added callback_timer_deferred_locked documentation * Added callback_timer_locked documentation * More documentation updates * More documentation updates * More documentation updates * New documentation files. Harmonised file name format * New documentation files. * Multiple document updates * Multiple document updates * Final conversion of web pages * Updates before PR * Updates before PR * Updates before PR # Conflicts: # docs/blog/_index.md * Final pre PR updates * Updates to message framework documentation * Renamed directory * Fix spelling * Added author and date to blog files Moved documentation files merged from development * Fixed 'Description' typo * Fix typos # Conflicts: # docs/IO/io_port.md # docs/containers/sets/const-multiset.md # docs/containers/sets/const-set.md # docs/maths/correlation.md # docs/maths/gamma.md * Renamed two files to lower case * Minor renaming * Added author and date * Updated callout on bresenham_line.md Added support for showing the ETL version on the documentation first page, by copying the version.txt file as a hugo asset. Updated the Python 'update_release.py' to copy 'version.txt' * Replace space in filename with hyphen. Added more information to hugo-commands.md * Replace space in filename with hyphen. Added more information to hugo-commands.md # Conflicts: # docs/getting-started/view-the-docs-locally/hugo-commands.md * Added a link to pseudo_moving_average.md * Updated title pages for groups * Fixed missing 404 for non-existent pages * Fixed coordinate variable names in the 'Calculating the intersection' example --------- Co-authored-by: Roland Reichwein <Roland.Reichwein@bmw.de> Co-authored-by: John Wellbelove <john.wellbelove@etlcpp.com> Co-authored-by: John Wellbelove <john.wellbelove@etlcpp.co.uk>
2.7 KiB
| title | weight | author |
|---|---|---|
| Implementing a moving average | 10 | John Wellbelove |
Author: John Wellbelove
Date: 2019
Example
Imagine we have accumulated 10 values and our window size is 10.
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
The average of this sequence is (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) / 10 = 5.5
We now add a new sample, 11 to the sequence. As the windows size is 10, we drop the first value.
[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
The average of this sequence is (2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) / 10 = 6.5
Now, averaging over 10 samples each time is not that big an issue, but what if it's 1000 or 10,000? Then, the overhead, both in processing time and storage has started to become a little excessive.
In the case of 10,000 samples of 'double' we are looking at 10,000 additions + 1 division each time a sample is added and a likely storage requirement of 80,000 bytes!
So we have an algorithm that has processing and storage complexity of O(N).
What other values give the same average?
So let's look at the problem again.
There are many ways of getting the same average:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] = Average of 5.5
[ 7, 7, 7, 7, 7, 4, 4, 4, 4, 4 ] = Average of 5.5
But what about this?
[ 5.5, 5.5 , 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5 ] = Average of 5.5
An average of 5.5 can be got from 10 samples of 5.5.
So why store 10 samples?
We can simply simulate the original sum just by multiplying the current average by the number of samples.
The calculation of the average for adding a new sample becomes this:
(Old_Average * Sample_Size) + New_Sample) / (Sample_Size + 1)
Now we have 1 multiplication, 2 additions and 1 division.
Our algorithm now has a complexity of O(1).
We can average over as large a sample size as we like and it will always take the same amount of time and use the same amount of storage. We can also change the sample size on-the-fly if we wish.
There is one downside in that the average will not exactly match the original version, as the actual oldest value is not being erased from the sum, but for the performance and storage advantages it may be a perfectly suitable solution.
You may find that you will need a slightly smaller sample size with the rolling mean to get similar results.
Note
The multiplication may be elided by re-arranging the formula.
Old_Average + ((New_Sample - Old_Average) / (Sample_Size + 1))
This may produce a negative interim value, which may be a problem if you are using scaled unsigned integral types for the average value.
The ETL has an implementation of this algorithm.
[pseudo_moving_average]({{% relref "../maths/pseudo_moving_average.md" %}})