Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Comments on When using the compare function in Array.prototype.sort, how to avoid an element to be processed more than once?
Parent
When using the compare function in Array.prototype.sort, how to avoid an element to be processed more than once?
When using the Array.prototype.sort method, we can pass a compare function as argument. Then, this function can be used to process array's elements, so the comparison is made using some custom criteria.
But I noticed that this can lead to some, let's say, redundancy. For instance, this code:
function getSortKey(item) {
console.log('getSortKey', item);
return parseInt(item);
}
const array = ['4', '16', '8', '2', '6'];
array.sort((a, b) => getSortKey(a) - getSortKey(b));
console.log(array);
I've created the getSortKey function just to know when each string is converted to a number during sorting. The output is:
getSortKey 16
getSortKey 4
getSortKey 8
getSortKey 16
getSortKey 8
getSortKey 16
getSortKey 8
getSortKey 4
getSortKey 2
getSortKey 8
getSortKey 2
getSortKey 4
getSortKey 6
getSortKey 8
getSortKey 6
getSortKey 4
[ '2', '4', '6', '8', '16' ]
Which means that all elements were processed by getSortKey more than once (that wouldn't be necessary, as each string always results in the same number).
This was tested in Chrome. Different browsers/runtimes/implementations may use different sorting algorithms and the exact output might not be the same (but testing in other browsers, it has the same behaviour: the function being called more than once for each element).
The example above was just to show this specific behaviour: the getSortKey function is called many times for the same elements.
But let's suppose that getSortKey is an expensive operation (it takes too much time and/or memory, etc), and the array has lots of elements, and these function calls are a bottleneck that needs to be fixed. The ideal situation is that getSortKey processes each element just once. How to do that?
Post
Create a hash map and precalculate the sort key in it:
// Set up: Create mock input
let u = ['4', '16', '8', '2', '6'];
function expensive_key_fn(x) {
console.log("Doing expensive operation on: " + x)
return String(x);
}
// Create an optimized sort function
let sortKey = {}
u.forEach(function(i) {
sortKey[i] = expensive_key_fn(i)
});
// Use it as sort key
u.sort((a, b) => sortKey[a] - sortKey[b]);
// Show reuslt
console.log(u);
This is basically the poor man's memoization - in fact, simple memoization is often implemented just like this, with a hash map, but lazily, to keep up the illusion/abstraction of the "function call". However, I don't find the abstraction that helpful in this context, so despite being familiar with memoization, I often prefer this idiom just because it's simpler, more accessible to novice programmers who might read my code, and has less cognitive load for me.
Constructing the hash map is O(N), which pales in comparison to O(NlogN) for sorting (assuming JS uses an efficient sorting implementation). That means the work of constructing the hash map is negligible. There is an extra memory cost of O(N) for the map, but it stores only a hash and a result value, not the whole element (if the elements are large).
0 comment threads