[Octave-bug-tracker] [bug #63376] tsearchn quite slow (compared to tsearch)

[A.R. Burgers]

URL:
  <https://savannah.gnu.org/bugs/?63376>

                 Summary: tsearchn quite slow (compared to tsearch)
                 Project: GNU Octave
               Submitter: arb
               Submitted: Thu 17 Nov 2022 10:00:18 AM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: Any


    _______________________________________________________

Follow-up Comments:


-------------------------------------------------------
Date: Thu 17 Nov 2022 10:00:18 AM UTC By: A.R. Burgers <arb>
tsearchn seems to be quite slow, as illustrated by the code below with a
triangulation of the unit square. In this example 30 times slower in the 2D
case than tsearch.

tsearch is a compiled built-in function, tsearchn is m-code, with a
non-vectorized for loop on the triangles, but vectorized over the points to be
looked up.


np = 40000; np_lookup = 10000;
x = rand(np,1); y = rand(np,1);
tri = delaunay(x,y);
xi = rand(np_lookup,1); yi = rand(np_lookup,1);

fprintf('np=%d, nt=%d, np_lookup=%d \n', np, size(tri, 1), np_lookup);
tic;
tsearch(x, y, tri, xi, yi);
t1 = toc;
fprintf('tsearch time %g\n', t1);

tic;
tsearchn([x, y], tri, [xi, yi]);
t2 = toc;
fprintf('tsearchn time %g\n', t2);
fprintf('ratio: %g\n', t2/t1);



np=40000, nt=79973, np_lookup=10000
tsearch time 0.891463
tsearchn time 24.2793
ratio: 27.2354








    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?63376>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/