JavaScript: Как эффективно получить элемент объекта массива для определенного свойства?

Question

Для данного объекта массива:

[{eventTitle=Event title 1, eventId=xyz1@google.com, startDate=Sun Mar 18 00:00:00 GMT+01:00 2018, endDate=Mon Mar 19 00:00:00 GMT+01:00 2018},
 {eventTitle=Event title 2, eventId=xyz2@google.com, startDate=Tue Mar 19 00:00:00 GMT+01:00 2019, endDate=Wed Mar 20 00:00:00 GMT+01:00 2019},
 {eventTitle=Event title 3, eventId=xyz3@google.com, startDate=Fri Mar 20 00:00:00 GMT+01:00 2020, endDate=Sat Mar 21 00:00:00 GMT+01:00 2020},
 .
 .
 .]

Как эффективно извлечь соответствующий startDate в определенный eventTitle без циклического поиска / поиска в массиве? Например, у меня есть Event title 2 и я хочу получить Tue Mar 19 00:00:00 GMT+01:00 2019.

РЕДАКТИРОВАТЬ:

Объект массива отсортирован по startDate.

Answer 1

Вы можете применить бинарный поиск к вашему массиву. При условии, что ваш массив отсортирован. -> O(log(n))

[obj1,obj2,obj3....obj100]

проверить объект в середине (obj50), а затем решить, нужно ли искать в половине [obj1...obj49] или в половине [obj51...obj100]


В противном случае вы можете передавать свои объекты (события) в другую структуру данных, например, в дерево. -> O(log(n)) Простой цикл по всему массиву будет неэффективным, но если вы не будете повторять его со слишком большим количеством, это также подойдет. Но лучшим вариантом будет сортировка массива с самого начала.

Редактировать: в следующем коде показан базовый c пример реализации двоичного поиска.

const events = [{
    eventTitle: "Event title 1",
    eventId: "xyz1@google.com",
    startDate: "Sun Mar 18 00:00:00 GMT+01:00 2018",
    endDate: "Mon Mar 19 00:00:00 GMT+01:00 2018"
  },
  {
    eventTitle: "Event title 2",
    eventId: "xyz2@google.com",
    startDate: "Tue Mar 19 00:00:00 GMT+01:00 2019",
    endDate: "Wed Mar 20 00:00:00 GMT+01:00 2019"
  },
  {
    eventTitle: "Event title 3",
    eventId: "xyz3@google.com",
    startDate: "Fri Mar 20 00:00:00 GMT+01:00 2020",
    endDate: "Sat Mar 21 00:00:00 GMT+01:00 2020"
  },
  {
    eventTitle: "Event title 4",
    eventId: "xyz4@google.com",
    startDate: "Fri Mar 21 00:00:00 GMT+01:00 2021",
    endDate: "Sat Mar 22 00:00:00 GMT+01:00 2021"
  },
  {
    eventTitle: "Event title 5",
    eventId: "xyz5@google.com",
    startDate: "Fri Mar 22 00:00:00 GMT+01:00 2022",
    endDate: "Sat Mar 23 00:00:00 GMT+01:00 2022"
  }
];

function binarySearch(array, value, borderLeft, borderRight) {
  if (borderLeft <= borderRight) {
    var index = Math.floor((borderLeft + borderRight) / 2);
    var number = getNumberFromTitle(array[index].eventTitle);
    if (number == value) {
      return array[index].startDate;
    } else if (number > value) {
      return binarySearch(array, value, borderLeft, index - 1);
    } else {
      return binarySearch(array, value, index + 1, borderRight);
    }
  } else {
    return null;
  }
}

function getNumberFromTitle(title) {
  var tmp = title.split(" ");
  return tmp[tmp.length - 1];
}

console.log(binarySearch(events, 4, 0, events.length - 1));

Answer 2

Вы можете создать утилиту Mapper. Во-первых, один раз l oop, O(n). Позже все звонки будут O(1)

У меня есть рабочий код:

https://gist.github.com/deepakshrma/4b6a0a31b4582d6418ec4f76b7439781

function Mapper(array , key){
    this.map = array.reduce(function(map, item){
        var val = item[key];
        if(!map[val]){
            map[val] = [];
        }
        map[val].push(item);
        return map;
    },{});
}
Mapper.FIRST_INDEX = 0;
Mapper.prototype.find = function find(key){
    return this.map[key] && this.map[key][Mapper.FIRST_INDEX]//return blank array
};
Mapper.prototype.findAll = function find(key, returnUndefined){
    return this.map[key] && this.map[key] || (returnUndefined? undefined: []);//return blank array
};
var users = [{eventTitle:"Event title 1", eventId:"xyz1@google.com", startDate:"Sun Mar 18 00:00:00 GMT+01:00 2018", endDate:"Mon Mar 19 00:00:00 GMT+01:00 2018"},
 {eventTitle:"Event title 2", eventId:"xyz2@google.com", startDate:"Tue Mar 19 00:00:00 GMT+01:00 2019", endDate:"Wed Mar 20 00:00:00 GMT+01:00 2019"},
 {eventTitle:"Event title 3", eventId:"xyz3@google.com", startDate:"Fri Mar 20 00:00:00 GMT+01:00 2020", endDate:"Sat Mar 21 00:00:00 GMT+01:00 2020"}];
//How to use

var userMapper = new Mapper(users , 'eventTitle');
console.log(userMapper.find("Event title 2")); 
var userToFind = ["Event title 3", "Event title 2"];
var reqUsers =  userToFind.map(function(name){
    return userMapper.find(name);
});
console.log(reqUsers);

Answer 3

Если у вас только есть массив, у вас нет выбора, кроме как искать его.

Но если вам придется искать его несколько раз, вы можете сделать один проход через него для создания карты, так что последующие поиски являются сублинейными (быстрее, чем поиск по массиву с al oop). Вы сделаете это так:

const map = new Map(theArray.map(entry => [entry.eventTitle, entry.startDate]));

Тогда по названию получите:

const startDate = map.get("some title");

Live Пример:

const theArray = [
    {eventTitle: "Event title 1", eventId: "xyz1@google.com", startDate: "Sun Mar 18 00:00:00 GMT+01:00 2018", endDate: "Mon Mar 19 00:00:00 GMT+01:00 2018"},
    {eventTitle: "Event title 2", eventId: "xyz2@google.com", startDate: "Tue Mar 19 00:00:00 GMT+01:00 2019", endDate: "Wed Mar 20 00:00:00 GMT+01:00 2019"},
    {eventTitle: "Event title 3", eventId: "xyz3@google.com", startDate: "Fri Mar 20 00:00:00 GMT+01:00 2020", endDate: "Sat Mar 21 00:00:00 GMT+01:00 2020"},
];
// Building it:
const map = new Map(theArray.map(entry => [entry.eventTitle, entry.startDate]));
// Using it:
console.log(map.get("Event title 2"));       // "Tue Mar 19 00:00:00 GMT+01:00 2019"
console.log(map.get("Event title 3"));       // "Fri Mar 20 00:00:00 GMT+01:00 2020"
console.log(map.get("no such event title")); // undefined

.as-console-wrapper {
    max-height: 100% !important;
}

(Вы можете сделать то же самое с объектом вместо карты (просто обязательно создайте его с помощью Object.create(null), чтобы он не имел прототип), но карта специально разработана для этого.)

---

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