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

Question

[yazux]

Допустим есть массив объектов:

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. Все эти способы работают слишком долго. нужен более быстрый способ т.к. объектов в массиве будет более миллиона, кроме того после поиска идёт ещё обработка данных, которая тоже занимает время, но дольше всего работает именно поиск.
Структуру массива и объектов менять, к сожалению, не имею возможности.
Подскажите варианты решения проблемы.

Comments

[Алексей Сергей]

как-то маловато данных.
1. могут ли добавляться/удаляться элементы из массива myArray? насколько часто?
2. как много свойств у реального элемента массива myArray?
3. есть ли ограничения по RAM?

я бы смотрел в сторону построения кэш-таблиц. что-то вроде:
{
City: {
"Омск": [ {id: 4, name: Саша, age: 24, city: "Омск" } ]
........
},
Age: {
24: [ {id: 4... } ]
........
}
}

как вариант, можно просто хранить несколько массивов, отсортированных по разным критериям.

[Алексей Сергей]

ну и, наверное, native "filter", лучше результат даст чем underscore.where

array.filter(item => item.prop)

[yazux]

Алексей Сергей: Про хранение массивов и таблицы уже были идеи. Опять же, построение этого всего занимает дополнительное время. Добавляться и удаляться не могут. У реально массива до 100 записей но с очень глубокой вложенностью и массивной обработкой данных.

[Алексей Сергей]

*
array.filter(item -> item.city == "Омск")

[Алексей Сергей]

может такое попробовать прикрутить?
https://github.com/typicaljoe/taffydb

[yazux]

Алексей Сергей: Уже попробовал вот это: https://github.com/agershun/alasql, дело в том, что это поиск тоже происходит в цикле, сделал каждую итерацию для поиска через web workers, внутри него уже запрос через alasql. Ситуация улучилась, но не на столько, на сколько бы хотелось.

[Faliah]

yazux: Хотел написать, про хэши и это всё, но увидел, что были уже мысли. Если не секрет, то не могли бы вы сказать в чем собственно сложность создания дополнительных структур для работы с данными. Поиск по массиву объектов - задача очень сложно оптимизируемая, хоть вэб-воркерами, хоть чем угодно. Да, это приведёт к дополнительному расходу по памяти, но ведь вы могли бы декомпозировать данные по отдельным коллекциям и, при необходимости, собирать из них наборы какого угодно вида. Понятно, что идея капитанская, но мне не понятен этот подход с желанием оптимизировать работу с моснтр-коллекцией, всеми доступными способами, которые несут в себе кучу других проблем и поднимают сложность решения (опять же веб-воркеры), вместо использования базовых бассивов с примитивами и хэш таблиц, операции с которыми выполняются очень быстро и логика таких операций линейна

[Виктор Л]

а если сразу сгрупировать
add //cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore.js
var someArray = [
{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: 21, city: 'Омск'},
];
var groupedData = _.groupBy(someArray, function(d){return d.city});
console.log(groupedData);

Answer 1

[Котик Антон]

Проиндексируйте значения для двоичного поиска. Создайте отдельный массив, в котором храните отсортированные значения city и номер объекта в исходном массиве.

Answer 2

[Андрей]

Обходить миллионные массивы при каждом чихе - это жесть.

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

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

Если исходный массив постоянно меняется, то в прототип необходимо добавить функцию, которая будет отслеживать эти изменения и обновлять индекс.

Answer 3

[Константин]

Не сваливать все в объект, а сразу писать в IndexedDB, а необходимые для оперативной обработки данные, например выборку по городу, брать средствами работы с IndexedDB.

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

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

UPD: кстати, PouchDB :

• сам использует IndexedDB, когда она доступна, в старых WebKit, в т.ч. на Android использует WebSQL, когда совсем плохо (старые IE) - тоже чего-нибудь придумывает, как минимум - localStorage;
  
• дает возможность работать с серверными данными, как c локальными, когда они доступны, идеальное решение для снижения заморочек с созданием "оффлайн" приложения или одностраничника с "миллионом записей", проводя "репликацию";
  
• все танцы с бубном вокруг индексов - фоновая, абсолютно прозрачная задача.
  
• если поставить на сервере CouchDB или эмулировать ее Rest api - можно забирать всех "Вась из Омска" прямо с сервера одним вызовом
  

UPD: И когда, наконец, народ научиться подбирать подходящий инструмент для работы, а не валить лес пилкой для ногтей и не вскапывать грядки карьерным самосвалом?

Comments

[Григорий]

Народ учится - всё сразу знать не дано - поэтому и интересуются, спрашивают - не все иноплатеняне с рождения знающие все языки программирования, как вы.

Answer 4

[Валентин]

1) Попробуйте функцию Array.filter
2) Попробуйте индекс по полю сделать, например, на основе хешей.
3) Попробуйте использовать indexeddb или websql

Comments

[Константин]

websql - лучше не надо. Небраузякно, неэстетично, трудозатратно, неэкологично, депрекейтно и вообще некошерно: caniuse.com/#search=websql

[Константин]

Array.filter - тоже не решение: https://benchmarkjs.com/. К сожалению jsperf.com закрыт, там онлайн видно было.

[Валентин]

Странно, localStorage уделывает всухую и indexeddb и websql reyesr.github.io/html5-storage-benchmark кстати по скорости все же функция filter быстрее, чем indexeddb при поиске например по тектовому полю, но она блокирует интерфейс, а при добавлении в память большого объема информации браузер слетит на определенном объеме.

Answer 5

[Dmitriy Mozgovoy]

Это какая то шутка?) Имхо 1М записей держать на клиенте и по ним еще искать это тупо, причем очень и властелин должен за такое наказывать.
Если не устраивают индексирование в массиве, webworker'ы не дают прироста, то больше тут ничего особо не сделаешь- клиентские девайсы не резиновые . Это задача сервера, а не клиента.
берете вебсокеты, вместо ajax, если хотите сэкономить мс, разумеется node, redis/mongo+кастомный клиентский кэш и вперед. в 100-200мс думаю вложитесь, это можно считать мгновенно. Что мешает этому?

Comments

[yazux]

Проблема в том, что у меня нет доступа к бекэнду вообще. Приходят с него данные, их надо обработать. Зачем так сделано, я понятия не имею, почему заказчик не хочет напрягать своих бекэндщиков тоже не знаю. Я с вами согласен, но к сожалению, не могу решить задачу таким способом.

[Dmitriy Mozgovoy]

yazux: тогда это совсем печально, там только озу бешено выжрет... ну тогда, как сказали уже- нужен отдельный массив-индекс с ключами по городу и массивом ссылок на поля исходного. Больше тут ничего не сделаешь с адекватным приростом. Можно еще повлиять на ощущения юзера и искать не в одном полном индексе, а разбить на несколько блоков и искать асинхронно между блоками, дабы не подвисал UI. Либо попробовать синхронно, но все же разбить на несколько отдельных индексов, каждый из которых в свою очередь обслуживают только свою начальную букву или несколько букв. Думается в таком случае поиск движок быстрее будет справляться с вычислением значения объекта по ключу. Хотя это в случае если городов очень очень много будет, т.е индексов более 65535 (хотя маловероятно даже для России.) Помнится после этого значения в 2 байта длинны движок замедляется.

Answer 6

[xmoonlight]

Да, я - злой: Regex! )

Answer 7

[Andrey Chursin]

Я не понимаю чем *sql не подходит?
Миллион объектов, js, серьёзно?

Индексация конечно поможет, но это костыль ИМХО!

Answer 8

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

Может через фильтр массива с замыканием?

Comments

[Константин]

Array.filter - еще более затратная по времени и ресурсам функция, чем поиск indexOf, плюс еще ведется копирование в новый Array, а потом еще обработать как-то надо. Да он просто повеситься!

P.S. он - в данном случае и браузер, и человек ожидающий результата :)

Answer 9

[Сергей]

А если хранить всё во внутреннем Storage и пользоваться его средствами?

https://developer.mozilla.org/ru/docs/Web/API/Storage