(Learner1D) improve time complexity

[basnijholt]

(original issue on GitLab)

opened by Jorn Hoofwijk (@Jorn) at 2018-12-02T12:45:11.532Z

As it appears the Learner1D is quite fast. Yet once add many points, it slows down quite a lot. Even though I am aware that in practice you will not add more than say, a thousand points. For testing I sometimes need to add 5000 points, which takes up to 50 seconds (on my slow laptop), which is slightly annoying.

Reason being that some parts of the Learner1D have a time complexity higher than should be strictly neccesary. i.e. : _ask_points_without_adding and _subdivide_quals have time complexity O(N), and they are called every time that ask is called, resulting in a total runtime of O(N^2) where N is the total number of added points.

And since I will make it faster anyway, I might as well make a MR

[basnijholt]

originally posted by Jorn Hoofwijk (@Jorn) at 2018-12-02T12:46:33.379Z on GitLab

btw I will use a similar approach as in the LearnerND, which should result in a O(N log N) time complexity.