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

Проводит ли indexOf через массив или делает что-то быстрее? Я знаю, что это зависит от реализации, но что делает Chrome или Firefox?Какова временная сложность массива javascript array.indexOf?

источник

2013-10-10 user1056805

Вы, вероятно, следует перейти к списку рассылки для разработчиков реализаций, вы заботитесь о и спросить там. Поскольку ECMAScript является Java-подобным, я ожидаю, что разработчики будут использовать базовые методы, основанные на платформе, где это возможно, поскольку большинство из них уже имеют оптимизированные функции для этого. Но это всего лишь предположение. – RobG

Исправление Firefox можно увидеть здесь (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects% 2FArray% 2FindexOf). @GameAlchemist Пожалуйста, контролируйте свое разочарование и направляйте его на кнопки, такие как кнопка «закрыть» на SO ... – loxxy

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

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

[...]

fromIndex

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

В случае, если вам интересно, here's how WebKit implements it:

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

источник

2013-10-10 04:40:19

спасибо, поэтому, если я знаю, что массив, с которым я работаю, отсортирован, я лучше использую собственную реализацию бинарного поиска, поскольку у нее есть более сложная задача «O (log (N))»? –

@Maximus Это зависит от размера вашего массива, но если он достаточно большой, чтобы это было важно, то стоит попробовать. Я бы поставил перед собой задачу, чтобы убедиться, что вы не делаете это медленнее, заменив встроенную (C++) функцию на функцию JavaScript, хотя (для небольшого 'N', менее эффективный алгоритм в C++, вероятно, побьет более эффективный алгоритм в JavaScript). –

Я понимаю, большое спасибо за ваш ответ. –

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

источник

2013-10-10 04:38:34 triggerNZ

JS-массивы не являются регулярными массивами, как следует из названия, но на самом деле хэш-карты. Можно было бы просто создать второй индекс для значений в дополнение к ключам, тем самым обеспечив лучшую временную сложность при поиске значений в обмен на использование памяти. –

@Casey Стоит отметить, что JS массивы _are_ JS объекты - просто с целыми ключами и некоторыми дополнительными методами. В [Документах Mozilla Array] (https: //developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array # Description): «Массивы - это объекты типа списка, у прототипа которых есть методы для выполнения операций обхода и мутации». Вы можете сами убедиться, что массивы используют пары ключ/значение, запустив 'Object.keys (['a', 'b']);' и 'Object.values (['a', 'b']);'. –

@PeterHenry Да, вы правы. – Casey

В ECMA6, у вас есть множество(), а затем вы можете сделать:

уаг OBJ = новый набор();

obj.add (1);

obj.has (1) == true;

obj.has (2) == false;

Я не знаю, о производительности, но более разборчивыми

источник

2018-01-18 19:38:21

'has()' должен определенно быть быстрее, чем 'indexOf()', но мы не уверены, что порядок элементов не отличается от исходного автора сообщения ... –

Да, у него мало информации, но я просто хочу показать еще одну возможность! Спасибо –

Это O (n). –

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

ответ

Смежные вопросы