Estoy desarrollando un sistema de chat en el que todos los mensajes se almacenan en una base de datos Mongodb con el siguiente esquema:
const messageSchema = new mongoose.Schema({ to: String, from: String, threadTopic: String, messages: [ { content: String, date: Date, } ] })En este sistema de chat hay "hilos" o temas que tienen un subconjunto de mensajes. Por ejemplo, dos personas podrían tener una conversación en un hilo, y esas mismas dos personas también podrían tener una conversación en un hilo diferente, por lo que estoy tratando de filtrar la salida de la base de datos para que incluya todos los mensajes separados por hilo.
Estoy usando el siguiente algoritmo para lograr esto:
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, ie 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); } } }En esencia, este algoritmo toma una respuesta de matriz que contiene diferentes subprocesos que aparecen dos veces en la matriz (cada vez con from:/to: invertido, es decir, enviar o recibir), y consolida todas las matrices de [mensajes] que pertenecen a cada subproceso. . ¿Hay alguna forma de mejorar este algoritmo para que funcione mejor que O(n^2)?
Suponiendo que su código actual le brinde el resultado que desea, puede mejorar el tiempo de ejecución agrupando primero por threadTopic , pero aún tendrá complejidad cuadrática en el peor de los casos (si todos los elementos de respuesta tienen el mismo threadTopic ). El siguiente enfoque es mucho mejor si es poco probable que varios elementos tengan el mismo threadTopic , más cerca de 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) }); } } } (Fundamentalmente, dado que para cada hilo, está asignando cada respuesta a cada respuesta, no puede pasar O(n ^ 2) allí)