I'm developing a chat system in which all messages are stored in a Mongodb database with the following schema:
const messageSchema = new mongoose.Schema({
to: String,
from: String,
threadTopic: String,
messages: [
{
content: String,
date: Date,
}
]
})
In this chat system there are "threads" or topics which have a subset of messages. For example, two people could have a conversation on one thread, and those same two people could also have a conversation on a different thread, so I am trying to filter the database output so that it includes all the messages separated by thread.
I am using the following algorithm in order to accomplish this:
var finalResult = [];
for (var i = 0; i < response.length; i++) {
for (var j = i+1; j < response.length; j++) {
//Check if there is a match between 2 threadTopics so they can be sonsolidated:
if (response[i].threadTopic === response[j].threadTopic) {
//Extract received messages, i.e. messages sent to the recipient (user)
const rxMsgs = (response[i].to == "Recipient") ? response[i].messages : response[j].messages
//Extract messages that the recipient (user) sent
const txMsgs = (response[i].from = "Recipient") ? response[i].messages : response[j].messages
const element = {
threadName: response[i].threadTopic,
msgs: rxMsgs.concat(txMsgs)
}
//append to final consolidated output
finalOutput = finalOutput.concat(element);
}
}
}
In essence, this algorithm takes in an array response containing different threads that appear twice in the array (each time with the from:/to: reversed, i.e.: send or receive), and consolidates all the [messages] arrays belonging to each thread. Is there any way to improve this algorithm so that it performs better than O(n^2)?
Assuming your current code gives you the output you want - you can improve the runtime by grouping by threadTopic first, but it'll still have quadratic complexity in the worst case (if all response items have the same threadTopic). The below approach is much better if multiple items having the same threadTopic is unlikely - closer to O(n).
const responsesByTopic = {};
for (const oneResponse of response) {
responsesByTopic[oneResponse.threadTopic] ??= [];
responsesByTopic[oneResponse.threadTopic].push(oneResponse);
}
const output = [];
for (const [threadName, responses] of Object.entries(responsesByTopic)) {
for (let i = 0; i < responses.length; i++) {
for (let j = i + 1; j < responses.length; j++) {
const rxMsgs = response[response[i].to === "Recipient" ? i : j].messages;
const txMsgs = response[response[i].from === "Recipient" ? i : j].messages;
output.push({
threadName,
msgs: rxMsgs.concat(txMsgs)
});
}
}
}
(Fundamentally, since for each thread, you're mapping each response to each other response, you can't get past O(n ^ 2) there)