Какова временная сложность массива javascript?метод indexOf?

Question

Какова временная сложность массива javascript?метод indexOf?

IndexOf просто проходит через массив или делает что-то более быстрое?
Я знаю, что это зависит от реализации, но что делает Chrome или Firefox?

507 3

javascript

3 ответов:

Comments

Ничего не найдено.

Brendan Long · Accepted Answer · 2015-08-02 13:43:51

Самый эффективный способ найти первый индекс, соответствующий значению в несортированном массиве, - это просто пройти по списку в порядке, который равен O(n). MDN также имеет некоторые подсказки:

Возвращает первый индекс, при котором данный элемент может быть найден в массиве, или -1, если он отсутствует.

[...]

FromIndex

По умолчанию: 0 (выполняется поиск всего массива)
Индекс для начала поиска. Если индекс больше или равен к длине массива возвращается значение -1, что означает, что поиск в массиве производиться не будет. Если предоставленное значение индекса является отрицательным числом, то оно берется как смещение от конца массива. Примечание: если предоставленный индекс отрицателен, массив по-прежнему ищется спереди назад . Если вычисляемый индекс меньше 0, тобудет произведен поиск всего массива .

Если вам интересно, вот как 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));
}

triggerNZ · Accepted Answer · 2013-10-10 07:38:34

Не имея никаких гарантий относительно природы или порядка элементов в массиве, вы не можете сделать лучше, чем O (n), поэтому он будет проходить через массив. Даже если бы это было для распараллеливания фактического поиска между процессорами (не знаю, делают ли это firefox или chrome, но они могли бы), это не меняет временной сложности с конечным числом процессоров.

Matheus Pavin · Accepted Answer · 2018-05-02 15:01:13

В ECMA6 у вас есть set(), и тогда вы можете сделать:
var obj = new set();
obj.add(1);
obj.has(1) == true;
obj.has(2) == false;
Я не знаю насчет исполнения, но более разборчиво