On Saturday, 24 March 2018 at 03:04:41 UTC, Andrei Alexandrescu
wrote:
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
Is there a possibility of improving this function?
- While quadratic, for low N, quadratic isn't a big deal. So at
what point does quadratic for this function become "a problem"?
- If it is a problem, what's stopping someone from improving it?
Last question though, is there any kind of list of features, and
minor features and fixes that can or need to be done? Perhaps it
already exists, but it seems like it'd be great to have a wiki of
contribution sites (like this function) that someone could just
browse and go "Hey, I know how to do X, maybe I'll take a crack
at it." That way, devs who don't have time to improve something
"low on the list" could still outsource it in a clear list
instead of people who just happen to see it on the forum at the
right place right time.
