昨晚我在群里装X,说“设计推特这种题,跟写个朋友圈差不多”,结果同事直接甩我一脸:你别吹了,能把时间线刷对再说……我就硬着头皮开搞。这个题吧,核心就四个动作:发推、关注、取首页、取关。听着很产品,写着很算法,气人。
我当时一开始想用“把所有推都丢一个大数组,然后每次取最新10条”,嗯……你推特要是只有我妈一个用户那确实行。现实是用户多了以后,getNewsFeed 不能每次全量扫,扫一次你机器就跟我周一早高峰一样喘。
所以套路是:每个用户自己存自己的推文列表,按时间顺序 append。再存一个关注集合 followees[user]。取首页的时候呢,把“我关注的人 + 我自己”的最后一条推先塞进一个最大堆(按时间戳排),每次弹出最新那条,顺手把这个人的上一条推再塞回堆里,就像多路归并那种感觉,直到拿够10条或者堆空。这个思路就很像你刷外卖订单:永远先看最新的那份,懒得翻历史对吧。
代码我用 JS 写个核心版,堆我自己撸一个,别嫌丑,能跑就行:
classMaxHeap{constructor(cmp) { this.a = []; this.cmp = cmp; } push(x) { this.a.push(x); this._up(this.a.length - 1); } pop() {if (this.a.length === 0) returnnull;const top = this.a[0];const last = this.a.pop();if (this.a.length) { this.a[0] = last; this._down(0); }return top; } _up(i) {while (i > 0) {const p = (i - 1) >> 1;if (this.cmp(this.a[i], this.a[p]) <= 0) break; [this.a[i], this.a[p]] = [this.a[p], this.a[i]]; i = p; } } _down(i) {const n = this.a.length;while (true) {let b = i, l = i * 2 + 1, r = l + 1;if (l < n && this.cmp(this.a[l], this.a[b]) > 0) b = l;if (r < n && this.cmp(this.a[r], this.a[b]) > 0) b = r;if (b === i) break; [this.a[i], this.a[b]] = [this.a[b], this.a[i]]; i = b; } }get size() { returnthis.a.length; }}classTwitter{constructor() {this.time = 0;this.tweets = newMap(); // userId -> [[t, tweetId], ...]this.followees = newMap(); // userId -> Set(userId) } _getSet(userId) {if (!this.followees.has(userId)) this.followees.set(userId, newSet());returnthis.followees.get(userId); } postTweet(userId, tweetId) {if (!this.tweets.has(userId)) this.tweets.set(userId, []);this.tweets.get(userId).push([++this.time, tweetId]); } follow(followerId, followeeId) {if (followerId === followeeId) return;this._getSet(followerId).add(followeeId); } unfollow(followerId, followeeId) {this._getSet(followerId).delete(followeeId); } getNewsFeed(userId) {const users = newSet(this._getSet(userId)); users.add(userId);const heap = new MaxHeap((x, y) => x.time - y.time);for (const u of users) {const arr = this.tweets.get(u);if (arr && arr.length) {const idx = arr.length - 1; heap.push({ time: arr[idx][0], tweetId: arr[idx][1], u, idx }); } }const res = [];while (heap.size && res.length < 10) {const cur = heap.pop(); res.push(cur.tweetId);const arr = this.tweets.get(cur.u);const ni = cur.idx - 1;if (ni >= 0) heap.push({ time: arr[ni][0], tweetId: arr[ni][1], u: cur.u, idx: ni }); }return res; }}
你看写完其实挺像生活:每个人只管自己发的东西(本地列表),关注关系就是通讯录(Set),首页是“把你关心的几个人的最新动态拎出来比一比”。复杂度也舒服:发推 O(1),关注取关 O(1),拉首页大概是 O((关注人数) + 10log(关注人数)),反正就取10条,堆也不会爆。
行了我先去喝口水,刚写到这我才发现我自己都没发过推特……就离谱。