[Fixed] How to run heavy logic inside a sorting function one time only

Issue

I need to sort an array of objects based on multiple date fields. Depending on category I sometimes need to exclude some dates.

I would like to avoid the getUsefullJobTimesForCategory function being called so many times, since for a single object the result will always be the same.

Current solution:

Sorting main function

private sortForCategory = (category: string) => (a: RefreshDto, b: RefreshDto) => {
    let jobTimesA: Date[] = this.getUsefullJobTimesForCategory(a, category);
    let jobTimesB: Date[] = this.getUsefullJobTimesForCategory(b, category);

    return this.sortByEarliestJobTimeForCategory(jobTimesA, jobTimesB);
    
  }

Getting required dates valid for sorting
This is the part I would like to do only once per object,
now it will run for every comparison (which is multiple times per entry)

  private getUsefullJobTimesForCategory(dto: RefreshDto, category: string): Date[]{
    //Heavy calculation
  }

Inner sorting logic once the required dates are known

  private sortByEarliestJobTimeForCategory= (jobTimesA: Date[], jobTimesB: Date[]) => {

    //Custom sorting of Date arrays
  }

Solution

Basically, if this.getUsefullJobTimesForCategory(a, category); returns the same thing each time you call it for a and category, do that once and remember those results, then use those results in the sort callback. That means having a way to pass those results to the two levels of sort functions you’re using. Since you can’t pass extra information directly to the callback via the sort method, that means creating a new sort function for the operation that closes over the extra information you want to provide.

Here’s a simplified example:

// A stand-in for the expensive operation
function expensiveOperation(obj) {
    // Busy wait -- DON'T DO THIS IN REAL CODE
    const stop = Date.now() + 50;
    while (Date.now() < stop) {
    }
    return obj.value;
}

// A version of the sort function that repeats the expensive operation
function simpleSortFunction(a, b) {
    return expensiveOperation(a) - expensiveOperation(b);
}

// An array to sort (we make copies)
const sourceArray = [
    {"value": 11},
    {"value": 13},
    {"value": 17},
    {"value": 19},
    {"value": 7},
    {"value": 3},
    {"value": 6},
    {"value": 19},
    {"value": 12},
    {"value": 12}
];

console.log("Running");

// Doing it without optimization
setTimeout(() => {
    console.time("without optimization");
    const array1 = sourceArray.slice();
    array1.sort(simpleSortFunction);
    showResult(array1);
    console.timeEnd("without optimization");
}, 0);

// A function that creates a sort function that gets the expensive
// information once and reuses it
function getSortFunction(array) {
    // Loop through once doing the expensive operations
    const map = new Map(array.map(obj => [obj, expensiveOperation(obj)]));
    return function simpleSortFunction(a, b) {
        // Use the results
        return map.get(a) - map.get(b);
    };
}

// Doing it with optimization
setTimeout(() => {
  console.time("with optimization");
  const array2 = sourceArray.slice();
  console.time("getting expensive values");
  const memoizedSortFunction = getSortFunction(array2);
  console.timeEnd("getting expensive values");
  array2.sort(memoizedSortFunction);
  showResult(array2);
  console.timeEnd("with optimization");
}, 0); // Won't run until the previous one finishes

// Just a function to show sorting results
function showResult(array) {
    console.log(array.map(({value}) => value).join(", "));
}

That example only has to do it for one level rather than two, but you just repeat the same sort of thing as getSortFunction for the second level.

Leave a Reply

(*) Required, Your email will not be published