JavaScript: How to efficiently retrieve array object item to a certain property?

user_1454083 0
Viewed 79

Given this array object:

[{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 efficiently retrieve the corresponding startDate to a certain eventTitle without looping/searching through the array? For example, I have Event title 2 and want to get Tue Mar 19 00:00:00 GMT+01:00 2019.

EDIT:

The array object is sorted by startDate.

object arrays javascript
3 Answers

You can apply a binary search on your array. Provided your array is sorted. -> O(log(n))

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

test the object in the middle (obj50), then decide if you have to search in the half [obj1...obj49] or in the half [obj51...obj100]


Otherwise you can pass your objects (Events) into an other data structure like a tree. -> O(log(n)) Just looping through your whole array wouldn't be efficient, but if you don't repeat it with too many its would be fine as well. But sorting your array from the beginning would be the best solution.

Edit: The following code shows a basic example of an binary search implementation.

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

user_41566330

If you only have the array, you have no option but to search through it.

But if you're going to have to search it more than once, you can make a single pass through it to produce a Map, so that subsequent searches are sublinear (faster than searching through the array with a loop). You'd do that like this:

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

Then getting by title is:

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

Live Example:

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

(You can do the same thing with an object instead of a Map (just be sure to create it with Object.create(null) so it doesn't have a prototype), but Map is specifically designed for this.)

Note that this example assumes there's only one event for each title. If there may be more than one, you need to build the map differently so that it points you to an array of only entries for that title.

user_1572470

You can create mapper util. First, it will loop once, O(n). Later all call will be O(1)

I have working code:

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

user_15943590
Related