Javascript-优化算法(复杂数据结构)

Question

简介

我正在实现一种方法，该方法将帖子插入到我的地图中的各个用户帖子列表中，按日期排序(首先是最近的帖子)。

这就是我构建数据的方式：

state = { 
userId: {
posts: [
{ // object returned from my feeds algorithm in the server side
id,
userData: {
id,
},
date,
},
... more posts ...
],
},
... more users ...
}

在我的算法中，我只需要插入给定列表中的所有帖子

[
{ id: "post1", { userData: { id: "alex" }, date },
{ id: "post2", { userData: { id: "sara" }, date }
]

在每个相应用户的帖子列表中。

问题

我还需要避免插入我所在州已经存在的帖子，而且我找不到一个简单的方法来优化它。

当前代码

这是我目前的实现方式。我觉得这可以做得更容易、更快。有什么帮助吗？

/*
Algorithm
*/
function addContents(state, contents, contentType, cached) {
const newState = state;
contents.forEach((content) => {
const { userData: { id: userId } } = content;
const prevUserState = state.get(userId);
const prevContents = prevUserState?.[contentType] ?? [];
const newContents = prevContents;
// TODO - Avoid inserting if already exists in prevContents! (check by **id**)
let inserted = false;
for (const [index, prevContent] of prevContents.entries()) {
// Replace
if (content.id === prevContent.id) {
newContents[index] = content;
inserted = true;
break;
}
// Insert in the correct order
if(content.date >= prevContent.date) {
newContents.splice(index, 0, content);
inserted = true;
break;
}
}
if (!inserted) {
newContents.push(content);
}
newState.set([
userId,
{
...prevUserState,
[contentType]: newContents
}
]);
});
// if(isEqual(state, newState)) return state; (deep compare to avoid re-renderizations because of state update)
return new Map([...newState]);
}


/*
Test
*/

(() => {
// State
const state = new Map([]);

// User ALEX
const userId1 = "alex";
const userPosts1 = [ // already sorted by date
{
id: "78q78w0w0",
userData: {
id: userId1,
},
date: new Date("10/26/1999 00:00:01")
},
{
id: "92uwdq092",
userData: {
id: userId1,
},
date: new Date("10/26/1999 00:00:00")
}
];
state.set(userId1, { posts: userPosts1 });

// User SARA
const userId2 = "sara";
const userPosts2 = [ // already sorted by date
{
id: "iipzxx115",
userData: {
id: userId2,
},
date: new Date("12/25/2003 03:30:10")
},
{
id: "Wxrr22232",
userData: {
id: userId2,
},
date: new Date("01/01/2000 17:44:41")
}
];
state.set(userId2, { posts: userPosts2 });


const newPosts = [
{
id: "OLDEST FOR ALEX!",
userData: {
id: userId1
},
date: new Date("10/25/1999 23:59:59")
},
{
id: "NEWEST FOR SARA!",
userData: {
id: userId2
},
date: new Date("01/05/2010 22:22:22")
},
{
id: "OLDEST FOR SARA!",
userData: {
id: userId2
},
date: new Date("10/25/1999 23:59:59")
}
]
addContents(state, newPosts, "posts");
console.log(state.get(userId1))
console.log(state.get(userId2))
})();

注意：由于此方法是在React的reducer中实现的，为了管理复杂的状态，在深入比较以前的状态和新的状态后，我将返回一个新的Map，以生成UI重新渲染。

更新

我已经实现了另一个版本，我可以做我需要的事情，但也许，它可以更优化。

function addContents(state, contents, contentType, cached) {
const newState = state;
const exists = {}; // optimization
for (const content of contents) {
const {
userData: { id: userId },
} = content;
const prevUserState = state.get(userId);
const prevContents = prevUserState?.[contentType] ?? [];
const newContents = prevContents;
if (cached) {
if (!exists[userId]) {
exists[userId] = prevContents.reduce((map, content) => {
map[content.id] = true;
return map;
}, {});
}
// Avoid inserting if necessary
if (exists[userId][content.id]) {
break;
}
}
// Insert the new content in the user's content list
console.log(`Inserting ${content.id}`);
let inserted = false;
for (const [index, prevContent] of prevContents.entries()) {
// Replace
if (content.id === prevContent.id) {
newContents[index] = content;
inserted = true;
break;
}
// Insert in the correct order
if(content.date >= prevContent.date) {
newContents.splice(index, 0, content);
inserted = true;
break;
}
}
if (!inserted) {
newContents.push(content);
}
newState.set([
userId,
{
...prevUserState,
[contentType]: newContents
}
]);
}
// if (isEqual(state, newState)) return state;
return new Map([...newState]);
}
/*
Test
*/

(() => {
// State
let state = new Map([]);

// User ALEX
const userId1 = "alex";
const userPosts1 = [ // already sorted by date
{
id: "78q78w0w0",
userData: {
id: userId1,
},
date: new Date("10/26/1999 00:00:01")
},
{
id: "92uwdq092",
userData: {
id: userId1,
},
date: new Date("10/26/1999 00:00:00")
}
];
state.set(userId1, { posts: userPosts1 });

// User SARA
const userId2 = "sara";
const userPosts2 = [ // already sorted by date
{
id: "iipzxx115",
userData: {
id: userId2,
},
date: new Date("12/25/2003 03:30:10")
},
{
id: "Wxrr22232",
userData: {
id: userId2,
},
date: new Date("01/01/2000 17:44:41")
}
];
state.set(userId2, { posts: userPosts2 });


const newPosts = [
{
id: "OLDEST FOR ALEX!",
userData: {
id: userId1
},
date: new Date("10/25/1999 23:59:59")
},
{
id: "NEWEST FOR SARA!",
userData: {
id: userId2
},
date: new Date("01/05/2010 22:22:22")
},
{
id: "OLDEST FOR SARA!",
userData: {
id: userId2
},
date: new Date("10/25/1999 23:59:59")
}
]
state = addContents(state, newPosts, "posts");
console.log(state.get(userId1))
console.log(state.get(userId2))

/*
Insert again!
*/
state = addContents(state, newPosts, "posts", true);
})();

Answer 1

使用对象而不是数组：这与redux的normalizr库的概念相同：https://github.com/paularmstrong/normalizr

state = { 
[user1Id]: {
posts: {
[post1Id]: { 
id,
userData: {
id,
},
date,
},
[post2Id]: { 
id,
userData: {
id,
},
date,
},
... more posts ...
},
},
... more users ...
}

通过这种方式，您可以通过其Id轻松访问所需对象，并检查其是否存在，只需执行以下操作：if(state[23].posts[12])如果您需要迭代用户或用户帖子，请使用

object.keys(state).map(userId => ...)

或

object.keys(state[23].posts).map(postId => ...)

插入/更新：

state[23].posts[newId]: { ...newPost}

Answer 2

我不能理解你在做什么，但我认为这就是你想要的。你可以很容易地做到这一点。

newdata = [{ id: "post1", { userData: { id: "alex" }, date }]
if(!oldstates.find(d => 
d.id === newdata.id && 
d.userData.id === newdata.userData.id && 
d.date === newdata.date 
)) {
oldstates.push(newdata)
}
// oneliner
if(!oldstates.find(d => d.id === newdata.id && d.userData.id === newdata.userData.id && d.date === newdata.date )) oldstates.push(newdata)