Задать вопрос
AlexFreem
@AlexFreem
addicted
javascript

Как найти объект в массиве по свойству?

Дан массив объектов. Необходимо найти индекс объекта в массиве по значению свойства. За условие берем что для каждого объекта свойство уникально.

var searchId = 5;
var arr = [{  id : 1 },{ id : 7 },{ id : 5 }];


Как тут получить индекс 3?

Предвидя решения с циклом for ( и соответственно другие переборы ) хотелось узнать насколько производителен этот метод при больших массивах ( 100k+ элементов ).
Ну и само собой есть ли другие варианты поиска и насколько они производительнее?
  • Вопрос задан
  • 15661 просмотр
Комментировать
Подписаться 4 Оценить Комментировать
Решения вопроса 1
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Вопервых индес будет 2 а не 3
Во вторых так как данные у вас не отсортированы, сложность алгоритма поиска в любом случае будет O(N).
В третьих если бы данные были отсортированы по этому ключу, можно было бы применить бинарный поиск у которого сложность будет O(1 +logN). Есть еще интерполяционный поиск со сложностью O(log(log(N)) но опять же работает только с отсортированными массивами.
Ну и последнее, 100К+ элементов это не так много.

Все три метода: jsfiddle.net/op1jxpsm/2 на массиве из 10 000 000 элементов
Результаты:

Хороший для тупого перебора случай, ищем 12415
Basic search: average=0ms, min = 0ms, max = 2ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms

Средний для перебора случай, ищем 3451524:
Basic search: average=64ms, min = 62ms, max = 67ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms

Плохой для перебора случай, ищем 9542417:
Basic search: average=176ms, min = 158ms, max = 182ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms
Ответ написан
Комментировать
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
JavaScript разработчик
SummerWeb • Ярославль
от 100 000 до 140 000 ₽
JavaScript разработчик
вАйТи
от 5 000 до 25 000 ₽
JavaScript Fullstack
OnClass
от 200 000 до 600 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Разработать дизайн продающего лендинга
25 апр. 2024, в 14:21
15000 руб./за проект
Шаблон WP - настройка
25 апр. 2024, в 14:07
20000 руб./за проект
Разработать ER-модель и модель процессов
25 апр. 2024, в 14:06
2500 руб./за проект
Ещё заказы