Gamestudio Links
Zorro Links
Newest Posts
'AssetFrameZone' undeclared identifier
by AndrewAMD. 12/09/22 13:40
How to combile shader FX?
by NicolaB. 12/08/22 08:18
Function refresh?
by Quad. 12/07/22 20:56
AUM Magazine
Latest Screens
DEAD TASTE
Tactics of World War I
Hecknex World
Scheherazade's Journey
Who's Online Now
4 registered members (Grant, ozgur, NexusP47, PeroPero), 1,050 guests, and 3 spiders.
Key: Admin, Global Mod, Mod
Newest Members
pythno, rxs, wezcam, juliastratos, DavidK
18872 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Percentile function very slow #486781
10/06/22 10:16
10/06/22 10:16
Joined: Jul 2022
Posts: 4
Velika Gorica
M
MislavSag Offline OP
Guest
MislavSag  Offline OP
Guest
M

Joined: Jul 2022
Posts: 4
Velika Gorica
Hi,

I am new to Zorro. I have donwloaded minute data from IB for few symbols and start experimenting.

Here is my first sample script:

```
function run() // at any bar
{
// Setup
StartDate = 20200101;
EndDate = 20200201;
BarPeriod = 1;
LookBack = 4800;

// Universe
assetList("AssetsIB");

// trading strategy
while(asset(loop("AMZN", "AXP"))){

// help ts
// The priceO, priceH, priceL, priceC functions can be also used under the names priceOpen, priceHigh, priceLow, priceClose.
vars close = series(priceC());
vars close_returns = series(ROCP(close, 4800 - 1));

// calculate percentile
var percentile_upper = Percentile(close_returns, 4800, 0.99);
//var percentile_lower = Percentile(close_returns, CLOSE_WINDOW_SIZE, 0.01);

/*
// get above and belowe returns if any
if(priceC(0) > percentile_upper){
var above = price(0) - percentile_upper;
}
*/
}
}

```
The code works, but it is pretty slow. I have set only one month for backtest period, but it takes more than 5 minutes for just 2 symbols (I have stopped execution after 5 minutes so I don't know how long it takes in the end ).

Is the problem in my code or is just Percentile function so slow?

Re: Percentile function very slow [Re: MislavSag] #486782
10/06/22 14:22
10/06/22 14:22
Joined: Aug 2017
Posts: 231
Netherlands
G
Grant Online
Member
Grant  Online
Member
G

Joined: Aug 2017
Posts: 231
Netherlands
4800 minutes is a long time to calculate something, that's all I noticed.

You can use the timer function to print calculation times from steps in your code, see https://zorro-project.com/manual/en/timer.htm

Re: Percentile function very slow [Re: MislavSag] #486784
10/06/22 18:49
10/06/22 18:49
Joined: Jul 2022
Posts: 4
Velika Gorica
M
MislavSag Offline OP
Guest
MislavSag  Offline OP
Guest
M

Joined: Jul 2022
Posts: 4
Velika Gorica
I know where is the bottleneck. Percentile function is slow. 4800 observations doesn't seems to much to me. May I will try with some other C++ implementation.

Re: Percentile function very slow [Re: MislavSag] #486785
10/06/22 19:40
10/06/22 19:40
Joined: Feb 2017
Posts: 1,587
Chicago
AndrewAMD Offline
Serious User
AndrewAMD  Offline
Serious User

Joined: Feb 2017
Posts: 1,587
Chicago
I bet Percentile makes a memory allocation at every call. If that's true, it might be helpful if there were a different version where the user can supply a data buffer.

Re: Percentile function very slow [Re: MislavSag] #486790
10/07/22 10:15
10/07/22 10:15
Joined: Jul 2000
Posts: 27,916
Frankfurt
jcl Offline

Chief Engineer
jcl  Offline

Chief Engineer

Joined: Jul 2000
Posts: 27,916
Frankfurt
It makes no memory allocation, but a quicksort on every call. Other C++ implementations will probably not help. But if someone knows a trick to calculate percentiles of arbitrary arrays with no sorting, we'll gratefully implement it.

For the percentile of a time series, if you're in need of speed, you could keep a sorted copy of that series, and insert new values and remove old values with bsearch. This would be faster than the percentile function. But needs a bit more code in your script.

Re: Percentile function very slow [Re: MislavSag] #486791
10/07/22 13:22
10/07/22 13:22
Joined: Feb 2017
Posts: 1,587
Chicago
AndrewAMD Offline
Serious User
AndrewAMD  Offline
Serious User

Joined: Feb 2017
Posts: 1,587
Chicago
How is Percentile quicksorting without using its own mutable buffer? Is it actually making changes to the input buffer?

EDIT: Or maybe Percentile has its own static mutabable buffer but only resizes it when necessary. That would make sense.

Last edited by AndrewAMD; 10/07/22 13:44.
Re: Percentile function very slow [Re: MislavSag] #486793
10/07/22 15:46
10/07/22 15:46
Joined: Dec 2019
Posts: 43
ozgur Online
Newbie
ozgur  Online
Newbie

Joined: Dec 2019
Posts: 43
Originally Posted by jcl
It makes no memory allocation, but a quicksort on every call. Other C++ implementations will probably not help. But if someone knows a trick to calculate percentiles of arbitrary arrays with no sorting, we'll gratefully implement it.


May I suggest P2 quantile estimator? It doesn't require storing whole distribution, instead needs an array with size of 5.
https://www.cse.wustl.edu/~jain/papers/ftp/psqr.pdf

A blog has several posts about it, it seems to produce results closer to true quantile:
https://aakinshin.net/posts/p2-quantile-estimator/
https://aakinshin.net/posts/mp2-quantile-estimator/
https://aakinshin.net/tags/research-p2qe/

Last edited by ozgur; 10/07/22 15:49.
Re: Percentile function very slow [Re: MislavSag] #486794
10/08/22 08:32
10/08/22 08:32
Joined: Jul 2000
Posts: 27,916
Frankfurt
jcl Offline

Chief Engineer
jcl  Offline

Chief Engineer

Joined: Jul 2000
Posts: 27,916
Frankfurt
Thank you for the links. I am not sure if estimation works well for very small percentliles, but I'll keep that in mind for a future version. Either a faster percentile estimation, or a fast time series percentile with the method that I suggested above.

Andrew: Zorro functions use buffers from a shared memory area that is resized when necessary. This is a trick from game engines that must not allocate memory at runtime at all.

Re: Percentile function very slow [Re: jcl] #486795
10/11/22 09:17
10/11/22 09:17
Joined: Aug 2022
Posts: 48
alun Offline
Newbie
alun  Offline
Newbie

Joined: Aug 2022
Posts: 48
If the array is already sorted on a previous step can we just insert the next element at the right place and remove the previous (FIFO) one?

I believe that would make it O(N) in the worst case instead of O(N*log(N)) as with quick sorting from scratch.

Maybe appending to the sorted array and then sorting it again would be of a similar.

Other ideas - see if could implement something like: http://hdrhistogram.org/
which sacrifices precision for performance

Re: Percentile function very slow [Re: MislavSag] #486796
10/11/22 12:41
10/11/22 12:41
Joined: Jul 2000
Posts: 27,916
Frankfurt
jcl Offline

Chief Engineer
jcl  Offline

Chief Engineer

Joined: Jul 2000
Posts: 27,916
Frankfurt
In fact inserting by bsearch is O(log N) when you keep a sorted array.


Moderated by  Petra 

Powered by UBB.threads™ PHP Forum Software 7.7.1