Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Online algorithms #120

Open
buybackoff opened this issue Jun 18, 2017 · 0 comments
Open

Online algorithms #120

buybackoff opened this issue Jun 18, 2017 · 0 comments
Labels
design future math performance

Comments

@buybackoff
Copy link
Member

buybackoff commented Jun 18, 2017 •
edited

Spreads library is designed for online algorithms (among other goals). Some of non-trivial ones are already implemented: moving median with fixed length, moving regression (commented out temporarily).

Here is the place to collect links to interesting online algorithms that could be useful and have known implementations.

Online algorithm

#75, #82

Online Algorithms in High-frequency Trading

Longest increasing subsequence

Insertion sort (Review: this is the method SortedDeque is waiting to implement and even has/had comments)

Algorithms for calculating variance

Boost.Accumulators
buybackoff added a commit that referenced this issue Jun 20, 2017
@buybackoff
Implement generic SpanOp cursor, which allows to apply IOnlineOp oper…
80766df 
…ation to a span, which could be defined by a number of elements, a width or a custom condition. #120

**SMADirectAndIndirectSpanOpBenchmark**
*The window width is 20. SMA MOPS are calculated as a number of calculated values multiplied by the width, which is equivalent to the total number of cursor moves for Window case. SortedMap line is for reference - it is the speed of raw iteration over SM without Windows overheads.*
 Case                |    MOPS |  Elapsed |   GC0 |   GC1 |   GC2 |  Memory
-------------        |--------:|---------:|------:|------:|------:|--------:
SMA Direct           |  333.33 |    60 ms |   0.0 |   0.0 |   0.0 | 0.000 MB
SMA Indirect         |  303.03 |    66 ms |   0.0 |   0.0 |   0.0 | 0.000 MB
SortedMap            |  100.00 |    10 ms |   0.0 |   0.0 |   0.0 | 0.000 MB
SMA Window           |   19.90 |  1005 ms |   0.0 |   0.0 |   0.0 | 0.008 MB
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
design future math performance
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@buybackoff