Exploring Array Element Matching in JavaScript
Written on
Understanding Array Element Matching
Recently, my team engaged in an in-depth discussion regarding a pull request that examined whether elements from one array could be found in another. In our scenario, one array contained comprehensive information about various items—some of which might be selected—while the other array listed only the IDs of the selected items. Thus, if we located an ID from the selected array in the first array, we could confirm its selection.
This approach is widely applicable beyond just selection; it can also pertain to categorizing items, marking them for deletion, or various other operations. The key takeaway is that one array holds complete data on all potential items, while the other contains a specific subset that we need to verify against.
During our conversation, we explored the performance and maintainability of different methods for executing this type of search. I thought it would be worthwhile to share some of the techniques we discussed, along with a few others that we didn't cover.
Naive O(N * M) Solutions
To clarify, Big O notation serves as a metric for assessing the frequency of data iterations. An O(N*M) complexity implies that we are iterating through two collections—N and M—each approximately once. This is a simplified explanation, but it captures the essence.
The Most Basic Approach
The simplest solution to this problem can be represented as follows:
const itemsToShow = [];
for (var i = 0; i < allItems.length; i++) {
const currentItem = allItems[i];
for (var j = 0; j < selectedItems.length; j++) {
if (selectedItems[j] === currentItem.id) {
itemsToShow.push(currentItem);}
}
}
This method is straightforward and allows for easy integration of additional logic, such as debugging outputs. However, it requires maintaining more code compared to alternative methods we'll examine later, and it iterates through both collections entirely. We can enhance performance slightly by using for...of and implementing a break statement upon finding a match, yet it still remains a somewhat verbose and older approach.
Using Array.prototype Methods
JavaScript’s Array prototype includes several methods designed for locating elements and verifying their existence. We could utilize one of these methods:
const itemsToShow = [];
for (var i = 0; i < allItems.length; i++) {
const currentItem = allItems[i];
if (selectedItems.some((id) => id === currentItem.id)) {
itemsToShow.push(currentItem);}
}
This variation is more concise and will short-circuit when a match is found, eliminating the need for a break statement. Another option is:
const itemsToShow = [];
for (var i = 0; i < allItems.length; i++) {
const currentItem = allItems[i];
if (selectedItems.includes(currentItem.id)) {
itemsToShow.push(currentItem);}
}
While both methods maintain the same Big O complexity, the latter might be more efficient due to the absence of a function call with includes. I find its syntax clearer as well. Other alternatives like find and indexOf exist, but they both involve function calls, and indexOf can complicate matters since it returns a number, which can lead to confusion with falsy values.
If you're working with TypeScript, you might prefer:
const itemsToShow = allItems.filter((currentItem) => selectedItems.includes(currentItem.id));
I share this preference, not only due to TypeScript concerns but also because I lean towards immutability after years of utilizing React and Redux. Even when mutation (like using Array.push) occurs before the value is utilized, I feel an immutable approach is generally better. This is partly due to the potential for misunderstanding when copying and pasting code, and partly because I believe in adopting one consistent method.
That said, remember that this approach incurs an additional function call for each item in the outer loop, so if performance is critical, it may not be your optimal choice.
O(N * log M) Solution
One of my colleagues suggested an O(N * log M) solution, which I hadn't initially considered:
const itemsToShow = [];
for (const currentItem of allItems) {
for (const id of selectedItems) {
if (id === currentItem.id) {
itemsToShow.push(currentItem);
selectedItems.splice(i);
break;
}
}
}
This method enhances loop performance since it removes items from selectedItems once found, thereby reducing the inner loop's size with each iteration of the outer loop. However, this introduces added complexity and the risk of obscure bugs, as other parts of the code might not anticipate that selectedItems will be mutated to an empty array. A solution to this would involve making a copy of selectedItems before commencing the loop, which further complicates matters.
Due to these concerns and my preference for minimizing mutations—even of temporary variables—we ultimately opted not to pursue this approach, although I appreciate the insight it provided.
O(N + M) Solution
In this solution, we create a hash of the selected item IDs, indexed by the item IDs. While this may seem redundant, the real aim is to enable direct ID retrieval without looping through.
One could also simply place a boolean at the index of each selected item since our only concern is verifying whether an item exists within the collection. However, I prefer maintaining at least the semblance of immutability, so I typically employ lodash's keyBy to construct the hash, using the item's value as the property for each key. Although I'm unsure of the exact implementation, I believe it's safe to assume it operates at O(M). The Array.prototype.filter method is roughly O(N), so my preferred implementation might look like this:
const selectedItemsHash = keyBy(selectedItems);
const itemsToShow = allItems.filter((item) => !!selectedItemsHash[item.id]);
What would your preferred method be? Is it one of these, or do you have another strategy in mind?
If you found this discussion engaging, you might also enjoy:
Chrome Developer Tool Tricks to Make You Look Pro
Because you will (that’s what dev tools are for)
javascript.plainenglish.io
Reverse Engineering TypeScript Types
See how typeof and keyof work together
betterprogramming.pub
For more articles, visit PlainEnglish.io. Sign up for our free weekly newsletter and follow us on Twitter, LinkedIn, YouTube, and Discord. Interested in scaling your software startup? Check out Circuit.