[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Octave-bug-tracker] [bug #55751] scatter3 performance regression bug in

From: Eddy
Subject: [Octave-bug-tracker] [bug #55751] scatter3 performance regression bug in Octave 5.0.91
Date: Tue, 5 Mar 2019 10:00:23 -0500 (EST)
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Firefox/60.0

Follow-up Comment #17, bug #55751 (project octave):

New idea comes, try the attached patch, it is the method (2) below. The patch
is primary for conceptual verification, no thoughtful test or careful cover of
every edge case.

With this patch, the time cost for the initial reported sample is reduced to
roughly 0.3 second, and the said ever-running example will end in 0.32

Read a bit about graphics.cc and bug #47677.

The current algorithm there, for non-coplanar random data of n points, the
time cost is roughly O(n^3): one n for a single coplanar test, one n for
search the largest coplanar point set, last n for repeated search of each

I can see at least two possible optimizations.

1. Use binary search instead of the full linear search. 
This reduce the time cost to O(n^2 log(n)).

2. Incremental search for coplanar point set. 
This is based on the observation that in the 'eig' method: eig(a'*a), the 3x3
matrix a'*a can be calculated by rank one updates corresponding to each point.
Thus we can check if the newly added point is inside the plane or not in O(1)
(one eig of 3x3 matrix). Time cost is thus reduced to O(n).

To further speed (if necessary), we may need to know the more frequent use
case of patch():
a. large list of many non coplanar input. or
b. coplanar input.

If it is (b), probably adding an initial overall coplanar test can help, at
the cost of slow down case (a). Current implementation favors (a).

(file #46431)

Additional Item Attachment:

File name: bug55751_inc_coplanar.patch    Size:4 KB


Reply to this item at:


  Message sent via Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]