[Top][All Lists]

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

[task #16066] Match program should avoid permutations

From: Mohammad Akhlaghi
Subject: [task #16066] Match program should avoid permutations
Date: Mon, 1 Nov 2021 19:17:12 -0400 (EDT)
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:93.0) Gecko/20100101 Firefox/93.0


                 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



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:


  Message sent via Savannah

reply via email to

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