在保持顺序和现有实例的同时用另一个数组的元素改变一个数组

Question

需要一个算法的帮助，该算法采用两个数组并在它们之间进行特定比较以保持相同的顺序：

如果 _ID 存在但 _ID 不在覆盖器中，则不在结果中包含元素
如果 _ID 在覆盖器中但 _ID 不在现有中，则将元素添加到 RESULT
如果 _ID 在现有和覆盖器中，则将 _ID 为 version/instance 的元素从现有添加到结果

大写字母代表参考_ID v# 表示引用 _ID

的 version/instance

1.

现有：[Av1 Bv1 Cv1 Ev1 Fv1 Gv1]

覆盖者：[ Bv2 Dv1 Fv2 Hv1 Jv1 ]

结果：[ Bv1 Dv1 Fv1 Hv1 Jv1 ]

2.

现有：[ Bv1 Cv1 Ev1 Fv1 Gv1 ]

改写者：[Av1 Bv2 Dv1 Fv2 Hv1 Jv1]

结果：[Av1 Bv1 Dv1 Fv1 Hv1 Jv1]

3.

现有：[Av1 Bv1 Cv1 Ev1 Fv1 Gv1]

改写者：[Av2 Bv2 Dv1 Fv2 Hv1 Jv1]

结果：[Av1 Bv1 Dv1 Fv1 Hv1 Jv1]

4.

现有：[ Cv1 Dv1 Ev1 ]

改写者：[Av1 Bv1 Dv2 Fv1 Hv1 Jv1]

结果：[Av1 Bv1 Dv1 Fv1 Hv1 Jv1]

5.

现有：[Av1 Bv1 Cv1 Ev1 Fv1 Gv1]

改写者：[ Dv1 ]

结果：[Dv1]

我正在寻找一个 log(n) 函数，它一次执行此变异操作（可能对现有和覆盖器都有主索引，但我不确定）。

不想使用 indexOf。

这是我使用缩尾技术的 log(n^2) 解决方案：

let eIndx = 0,
    existing = [ Av1, Bv1, Cv1, Ev1, Fv1, Gv1 ],
    overwriter = [ Bv2, Dv1, Fv2, Hv1, Jv1 ];

overwriter.map( element => {

    while( element._ID !== existing[ eIndx ]._ID && 
           eIndx       !== existing.length ) {

        delete existing[ eIndx ];

        ++eIndx;
    }

    return eIndx !== existing.length ? existing[ eIndx ] : element;
});

如果现有 _ID 中的 none 个处于覆盖状态，则此解决方案最慢。

我不确定是否应该遍历现有数组或覆盖数组。

在我从 post 中解释的扩展（更复杂的）解决方案中，我遍历了覆盖器，并且我有一个哈希字典来参考将来是否已经存在 _ID/版本组合（稍后尚未迭代的索引）数组。我不能再使用那个全局字典，我想弄清楚我是否需要为每个数组实例制作一个本地字典，或者是否有一种方法我不需要字典而只使用枢轴进行比较。我在 log(n) 解决方案中看到的一个问题是，如果不遍历所有现有数组，它不知道覆盖的第一个元素是否是新的 _ID。

大多数时候我正在寻找尽可能快的东西

非常感谢您分享帮助。

Answer 1

您可以使用 Map 并检查 ID 是否存在。

function merge(existing, overwriter) {
    const getId = s => s.split('v')[0]; // or whatever is suitable

    var versions = new Map;

    existing.forEach(s => versions.set(getId(s),  s));
    return overwriter.map(s => versions.get(getId(s)) || s);
}

console.log(merge([ 'Av1', 'Bv1','Cv1','Ev1','Fv1', 'Gv1' ],[ 'Bv2', 'Dv1','Fv2','Hv1','Jv1']));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

我发布这个答案作为讨论的基础，尽管 based on previous discussion，我知道它不能完全满足您的需求。

它是递归的，这在 Javascript 中可能仍然意味着它很慢或可能溢出堆栈。不过，它已准备好进行尾调用优化，因此最终它不应该太慢。但是作为递归，代码非常干净。但是，它基于我根据您的示例所做的假设，即列表已排序。

const original = [{"_ID": 2, "val": "a0"}, {"_ID": 3, "val": "a1"}, {"_ID": 5, "val": "a2"}, {"_ID": 7, "val": "a3"}, {"_ID": 11, "val": "a4"}, {"_ID": 13, "val": "a5"}, {"_ID": 17, "val": "a6"}, {"_ID": 19, "val": "a7"}]

const overwriter = [{"_ID": 1, "val": "b0"}, {"_ID": 2, "val": "b1"}, {"_ID": 3, "val": "b2"}, {"_ID": 5, "val": "b3"}, {"_ID": 8, "val": "b4"}, {"_ID": 13, "val": "b5"}, {"_ID": 21, "val": "b6"}, {"_ID": 34, "val": "b7"}]

const mergeLists = (a, b, combined = []) => a.length == 0
    ? combined.concat(b)
    : b.length == 0 
        ? combined
        : a[0]._ID < b[0]._ID 
            ? mergeLists(a.slice(1), b, combined)
            : a[0]._ID == b[0]._ID
                ? mergeLists(a.slice(1), b.slice(1), combined.concat([a[0]]))
                : mergeLists(a, b.slice(1), combined.concat([b[0]]))
         

console.log(mergeLists(original, overwriter))

鉴于我们发现它们没有排序，我认为没有什么比在本地重新创建该索引更好的了。它肯定比每次都搜索列表更快（这将是O(m * n)。）

属性查找，使用对象作为索引，只比 O(1) 慢一点点，所以，以额外的 space 为代价，你仍然应该能够做到这在 O(m + n).

该代码应该非常简单：通过将现有数据缩减为一个对象来创建索引，以 _ID 属性为键，然后迭代覆盖器，将匹配项放入输出中来自索引的一个，如果它存在，否则被覆盖。

这仍然没有变异。您可以使用适当的 splice 来实现这一点，但如果您这样做，请确保反向迭代。但我建议在任何情况下都不要变异。

无论如何，此代码都适用于我在上面使用的数据。如果您的 ID 不是字符串或数字，您应该使用 Nina 的 Map 版本：

const mergeLists = (original, overwriter) => {
  const index = original.reduce((idx, val) => (idx[val._ID] = val, idx), {})
  return overwriter.map(val => index[val._ID] || val)
}

Answer 3

你说的是 log(n) 和 log(n²) 但显然分别表示 O(n) 和 O(n²)。

如果您首先为现有值创建一个映射，并以其 id 值作为键，则可以实现 O(n) 时间复杂度。然后覆盖数组的循环可以在每次获取的恒定时间内获取相应的元素。

这是一个例子：

const existing = [
        { _id: "A", version: 1 }, 
        { _id: "B", version: 1 },
        { _id: "C", version: 1 },
        { _id: "E", version: 1 }, 
        { _id: "F", version: 1 },
        { _id: "G", version: 1 },
    ],
    overwriter = [
        { _id: "B", version: 2 },
        { _id: "D", version: 1 },
        { _id: "F", version: 2 },
        { _id: "H", version: 1 },
        { _id: "J", version: 1 },
    ];

const map = new Map(existing.map( o => [o._id, o] ));
const result = overwriter.map( el => map.get(el._id) || el );

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

在保持顺序和现有实例的同时用另一个数组的元素改变一个数组

Mutating an array with the elements of another array while maintaining order and existing instances

javascript

arrays

masking

mutation