通行证
- 积分
- 599
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-6-9
- 最后登录
- 1970-1-1
|
内存不够的情况,一般是不建议用高级数据结构的,因为overhead太大。你想想你用trie,平均每单词花费的空间大小?你一个node就有26甚至更多个指针。这就几十byte出去了。hash稍微好点,但也是overhead太大。而你用数组存呢?一个数字一个坑,几乎没有overhead。空间利用率高很多。
面试官说不要用hashmap,我猜他的意思是内存大小对给每个unique的数字建一个key都不够。
这题如果是问我,我会这么做:利用这题关键点a sorted array。
For simplicity, 假设数组长度是100,内存长为30.
我们保留20的空间用来存数据结构,把10的空间拿出来做为buffer。一次读一buffer的数字,做处理,所以大概是这么读:
第一趟:1122334444
第二趟:4455566777
第三趟:7778888888
第四趟:999........
那保留的20存什么呢?存每一趟的起始数字和这一趟在disk上的offset
1: offset 5
4: offset30
7: offset70 ...
然后怎么query每个数字频率?
比如查6的频率,那么现在你得数据结构里二分查找6. 你会发现6在4 ~ 7之间。这样你再把4那趟的数字load到内存里(你有offset),然后再在4那趟数字:4455566777 里二分查找6的起始和结束位置,这样6的频率揪出来了。(对于跨多个block的数据,方法类似,不再赘述)
这个复杂度是log10 + log10的. 不是O(1),但足够好了。因为O(1)方案要把所有key全load进来,我默认这是无法实现的。
这题有很多可以探讨优化的地方,可以跟面试官聊。比如你的硬盘是否还有额外空间?你可以存多级表在硬盘。你硬盘里数据是否连续?那么连offset都不用存了,顺序往下读即可。。等等 |
|