本文例题来自355-Design Twitter

题目

355-Design Twitter

分析

本题非常贴近于程序员码代码的日常需求，剔除了与DB和其他接口的交互，所以唯一要考虑的就是不同的数据，用何种数据类型来处理。
提炼题目，发现了至少需要如下两个数据类型

• 隶属于个人的推文列表，为了方便取最新的十笔推文，使用队列DEQUE是个好办法。
• 隶属于个人分关注列表，为了剔除重复性使用集合SET

个人的解法

无

评论的力量

评论有个解法非常优秀，本分分析即源自此解法

关注列表用set实现，添加和删除都比较简单 #推文列表用list实现，时间戳+推文组成元组加入列表（初始方案，不行） 推文列表用双端队列（deque）实现，时间戳+推文组成元组加入队列头 最复杂的是获取推文，用最大堆实现十条推文的获取。hepq.merge可以多输入单输出排序，再用itertools.islice(iterable, stop) 切片。
by LJ001
python

collections.defaultdict

字典dict的子类，放到面对对象来说，即继承了字典，并实现了额外的方法——提供了一个工厂函数，为字典查询提供一个默认值。
1.何为工厂函数
这是一个面向对象编程的概念，存在的意义就是当你调用此函数时，就建立了一个对应的对象，而这个对象的形式和你的调用函数和传入值有关，工厂会根据你的调用生成指定的对象，而调用者无需去管理工厂里面用的哪些接口。详细可以看设计模式——工厂模式
2.为字典查询提供一个默认值是什么意思
简单点来说，当字典不存在此键值对时，defaultdict提供了初始化，并给予了默认值，最明显的结果如下：

#!/usr/bin/python3
> d = collections.defaultdict(list)
#defaultdict(<class 'list'>, {})
> print(d)
#[]
> print(d['JACK'])
#defaultdict(<class 'list'>, {'JACK': []})
> print(d)

不需要创建即有了键值对。用处不言而喻，跳过了可能的存在性检查，不存在即创建。一定程度上代替了如下两种方法：

dict的miss定义

dict的内置方法setdefault

同时defaultdict还给我们提供了用lambda初始化的方法

#!/usr/bin/python3
d = collections.defaultdict(lambda : '1')

heapq.merge

堆排序算法其中之一的工具

heapq.merge

解释下*，表示对iterable变量定义为可变变量

itertools.islice

itertools.islice

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tweets=collections.defaultdict(collections.deque)
        self.followlist=collections.defaultdict(set)
        self.timestamp=2**31
    def postTweet(self, userId, tweetId):
        """
        Compose a new tweet.
        :type userId: int
        :type tweetId: int
        :rtype: void
        """
        self.timestamp-=1
        self.tweets[userId].appendleft((self.timestamp,tweetId))
        

    def getNewsFeed(self, userId):
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        :type userId: int
        :rtype: List[int]
        """
        tweets = heapq.merge(*(self.tweets[u] for u in self.followlist[userId] | {userId}))
        return [t for _, t in itertools.islice(tweets, 10)]

    def follow(self, followerId, followeeId):
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.followlist[followerId].add(followeeId)
        

    def unfollow(self, followerId, followeeId):
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        :type followerId: int
        :type followeeId: int
        :rtype: void
        """
        self.followlist[followerId].discard(followeeId)