CODEWITHSUNDEEP
javascriptecmascript-6time-complexityjavascript-objects
Puneet Kushwah
Puneet Kushwah

Reputation: 1600

Fastest way to search in millions of records which is the combination of two js objects

I have millions of objects of messages

messages: [
    {
      id: Int,
      text: String,
      userId: Int,
      receiverId: Int,
    },

and thousands of users

  users: [
    {
      id: Int,
      name: String,
    },

I need to process two objects and return an object in format 

[{ message, userFromName, userToName }]

I read about array methods like find, filter, some and all of these are slower than native for and foreach.

I also wrote a function which two foreach loops

msgData.forEach(function(msg,i) {
    ...iterating every msg 
    userData.forEach(function(user) {
       ...iterating every user id over message sender and receiver id
    });
});

The complexity of the code O(n)square

How to get the required format in less amount of time?

Upvotes: 2

Views: 2832

Answers (2)

ricardoorellana
ricardoorellana

Reputation: 2340

Assuming that you will have a key in common between the two arrays, you could use a Hash Map Data Structure, in Javascript can be represented as a simple plain object, for example:

const users = [{id: 1, name: 'Marcela'}, {id:2, name: 'Ana'}];
const messages = [{id: 1, message: 'She is a great Graphic Designer'}, {id: 2, message: 'She likes watch movies'}];

// #1 convert one array to a hashmap
const userHashMap = {};

// O(N)
for (let user of users) {
  userHashMap[user.id] = user;
}

// above code will store a DS like 
// {
//     1: 
//         {
//             id: 1,
//             name: 'Marcela'
//         }, 
//     2:
//         {
//             id: 2,
//             name: 'Ana'
//         }
// }

// #2 Now you can iterate over messages in O(N)
// and we can get the values of users 
// in constant time O(1) (That's the most important use of HashMaps):

messages.forEach(message => {
  console.log(`This id message ${message.id} belongs to ${userHashMap[message.id].name}`);
  console.log(`Message for ${userHashMap[message.id].name}: ${message.message}`);
});

Remember, we reduced time complexity using a technique that has an impact in memory (object HashMap is storing data for every user so space complexity is O(N)).

Upvotes: 0

Klaycon
Klaycon

Reputation: 11080

Convert users to a dictionary for fast, non-iterative lookup:

Native Object:

let userDict = users.reduce((o,u)=> {
  o[u.id]=u.name;
  return o;
}, {});

Map:

let userDict = new Map();
userDict.forEach(u => userDict.set(u.id,u.name));

This is O(n). With this dictionary you can simplify the msgData forEach to this:

let result = msgData.map(msg => {
  return { message: msg.text, userFromName: userDict[msg.userId], userToName: userDict[msg.receiverId]};
 });

This is also O(n) as both object and Map lookups are O(1). See this question for performance details on those. Either way you go will be a significant performance improvement over your current O(n^2) solution.

Upvotes: 1

Related Questions