On 3/23/18 7:29 PM, H. S. Teoh wrote:
Well, looking at the implementation of std.getopt turned up the
disturbing fact that the program's argument list is actually scanned
*multiple times*, one for each possible option(!). Besides the bogonity
that whether or not searchPaths will be set prior to finding -l depends
on the order of arguments passed to getopt(), this also represents an
O(n*m) complexity in scanning program arguments, where n = number of
arguments and m = number of possible options.
And this is not to mention the fact that getoptImpl is *recursive
template*. Why, oh why?
Am I the only one who thinks the current implementation of getopt() is
really stupid?? Can somebody please talk some sense into me, or point
out something really obvious that I'm missing?
Affirmative. The implementation is quadratic (including a removal of the
option from the string). This is intentional, i.e. understood and
acknowledged while I was working on it. Given that the function is only
called once per run and with a number of arguments at most in the
dozens, by the time its complexity becomes an issue the function is long
beyond its charter.
This isn't the only instance of quadratic algorithms in Phobos.
Quicksort uses an insertion sort - a quadratic algorithm - for 25
elements or fewer. That algorithm may do 600 comparisons in the worst
case, and it's potentially that many for each group of 25 elements in a
large array.
Spending time on improving the speed of getopt is unrecommended. Such
work would add no value.
Andrei
