r******r
发帖数: 700 | 1 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 2 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
s**********o
发帖数: 14359 | 3 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
|
f********t
发帖数: 6999 | 5 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
发帖数: 1 | 6 其实越看这东西越佩服香农，这式子什么意思呢？架设有两件事各有50%的可能发生，
那么根据这式子算出来信息熵是1bit，而现在我们很容易理解，最优的编码是用0和1各
表示一个事件。如果有四件事各有25%的发生几率，那么信息熵是2bit，我们知道这个
时候用00，01，10，11各表示一个事件就可以完全表示出这个随机事件。也就是说这个
事件的信息量是2bit。推而广之……我觉得现在这东西一点也不难理解，尤其是习惯了
数字时代和bit的我们。然而，这些都是香农定义的，那个时候可不是数字计算机的时
代。看过他的访谈就知道——图灵是天才，图灵机是天才的想法，用算法来描述所有人
类的思考行为是天才的。然而，同样的东西，也逐渐在他的美国同行，例如冯诺伊曼，
例如香农，的脑海中成型了。然而香农，用bit描述世界上所有的信息和交流，即便在
当时，当他在午餐时和图灵提起时，都被图灵认为是不切实际的。很多技术和理论都是
历史发展的产物，但信息论的提出却超出了时代——这个本来应该是在数字时代出现之
后从实践中逐渐总结出的理论，却因为香农的天才，提前了至少10年。
美国人因为香农就此在计算机领域领先10年。 |
|
l*********y
发帖数: 142 | 7 我是在看
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用 |
|
l*********y
发帖数: 142 | 8 我是在看
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用 |
|
g******g
发帖数: 289 | 9 我有一组数据，全部是2bit，从0到1.可能会有噪音，大概10%，所以需要ecc处理。希
望处理完的数据越小越好。
最早用Reed Solomon，但是2bit必须整合成12bit或者8bit。但是10%的噪音就会变成60
%或者40%，这个数据实在太大了。
如果不能用Reed Solomon，那该用什么方法？ |
|
g******g
发帖数: 289 | 10 我有一组数据，全部是2bit，从0到1.可能会有噪音，大概10%，所以需要ecc处理。希
望处理完的数据越小越好。
最早用Reed Solomon，但是2bit必须整合成12bit或者8bit。但是10%的噪音就会变成60
%或者40%，这个数据实在太大了。
如果不能用Reed Solomon，那该用什么方法？ |
|
|
D**s
发帖数: 6361 | 12 Intel创始人是摩尔定律的提出者，Intel公司也是摩尔定律最坚定的捍卫者。前几年
Intel还在自信半导体工艺领先业界三年半，谁知道14nm节点Intel遭遇了挫折。
而台积电、三星这两家在14/16nm节点之后好像开了挂，10nm工艺去年就宣传说量产了
，今年都要试产7nm了，5nm工艺也要在2020年搞定，这速度可比Intel快多了。
面对被以前的跟班轻松超越的问题，Intel也忍不住了，希望半导体公司在制程工艺描
述上诚实一点，并给出统一的衡量公式。
先说说为什么Intel要介意这个问题。放在几年前，Intel在半导体工艺上一直都是领先
台积电、三星等公司的，22nm节点就开始量产3D晶体管（也就是FinFET工艺），那时候
三星、台积电才推出28nm工艺没多久，跟Intel差距确实挺远的，Intel自然不会有什么
失落感。
但之后的情况不一样了，Intel在14nm遇到了技术问题，原计划的Fab 14工厂升级工艺
也被取消了，以致于Tick-Tock战略停摆，现在14nm工艺都要出四代产品了，这一代工
艺要用差不多4年时间。
台积电、三星的14/16nm FinFET工艺在... 阅读全帖 |
|
s*******h
发帖数: 3219 | 13 【 以下文字转载自 Midlife 讨论区 】
发信人: sammamish (sammamish), 信区: Midlife
标 题: 最近研究了一下魂斗罗的源代码。为什么魂斗罗只有128KB
发信站: BBS 未名空间站 (Sat Jun 10 12:33:34 2017, 美东)
为什么魂斗罗只有128KB却可以实现那么长的剧情？
1.游戏大量复用图块，图块还使用调色板索引，好像每个像素才占用2bit。
2.程序员精心优化各种数据结构，每一bit存储都不浪费。
3.声音只存储发声通道的调制参数序列，能复用就复用。
4.代码全是汇编写成，直接操作硬件，基本不存在浪费的指令。
个人觉得fc最神奇的游戏还属超级玛丽，32个关卡，每关都不同，各种隐藏要素，好像
代码区才10多k，数据区10多k。反汇编看完还是不敢相信这点东西能玩一个童年…现在
helloworld的二进制都可能比这大多了。 |
|
m****u
发帖数: 3915 | 14 getGrayCode(2)就是返回2bit的格雷码
也就是：{00, 01, 11, 10}
getGrayCode(3)就是
{000， 001， 011， 010, 110, 111, 101, 100} |
|
s*******e
发帖数: 93 | 15 这个idea不错，不过我感觉只要记录了每个节点的子节点类型和个数，用preorder好像
也行。有反例吗？
具体一点的话，记录每个节点的子节点类型和个数好像只要2bits就够了：
00 没有子节点
01 只有右手
10 只有左手
11 两个都有
然后比如preorder是 A B D E C F
类型是 11 11 00 00 01 00
就知道 reconstruct出来是
A
B C
D E F
谁看看这样有没有漏洞？谢谢。 |
|
g*****e
发帖数: 282 | 16 哪怕是utf7 utf8也可以，每个hash value 1byte足够（2bit已经够了）。phone
interview里碰到过，跟面试官讨论后认可 |
|
|
|
s*******h
发帖数: 3219 | 19 【 以下文字转载自 Midlife 讨论区 】
发信人: sammamish (sammamish), 信区: Midlife
标 题: 最近研究了一下魂斗罗的源代码。为什么魂斗罗只有128KB
发信站: BBS 未名空间站 (Sat Jun 10 12:33:34 2017, 美东)
为什么魂斗罗只有128KB却可以实现那么长的剧情？
1.游戏大量复用图块，图块还使用调色板索引，好像每个像素才占用2bit。
2.程序员精心优化各种数据结构，每一bit存储都不浪费。
3.声音只存储发声通道的调制参数序列，能复用就复用。
4.代码全是汇编写成，直接操作硬件，基本不存在浪费的指令。
个人觉得fc最神奇的游戏还属超级玛丽，32个关卡，每关都不同，各种隐藏要素，好像
代码区才10多k，数据区10多k。反汇编看完还是不敢相信这点东西能玩一个童年…现在
helloworld的二进制都可能比这大多了。 |
|
p**********u
发帖数: 15479 | 20 【 以下文字转载自 Military 讨论区 】
发信人: sammamish (sammamish), 信区: Military
标 题: 最近研究了一下魂斗罗的源代码。为什么魂斗罗只有128KB (转载)
发信站: BBS 未名空间站 (Sat Jun 10 12:33:51 2017, 美东)
发信人: sammamish (sammamish), 信区: Midlife
标 题: 最近研究了一下魂斗罗的源代码。为什么魂斗罗只有128KB
发信站: BBS 未名空间站 (Sat Jun 10 12:33:34 2017, 美东)
为什么魂斗罗只有128KB却可以实现那么长的剧情？
1.游戏大量复用图块，图块还使用调色板索引，好像每个像素才占用2bit。
2.程序员精心优化各种数据结构，每一bit存储都不浪费。
3.声音只存储发声通道的调制参数序列，能复用就复用。
4.代码全是汇编写成，直接操作硬件，基本不存在浪费的指令。
个人觉得fc最神奇的游戏还属超级玛丽，32个关卡，每关都不同，各种隐藏要素，好像
代码区才10多k，数据区10多k。反汇编看完还是不敢相信这点东西能玩一个童... 阅读全帖 |
|
R***a
发帖数: 41892 | 21 ISO方面我预计是目前APS-c中最强的。
A55高ISO看raw就是赶上或超过550D了。
A580多了半档光，预计超越550D没悬念。
D7000比A580多了2bit ADC，理应比A580略好 |
|
k****t
发帖数: 12697 | 22 纯瞎扯吧.
2D 上表现3D, 无外GEOMETRIC PERSPECTIVE 和ATMOSHPERIC PERSPECTIVE. GEOMETRIC
不用说了都一样. ATMOSPHERIC 也是,只要机器有灰色层次不是2BIT的非黑就白不都一
样. |
|
R***a
发帖数: 41892 | 23 这么实现需要的技术点
1. ADC需要能够预估使用多大的增益，这似乎问题不大
2. ADC可能必须是每个像素一个，而不能象别人家那样可以是一条线共用一个adc
另外还有一个问题就是，nikon/pentax使用的都是外置ADC，不同于sony
on-chip的12-bit ADC，难道sensor还能管外置ADC怎么工作的么？或者说，
N既然有了能动态gain的外置ADC，为啥不用在自家sensor上？
这个，可能这些adc都是在内置adc的基础上另加2bit的。
按照我以前看的A700的exmor cmos说明，exmor的功能是内置12 bit ADC，
可以外接一个ADC加两次读取周期，变成14 bit的，
也就是Exmor实际是14 bit capable，但是内置限制了12 bit输出而已，
这样就可以解释为啥外置ADC能够take advantage |
|
|
L****c
发帖数: 209 | 25 这个图里，TLC应该是64GB吧？容量是倍增的。
MLC 2bits/cell: 0~3/cell
TLC 3bits/cell: 0~7/cell |
|
d******d
发帖数: 2210 | 26 嗯，应该是小底撑不起 14bits吧。
多出2bits, 但都是 noise 和没有一样 |
|
|
H********g
发帖数: 43926 | 28 人单倍体基因组3.２Ｇ bp. 1bp 包含2bit信息。 |
|
H********g
发帖数: 43926 | 29 一个精子3.2G base pair, 1 base pair通常最大储存2bit信息, 因此最大信息载量是6
.4Gbit=0.8GByte。假如乘以2亿的话，0.8GBytex0.2G=0.16GGByte.
另外1587G/37.5M=43.32K,这个图的作者怎么算的？ |
|
H********g
发帖数: 43926 | 30 数据不对吧。人单倍体是3.2-3.5G碱基对，如果一个碱基对算2bit那就是6.4-7Gbit，
除以8之后就是800-900 M Byte
==单个人类精子DNA中包含的信息量大约是75M byte |
|
s*******h
发帖数: 3219 | 31 【 以下文字转载自 Midlife 讨论区 】
发信人: sammamish (sammamish), 信区: Midlife
标 题: 最近研究了一下魂斗罗的源代码。为什么魂斗罗只有128KB
发信站: BBS 未名空间站 (Sat Jun 10 12:33:34 2017, 美东)
为什么魂斗罗只有128KB却可以实现那么长的剧情？
1.游戏大量复用图块，图块还使用调色板索引，好像每个像素才占用2bit。
2.程序员精心优化各种数据结构，每一bit存储都不浪费。
3.声音只存储发声通道的调制参数序列，能复用就复用。
4.代码全是汇编写成，直接操作硬件，基本不存在浪费的指令。
个人觉得fc最神奇的游戏还属超级玛丽，32个关卡，每关都不同，各种隐藏要素，好像
代码区才10多k，数据区10多k。反汇编看完还是不敢相信这点东西能玩一个童年…现在
helloworld的二进制都可能比这大多了。 |
|
s*******h
发帖数: 3219 | 32 为什么魂斗罗只有128KB却可以实现那么长的剧情？
1.游戏大量复用图块，图块还使用调色板索引，好像每个像素才占用2bit。
2.程序员精心优化各种数据结构，每一bit存储都不浪费。
3.声音只存储发声通道的调制参数序列，能复用就复用。
4.代码全是汇编写成，直接操作硬件，基本不存在浪费的指令。
个人觉得fc最神奇的游戏还属超级玛丽，32个关卡，每关都不同，各种隐藏要素，好像
代码区才10多k，数据区10多k。反汇编看完还是不敢相信这点东西能玩一个童年…现在
helloworld的二进制都可能比这大多了。 |
|
R*R
发帖数: 2661 | 33 性能这个东西，只是在benchmark上看着好看，实际使用起来根本感觉不出来任何区别
。你能分辨出千分之一秒，百分之一秒的分别吗？
性能都差不多，SSD关键是可靠性。TLC最差的就是可靠性，随着使用时间的增长出错几
率比MLC大的多。
建议你研究一下MLC 2bit per cell 和 TLC 3 bit per cell 有什么区别吧。
当年840 evo 刚出来的时候各大网站的评测也是领先，后来呢，一两年之后问题就来了。 |
|
N*n
发帖数: 456 | 34 我来出个主意吧。你没有提到并行处理，所以假设单流程处理
ID分两段。
第一段 是一个 int number. 这个 INT number 从时间零点开始每秒+1。
第二段 counter m bit(m>14,可以用16bit) 1024x16=16384 之间的数字。每来一个新
请求，则+1.新的一秒开始，则清零重新开始
如果要多流程，彼此不通讯，
假设是 Master-worker arch-tech. 则每个worker node get a unique identifier.
for 16 workers, 0-15
If u want to identify the source of request, u could add x bit,
which is from the 1st x bit of IP. x could be 8. This part can be optimized
, based on IP来源的频率分析.
比如 你统计发现 40% request coming from 199.126.* 30%request
from 17.* 30% fr... 阅读全帖 |
|
N*n
发帖数: 456 | 35 NAT 我当然知道。。所以有后面的IP request 频率分析。。
private IP, 我想你说的10.*, 192.168.* 。。在2bit system, 他们都是在
其它之列。。
如果是 8比特。。就是直接用IP四个数的头一个，那 private IP, 不用的那个刚好
可以做备用。。
MAC 唯一不错，但是用上MAC,全球request..你怎么保证 ID连续？ |
|
n*****t
发帖数: 22014 | 36 基本思想就是流水线，把冲突的瓶颈简化，集中到单个节点。
客户服务器 A：UI、车次选定，向 B 查询
编码服务器 B：提供 web interface 给 A，转换协议，TCPIP 向 C 查询，
2bit 表示操作：查询、锁定、解锁（付款失败等）、确认售出，
1bit 表示后续地址方式：区段、枚举
24bit 表示一个地址，如北京到上海，则其中每个区间皆用一个地址表示，售出一张票
需更新 15 个 byte
中心节点 C：响应查询、锁票，如有必要，TCPIP 包的解析在 kernel 里做，SSD 的写
也单独建分区，做设备文件操作，避开 FS 开销。
注：
1、锁票后，由 A 更新数据库，完成收款、出票、记录等功能，并通过 B 通知中心节
点，交易完成。
2、A 对数据库的操作，可保证无冲突，并可按车次等分布到多台 DB SERVER |
|
g******g
发帖数: 289 | 37
些.
那么block length应该设多大？2bit的话，如果用BCH，应该是7，是否冗余数据太多了
？ 希望处理后的数据越短越好。 |
|
t****t
发帖数: 6806 | 38 你这个7怎么来的..我感觉你对FEC没什么概念.
用哪个码, 要看你的设计要求, 容错率, 延迟, 和原始数据的误码率. 比如说你是10%错
, 那把10组数据绑在一起和把1000组数据绑在一起就不一样. 10个bit平均错一个, 你用
一个纠2错的码, 但你错2个以上的概率是1-((1-p)^10+C(10, 1)p(1-p)^9+C(10,2)p^2(
1-p)^8)=7%. (我知道你一个数据是2bit, 我是为简化说明起见). 1000个bit平均错100
个, 你用纠200错的码, 但你错200个以上的概率基本上可以忽略不计.
去EE版问吧. 这里很少人做这个的. |
|
e*****t
发帖数: 642 | 39 可能这个格式节省一点空间吧，要转成fasta，还得用软件转，叫twobittofa.在Linux
下 make的时候又说library找不到，不知道为啥弄这么复杂。
哪位大虾能发个链接，有rat whole genome seq的。多谢了。 |
|
p*******m
发帖数: 20761 | 40 本文经超能网授权转载，其它媒体转载请经超能网同意
Intel创始人是摩尔定律的提出者，Intel公司也是摩尔定律最坚定的捍卫者。前几年
Intel还在自信半导体工艺领先业界三年半，谁知道14nm节点Intel遭遇了挫折。
而台积电、三星这两家在14/16nm节点之后好像开了挂，10nm工艺去年就宣传说量产了
，今年都要试产7nm了，5nm工艺也要在2020年搞定，这速度可比Intel快多了。
面对被以前的跟班轻松超越的问题，Intel也忍不住了，希望半导体公司在制程工艺描
述上诚实一点，并给出统一的衡量公式。
台积电/三星工艺耍花招：Intel生气了
先说说为什么Intel要介意这个问题。放在几年前，Intel在半导体工艺上一直都是领先
台积电、三星等公司的，22nm节点就开始量产3D晶体管（也就是FinFET工艺），那时候
三星、台积电才推出28nm工艺没多久，跟Intel差距确实挺远的，Intel自然不会有什么
失落感。
但之后的情况不一样了，Intel在14nm遇到了技术问题，原计划的Fab 14工厂升级工艺
也被取消了，以致于Tick-Tock战略停摆，现在14nm工艺都要出四... 阅读全帖 |
|
