<div style="color:#16b0ff;font-size:50px;font-weight: 900;text-shadow: 5px 5px 10px var(--theme-color);font-family: 'Comic Sans MS';">Open</div> <span style="color:#16b0ff;font-size:20px;font-weight: 900;font-family: 'Comic Sans MS';">Introduction</span>:收纳开放性设计问题相关的知识总结! [TOC] # 开放性设计 ## 求两个文件中的QQ交集 **问题**:A文件有30亿个QQ号码,B文件有40亿个QQ号码,求A文件和B文件中QQ号码的交集,内存大小限制为1GB。 ### 方案一:直接暴力比较 最简单的方法是直接暴力比较:双重循环比较。显然,这种方法要比较的次数是:30亿×40亿,时间复杂度太大。 ### 方案二:利用hashmap 将B文件中的40亿个QQ号码放入Hash表中,然后遍历B文件中的30亿个QQ号码,准一判断是否已在Hash表中存在。 显然,应该用哈希表优化查找速度,使得时间复杂度大大降低,只需要遍历上面一层即可。然而,空间的占用还是太大了,1GB的内存根本无法容纳40亿个QQ号。 ### 方案三:分治切割文件 既然内存容纳不下,那就想办法进行切割,比如:根据QQ号码的最后一位的值来切割A文件和B文件,使文件变小。显然,尾数为j的QQ号码只可能在Aj文件和Bj文件中,只需要比较Aj和Bj文件即可。 | QQ号最后一位 | A文件的切割 | B文件的切割 | | ------------ | ----------- | ----------- | | 0 | A0 | B0 | | 1 | A1 | B1 | | 2 | A2 | B2 | | 3 | A3 | B3 | | ... | ... | ... | 通过切割的方法,可以化大为小,让内存容纳得下。需要强调的是,仅仅以QQ号最后一位来划分,那么每个小文件的数据量大约是原来文件的1/10, 可能还是偏大。所以可以考虑以QQ号的最后3位来划分,那么每个小文件的数据量大约是原来大文件的1/1000,甚至还可以更细地来进行划分。通过一定的规则进行分割,把A文件和B文件中同类型数据划分到对应的小文件中,解决了内存问题。 ### 方案四:利用bitmap 可以对hashmap进行优化,采用bitmap这种数据结构,可以顺利地同时解决时间问题和空间问题。 | bit | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | | ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | index | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1个unsigned char类型的数据,可以标识0~7这8个整数的存在与否。以此类推: - 1个unsigned int类型数据可以标识0~31这32(2^5)个整数的存在与否 - 2个unsigned int类型数据可以标识0~63这64(2^6)个整数的存在与否 - 3个unsigned int类型数据可以标识0~127这128(2^7)个整数的存在与否 - 4个unsigned int类型数据可以标识0~255这256(2^8)个整数的存在与否 - ...... - 28个unsigned int类型数据可以标识0~2^32-1这43亿(2^32)个整数的存在与否 10位QQ号码的理论最大值为 2^32 - 1 ≈ 43 亿bit。 占用内存:43亿bit≈5.37亿bytes≈52万KB≈512MB 显然,可以推导出:512MB大小足够标识所有QQ号码的存在与否,请注意:QQ号码的理论最大值为2^32 - 1,大概是43亿左右。接下来的问题就很简单了: 用512MB的unsigned int数组来记录B文件中QQ号码的存在与否,形成一个bitmap。然后遍历A文件中的QQ,看是否在bitmap中,如果在,那么该QQ号码就同时存在于A和B两个文件中。 https://mp.weixin.qq.com/s/Q_EvlN9LvkdA5M5EharBBA ## 40亿个QQ号码如何去重 文件中有40亿个QQ号码,请设计算法对QQ号码去重,相同的QQ号码仅保留一个,内存限制1G。 https://mp.weixin.qq.com/s/YlLYDzncB6tqbffrg__13w ### 方法一:排序 ### 方法二:hashmap ### 方法三:文件切割 ### 方法四:bitmap ## 群聊消息已读未读功能设计 企业IM比如企业微信、钉钉里面的群消息的有个已读未读的功能,发送者刚发出消息时,当前群里其他群成员都是未读状态,陆陆续续有人看了这个消息,这时候消息的详情变成x人已读,y人未读。每条消息对应一个唯一的`messageid(uint64_t)`,每个用户对应一个唯一的`userid(uint64_t)`,应该如何保存这个消息对应的已读未读详情呢? ### 简单粗暴方案 对于每一个messageid,存当前`read_ids + unread_ids`,当群成员A已读某一条消息时,把A的userid从unread_ids移除写到read_ids上就好了,客户端更新到messageid对应的详情列表,就可以展示m人已读,n人未读。 按照目前的设计,每一条消息已读未读详情就要占用8B × 群成员数的内存,如果一个活跃的200人大群,每发一条消息,已读未读就要1600B,如果平均每天消息量是1k,那每个这样的群,每天就要1.6MB磁盘空间,对于客户端来说,特别是手机端,占用磁盘空间是用户不能接受的,又不能把工作消息删了,对于服务器端来说,用户群体如果特别大,那数据库存储这个成本也不小。 ### bitmap方案 ## 未支付订单超时关闭