[task #16066] Match program should avoid permutations

[Mohammad Akhlaghi]

URL:
  <https://savannah.gnu.org/task/?16066>

                 Summary: Match program should avoid permutations
                 Project: GNU Astronomy Utilities
            Submitted by: makhlaghi
            Submitted on: Mon 01 Nov 2021 11:17:10 PM UTC
         Should Start On: Mon 01 Nov 2021 12:00:00 AM UTC
   Should be Finished on: Mon 01 Nov 2021 12:00:00 AM UTC
                Category: Match
                Priority: 5 - Normal
              Item Group: Enhancement
                  Status: None
                 Privacy: Public
        Percent Complete: 0%
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any
                  Effort: 0.00

    _______________________________________________________

Details:

Currently the Match program takes the fully input permutation, applies it over
the full length of both inputs (even the non-matched rows), then only selects
the top rows (this is how the permutation is defined).

However, when the inputs are large (for example 1 million rows), and only a
small fraction match (for example 30000 rows), the permutation above will
actually be slower than the actual matching! 

So instead of permuting the whole array, its simpler to just allocate the
output columns separately and fill them with the order specified in the
permutation (only for the rows that matched).

This won't have any effect for a small input, but for a large input in the
scenario above, it will lead to major speed improvements.




    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/task/?16066>

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