Как реализовать быстрый поиск в массиве объектов по значению свойства?

Допустим есть массив объектов:
var myArray = [
	{id: 1, name: 'Вася', age: 21, city: 'Москва'},
	{id: 2, name: 'Коля', age: 22, city: 'Новгород'},
	{id: 3, name: 'Петя', age: 23, city: 'Челябинск'},
	{id: 4, name: 'Саша', age: 24, city: 'Омск'},
];

Допустим, мне требуется найти всех людей живущих в Омске.
Я пробовал делать обычными перебором, методом Find и where в underscore. Все эти способы работают слишком долго. нужен более быстрый способ т.к. объектов в массиве будет более миллиона, кроме того после поиска идёт ещё обработка данных, которая тоже занимает время, но дольше всего работает именно поиск.
Структуру массива и объектов менять, к сожалению, не имею возможности.
Подскажите варианты решения проблемы.
  • Вопрос задан
  • 11725 просмотров
Пригласить эксперта
Ответы на вопрос 9
27cm
@27cm
TODO: Написать статус
Проиндексируйте значения для двоичного поиска. Создайте отдельный массив, в котором храните отсортированные значения city и номер объекта в исходном массиве.
Ответ написан
iCoderXXI
@iCoderXXI
React.JS/FrontEnd engineer
Обходить миллионные массивы при каждом чихе - это жесть.

Необходима индексация!

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

Если исходный массив постоянно меняется, то в прототип необходимо добавить функцию, которая будет отслеживать эти изменения и обновлять индекс.
Ответ написан
SynCap
@SynCap
Делаю интернет с 1998 года
Не сваливать все в объект, а сразу писать в IndexedDB, а необходимые для оперативной обработки данные, например выборку по городу, брать средствами работы с IndexedDB.

Для браузеров не умеющих работать с IndexedDB есть библиотека PouchDB, менее шустрая, чем нативные встроенные в браузер реализации (UPD: если их нет, в противном случае - используются нативные), но даже на старых браузерах (IE7,8) будет выигрыш, как по удобству манипуляции данными, так и по скорости.

UPD: обращение к IndexedDB НЕ блокирует интерфейс и может использоваться в воркерах (см. issues на странице).

UPD: кстати, PouchDB :
  • сам использует IndexedDB, когда она доступна, в старых WebKit, в т.ч. на Android использует WebSQL, когда совсем плохо (старые IE) - тоже чего-нибудь придумывает, как минимум - localStorage;
  • дает возможность работать с серверными данными, как c локальными, когда они доступны, идеальное решение для снижения заморочек с созданием "оффлайн" приложения или одностраничника с "миллионом записей", проводя "репликацию";
  • все танцы с бубном вокруг индексов - фоновая, абсолютно прозрачная задача.
  • если поставить на сервере CouchDB или эмулировать ее Rest api - можно забирать всех "Вась из Омска" прямо с сервера одним вызовом
UPD: И когда, наконец, народ научиться подбирать подходящий инструмент для работы, а не валить лес пилкой для ногтей и не вскапывать грядки карьерным самосвалом?
Ответ написан
Tpona
@Tpona
Ужасный перфекционист
1) Попробуйте функцию Array.filter
2) Попробуйте индекс по полю сделать, например, на основе хешей.
3) Попробуйте использовать indexeddb или websql
Ответ написан
DIITHiTech
@DIITHiTech
Fullstack javascript developer
Это какая то шутка?) Имхо 1М записей держать на клиенте и по ним еще искать это тупо, причем очень и властелин должен за такое наказывать.
Если не устраивают индексирование в массиве, webworker'ы не дают прироста, то больше тут ничего особо не сделаешь- клиентские девайсы не резиновые . Это задача сервера, а не клиента.
берете вебсокеты, вместо ajax, если хотите сэкономить мс, разумеется node, redis/mongo+кастомный клиентский кэш и вперед. в 100-200мс думаю вложитесь, это можно считать мгновенно. Что мешает этому?
Ответ написан
AndreyChursin
@AndreyChursin
Не многословен
Я не понимаю чем *sql не подходит?
Миллион объектов, js, серьёзно?

Индексация конечно поможет, но это костыль ИМХО!
Ответ написан
@cane
var myArray = [
	  {id: 1, name: 'Вася', age: 21, city: 'Москва'},
	  {id: 2, name: 'Коля', age: 22, city: 'Новгород'},
	  {id: 3, name: 'Петя', age: 23, city: 'Челябинск'},
	  {id: 4, name: 'Саша', age: 24, city: 'Омск'},
	  {id: 5, name: 'Ваня', age: 99, city: 'Омск'}
	];
	
	function filterByCity(arr, city) {
		return arr.filter(function(item, i, arr) {
			  return (item.city == city);
		});
	};

	var omsk = filterByCity(myArray, 'Омск');

	console.log(omsk);


Может через фильтр массива с замыканием?
Ответ написан
salkat
@salkat
Бизнесмен. Создаём контакт-центры
А если хранить всё во внутреннем Storage и пользоваться его средствами?

https://developer.mozilla.org/ru/docs/Web/API/Storage
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
Artezio Нижний Новгород
от 130 000 до 180 000 ₽
Artezio Москва
от 160 000 до 220 000 ₽
Artezio Могилев
от 2 800 до 3 300 $