Compare List of objects in java script

Question

I want to create a function to compare a list of objects in the fast way

for (let i = 0; i < posts.length - 1; i++) {
  for (let j = i + 1; j < posts.length; j++) {
    const post1 = posts[i];
    const post2 = posts[j];

    if (validation(post1, post2)){
      console.log(`found comparation`);
    }
  }
}

And the validation function compares two fields like this:

const validation = (post1, post2) => post1.need.includes(post2.have) &&
    post2.need.includes(post1.have);

What would be the fastest way to perform this search? These 'need' and 'have' strings are IDs for a category where I associate them by levels like '01030204'. In case it's useful to know, I'm open to dividing the data based on this, but I'm really looking for ideas on how to improve the speed of this search.

Answer 1

includes is not an efficient method when you have to repeat it on the same array several times. Also, if you would key your data by those have strings, and register for each of them which are the need strings that can be reached by which posts, then you have a more efficient adjacency list (graph data structure), and can hope to find such matching pairs faster.

As you didn't provide sample data, I had to invent some. Here is a possible implementation:

// Sample data
const posts = [
    { id: 1, have: "a", need: ["b", "c", "d"] },
    { id: 2, have: "a", need: ["b", "e"] },
    { id: 3, have: "b", need: ["c"] },
    { id: 4, have: "c", need: [] },
    { id: 5, have: "d", need: ["a", "c"] },
    { id: 6, have: "d", need: ["a"] },
    { id: 7, have: "e", need: ["b", "d"] },
];

// Create a 2-level dictionary to register "edges" from "have" to "need"
// identifying which posts establish each edge.
const map = {};
for (const post of posts) {
    const needs = (map[post.have] ??= {});
    for (const need of post.need) {
        (needs[need] ??= []).push(post);
    }
}

// Iterate the 2-level dictionary to find matching pairs:
for (const [start, startMap] of Object.entries(map)) {
    for (const [end, posts] of Object.entries(startMap)) {
        if (end < start) continue;
        const backPosts = map[end]?.[start]; // This has the opposite directed edges
        if (!backPosts) continue;
        for (const post1 of posts) {
            for (const post2 of backPosts) {
                console.log(`Found mutually related posts via "need" ${end}:`);
                console.log(`  ${JSON.stringify(post1)}`);
                console.log(`  ${JSON.stringify(post2)}`);
            }
        }
    }
}