TAChart: speed up AddXY function for long series
Original Reporter info from Mantis: Ask
-
Reporter name: Alexander S. Klenin
Original Reporter info from Mantis: Ask
- Reporter name: Alexander S. Klenin
Description:
TChartSeries.AddXY inserts new point into a sorted list, which have O(N^2) computational cost.
This can be a problem for really long (>10000 points) series.
This issue is not entirely theoretical, and was reported by at least one
user (in Russian): http://freepascal.ru/forum/viewtopic.php?f=5&t=3821
Attached patch partially avoids the problem by changing algorithm so it amortized O(N) cost in the important particular case of already ordered points.
We now can advise the users to pre-sort their points by X coordinate to avoid speed penalty.
Steps to reproduce:
See the second attached patch, which makes it possibile to add many points at once to the TAChart demo.
Try adding 100000 points with and without the optimization patch.
I am not sure if the demo patch should be applied -- on the one hand, it may be helpful for some users. On the other hand, the point of the demo it to be as simple as possible -- and this patch adds (a small amount of) complexity.
Mantis conversion info:
- Mantis ID: 12642
- Version: 0.9.27 (SVN)
- Fixed in version: 0.9.27 (SVN)
- Fixed in revision: 17504 (#0d6bfec7)