比较java脚本中的对象列表

Question

我想创建一个函数来快速比较对象列表

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`);
    }
  }
}

验证函数会像这样比较两个字段：

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

执行此搜索的最快方法是什么？这些“need”和“have”字符串是类别的 ID，我将它们按“01030204”等级别关联起来。如果知道有用，我愿意据此划分数据，但我真的在寻找有关如何提高搜索速度的想法。

Answer 1

也许你可以对每个对象进行哈希，并使用字典来决定哈希是否有对应的对象。当哈希匹配时，您就可以进行真正的比较。这应该能够在 O(n) 时间内完成这项工作。

编辑：我没有足够仔细地查看问题...

validation

函数非常不寻常，所以我认为我的方法不起作用。对不起。

Answer 2

当您必须在同一个数组上重复多次时，

includes

并不是一种有效的方法。另外，如果您通过这些

have

字符串来键入数据，并注册每个帖子可以访问的

need

字符串，那么您将获得更有效的邻接列表（图形数据结构），并希望能够更快地找到这样的匹配对。

由于您没有提供示例数据，我不得不发明一些。这是一个可能的实现：

// 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)}`);
            }
        }
    }
}