# How to compute Maximum Drawdown faster and highlight data-list-line on the plot?

Given a list as

lst = {31.1, 30.67, 30.53, 30.8, 30.5, 30.44, 30.22, 29.08, 29.16, 28.76,
28.9, 28.59, 28.45, 28.13, 27.87, 28.47, 27.76, 27.87, 27.59, 27.34,
27.47, 28.15, 28.28, 27.78, 28.38, 28.31, 28.14, 27.98, 27.87, 27.73,
28.29, 28.6, 29.06, 29.04, 28.82, 28.74, 28.69, 28.76, 28.25, 27.68,
27.4, 27.05, 27.79, 27.44, 27.94, 27.95, 27.86, 27.81, 27.23, 27.05,
26.69, 26.98, 27.34, 27.15, 27.25, 27.29, 27.81, 27.78, 27.69, 27.38,
27.25, 27.21, 27.51, 27.04, 26.92, 27.02, 26.69, 26.65, 26.56, 26.87,
26.82, 26.52, 27., 27.31, 27.29, 27.97, 27.81, 28.07, 27.92, 28.21,
27.17, 27.21, 27.26, 25.83, 26.07, 25.68, 25.46, 25.62, 24.86, 25.5,
26.55, 25.95, 26.03, 26.04, 25.99, 25.42, 25.68, 26.03, 26.06, 26.76,
26.65, 26.59, 26.41, 26.36, 25.99, 26.31, 26.55, 26.32, 26.68, 26.79,
27.04, 26.46, 26.52, 26.45, 25.79, 25.76, 25.75, 26.02, 25.67, 25.88};


and it could be shown using ListLinePlot How to compute its Maximum Drawdown faster using list operation, and hilight the data part on the list plot? the definition of Maximum Drawdown could be found here.https://www.investopedia.com/terms/m/maximum-drawdown-mdd.asp https://www.wikiwand.com/en/Drawdown_(economics)

# $$O(n^2)$$ Imlementation

Here is a brute-force method with $$O(n^2)$$ complexity and $$O(n^2)$$ memory usage.

A = LowerTriangularize[Outer[Plus, -#, #]] &[DeveloperToPackedArray[lst]];
idx = Ordering[#, -1][] & /@ A;
minpos = Ordering[Extract[A, Transpose[{Range[Length[A]], idx}]], -1][];
maxpos = idx[[minpos]];

mdd = (lst[[maxpos]] - lst[[minpos]])
daycount = minpos - maxpos
losspercentage = mdd/lst[[maxpos]] 100

ListLinePlot[{
Transpose[{Range[Length[lst]], lst}],
Transpose[{Range[maxpos, minpos], lst[[maxpos ;; minpos]]}]
},
PlotRange -> All,
PlotStyle -> {Automatic, Red}
]


6.24

88

20.0643 # $$O(n)$$ Imlementation

Here is a prototype of a functions that should find the positions that realize the maximum drop down:

getMDDPosition = Compile[{{x, _Real, 1}},
Block[{y, min, max, minpos, maxpos, mdd, mddminpos, mddmaxpos},
mddminpos = mddmaxpos = maxpos = minpos = 1;
max = min = CompileGetElement[x, 1];
mdd = 0.;
Do[
y = CompileGetElement[x, i];
If[y <= min,
min = y;
minpos = i;
,
If[y >= max,
If[max - min >= mdd,
mdd = max - min;
mddmaxpos = maxpos;
mddminpos = minpos;
];
max = min = y;
maxpos = minpos = i;
];
],
{i, 2, Length[x]}];
If[max - min >= mdd,
mdd = max - min;
mddmaxpos = maxpos;
mddminpos = minpos;
];
{mddmaxpos, mddminpos}
],
CompilationTarget -> "C",
RuntimeAttributes -> {Listable},
Parallelization -> True,
RuntimeOptions -> "Speed"
];


Call it like

{maxpos, minpos} = getMDDPosition[lst]


{1, 89}

Use this at your own risk; I haven't conducted too much of testing...

# Edit

Towards the problem that the compiled function needs to be recompiled in each session: One can use these very easy mechanics to memoize the compiled library. This way, only the loading into Mathematica has to be performed at runtime.

Write something like this into your package. When the package is loaded it checks whether a library already exists. If it does not exist, it compiles getMDDPosition and copy its library to a file where it can be located afterwards. (This is only an example; best to write into a subdirectory of your package.) If it does exist, it just loads it from file. Note that still certain Mathematca packages for the treatment of compiled functions have to be loaded, but it has to be done only once per session, independent of the number of compiled functions you load this way.

Needs["CCompilerDriver"];
If[FileExistsQ["getMDDPosition.dylib"] && FileExistsQ["getMDDPosition.m"],
getMDDPosition = Import["getMDDPosition.m"];
,
With[{libfile = "getMDDPosition" <> CCompilerDriverCCompilerDriverBase$PlatformDLLExtension}, getMDDPosition = Compile[{{x, _Real, 1}}, Block[{y, min, max, minpos, maxpos, mdd, mddminpos, mddmaxpos}, mddminpos = mddmaxpos = maxpos = minpos = 1; max = min = CompileGetElement[x, 1]; mdd = 0.; Do[y = CompileGetElement[x, i]; If[y <= min, min = y; minpos = i;, If[y >= max, If[max - min >= mdd, mdd = max - min; mddmaxpos = maxpos; mddminpos = minpos; ]; max = min = y; maxpos = minpos = i;]; ], {i, 2, Length[x]} ]; If[max - min >= mdd, mdd = max - min; mddmaxpos = maxpos; mddminpos = minpos; ]; {mddmaxpos, mddminpos} ], CompilationTarget -> "C", RuntimeAttributes -> {Listable}, Parallelization -> True, RuntimeOptions -> "Speed"]; CopyFile[getMDDPosition[[-1, 1]], libfile, OverwriteTarget -> True]; getMDDPosition[[-1, 1]] = libfile; ]; Export["getMDDPosition.m", getMDDPosition, "Package"]; ]  Instead of loading "CCompilerDriver" here, it might be a better strategy to put it into the dependency list of your package (the second argument of BeginPackage). • Thanks! the upper two block codes are tested working well when list length is less then 10000, or the first one may throw exception as  SystemException["MemoryAllocationFailure"]'. – Jerry Dec 3 '18 at 9:18 • @Jerry You're welcome. Thanks also for the feedback. The memory allocation failure comes expected for the$O(n^2)$algorithm as a matrix of size$n \times n$has to be allocated. I am a bit surprised that this cause problems for$n = 10000\$ already because the matrix should be about 800 MB in size so that it should fit easily into RAM... – Henrik Schumacher Dec 3 '18 at 9:32
• Sorry to clearfy that I did tests with lst=Table[RandomReal[],{10000}], In fact, the first algorithm spends about 0.45-0.7seconds, when 10000 doubles, time spent becomes longer, or throw memory allocation exeption at last, it depends on the computer memory that could be used at the time. – Jerry Dec 3 '18 at 9:53
• The compile version has insufficient problem that when I put it into a package file, every time I load or reload the package it would spend time to compile again, such that it make the time spent on package initialization becoming longer. the more compile functions, the more time shall elapse. I wonder how to fix it so that the compile action could be performed mannually? – Jerry Dec 3 '18 at 10:01
• Please see my edit. It shows how you enforce that the function in compiled only once when the package is loaded for the first time. – Henrik Schumacher Dec 3 '18 at 10:25