更新对象数组中的对象属性的最有效方法

Question

我想知道更新存储在包含 10k+ 项的数组中的对象属性的最有效方法是什么。

例如，如果我有一个包含这样的对象的数组 {name:"", Price:"")

如果数组已包含该元素，我想替换或更类似于更新价格值。

检查数组是否包含名称 = x 的对象，如果是，则将价格替换为最新价格。

我不想在该数组中包含重复的元素，因此它不会变得很大，我认为如果属性值已存在于其中，我应该更新它。

到目前为止，我已经尝试了几种方法，例如使用 indexOf、splice 或仅使用 for 循环。我想知道处理大数组的最佳性能方式是什么。

let array = [
{name:"abc", price: 24},
{name:"cde", price: 25},
{name:"fgh", price: 22},
{name:"gfds", price: 21},
]

function addToArray(elem){
  //check if array contains elem by checking for name property value
  if(array.filter(el => el.name === elem.name).length > 0){
    //update the array element that has the name of the passed elem
  }
}

Answer 1

您说过您的起点是一个数组，但最有效的方法是使用Map而不是数组，其中键是名称，值是价格或包含价格的对象（取决于是否您需要其他信息）。

使用未排序的数组

但是，如果您使用数组执行此操作，除非我们可以按排序顺序构建/维护数组（请参阅下面的“使用排序数组”），否则没有什么比循环遍历它查找具有给定值的前一个元素更有效的了name。filter不是正确的工具（您不需要它创建的数组）。您可以编写自己的循环：

let element;
for (let index = 0, length = array.length; index < length; ++index) {
    const thisElement = array[index];
    if (thisElement.name === name) {
        // Already have one
        element = thisElement;
        break;
    }
}
if (element) {
    element.price += price;
} else {
    array.push({name, price});
}

对于某些 JavaScript 引擎，如果在循环之前声明、、 ，您可能会获得一点点的速度提升：indexlengththisElement

let element, index, length, thisElement;
for (index = 0, length = array.length; index < length; ++index) {
    thisElement = array[index];
    // ...

但对其他人来说，情况可能恰恰相反。（无论哪种方式都不太可能有很大的区别。）

或者使用find：

const element = array.find(e => e.name === name);
if (element) {
    element.price += price;
} else {
    array.push({name, price});
}

其中任何一个都提供线性查找时间。但如果你使用的是Map，您将获得次线性查找时间。

带地图

如果使用对象作为值：

const element = map.get(name);
if (element) {
    element.price += price;
} else {
    map.set(name, {name, price});
}

或者如果使用价格作为价值：

const currentPrice = map.get(name) ?? 0; // If not found, `get` returns undefined; convert it to 0
map.set(currentPrice + price);

使用排序数组

如果我们可以按排序顺序构建/维护数组（你说过你不能，但也许其他人稍后发现可以），我们可以通过使用二分搜索比线性查找做得更好（代价是稍微多一点的开销当插入新元素时，因为插入点之后的所有元素都必须移动）。这是更多的代码，但如果搜索时间是主要问题，它会减少搜索时间。

const upsert = (array, name, price) => {
    let left = 0;
    let right = array.length;
    while (left < right) {
        let guess = Math.floor((left + right) / 2);
        let element = array[guess];
        if (element.name === name) {
            // Found! Update it
            element.price += price;
            return;
        }
        if (element.name < name) {
            left = guess + 1;
        } else {
            right = guess - 1;
        }
    }
    // Not found, insert it
    array.splice(left, 0, {name, price});
};