objects - ¿Cuál es la complejidad del tiempo de array.indexOf de javascript?

javascript get index of object in array

Question

¿IndexOf simplemente camina a través de la matriz o hace algo que es más rápido? Sé que esto depende de la implementación, pero ¿qué hace Chrome o Firefox?

Answer 1

En ECMA6, tienes el set() , y luego puedes hacer:

var obj = new set();
obj.add(1);
obj.has(1) == true;
obj.has(2) == false;

No sé sobre el rendimiento, pero es más legible.

Answer 2

La forma más eficiente de encontrar el primer índice que coincida con un valor en una matriz no clasificada es simplemente recorrer la lista en orden, que es O (n). MDN también tiene algunos consejos:

Devuelve el primer índice en el que se puede encontrar un elemento determinado en la matriz, o -1 si no está presente.

[...]

desde el índice

Predeterminado: 0 (Se busca la matriz completa)
El índice para iniciar la búsqueda en. Si el índice es mayor o igual que la longitud de la matriz, se devuelve -1, lo que significa que no se buscará la matriz. Si el valor de índice proporcionado es un número negativo, se toma como el desplazamiento desde el final de la matriz. Nota: si el índice proporcionado es negativo, la matriz aún se busca de adelante hacia atrás . Si el índice calculado es menor que 0, se buscará toda la matriz .

En caso de que se lo pregunte, así es como WebKit lo implementa :

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

Answer 3

Sin garantías sobre la naturaleza o el orden de los elementos en una matriz, no puede hacerlo mejor que O (n), por lo que pasaría por la matriz. Incluso si se trataba de paralelizar la búsqueda real en las CPU (no tengo idea si Firefox o Chrome hacen esto, pero podrían hacerlo), no cambia la complejidad del tiempo con un número finito de CPU.