javascript的array.indexOf的时间复杂度是多少？ [英] What is the time complexity of javascript's array.indexOf?

问题描述

indexOf是简单地遍历数组还是执行更快的操作？
我知道这是依赖于实现的但是Chrome或Firefox做了什么？

Does indexOf simply walk through the array or does it do something that is faster? I know that this is implementation dependent but what does Chrome or Firefox do?

推荐答案

最有效的查找方式匹配未排序数组中的值的第一个索引是按顺序遍历列表，即O（n）。 MDN 也有一些提示：

The most efficient way to find the first index matching a value in an unsorted array is to just walk through the list in order, which is O(n). MDN also has some hints:

返回可以在数组中找到给定元素的第一个索引，如果是，则返回-1不存在。

Returns the first index at which a given element can be found in the array, or -1 if it is not present.

[...]

fromIndex

fromIndex

默认值：0（搜索整个数组）

开始搜索的索引。如果索引大于或等于数组的长度，则返回-1，这意味着不会搜索该数组。如果提供的索引值为负数，则将其作为数组末尾的偏移量。注意：如果提供的索引为负数，仍会从前到后搜索数组。如果计算的索引小于0，则将搜索整个数组。

Default: 0 (Entire array is searched)
The index to start the search at. If the index is greater than or equal to the array's length, -1 is returned, which means the array will not be searched. If the provided index value is a negative number, it is taken as the offset from the end of the array. Note: if the provided index is negative, the array is still searched from front to back. If the calculated index is less than 0, then the whole array will be searched.

如果您想知道，这里是WebKit如何实现它的方式 ：

EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
{
    // 15.4.4.14
    JSObject* thisObj = exec->hostThisValue().toThis(exec, StrictMode).toObject(exec);
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

    unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
    JSValue searchElement = exec->argument(0);
    for (; index < length; ++index) {
        JSValue e = getProperty(exec, thisObj, index);
        if (exec->hadException())
            return JSValue::encode(jsUndefined());
        if (!e)
            continue;
        if (JSValue::strictEqual(exec, searchElement, e))
            return JSValue::encode(jsNumber(index));
    }

    return JSValue::encode(jsNumber(-1));
}

这篇关于javascript的array.indexOf的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！