我也来写写我的2014投资之路,确切的说应该是2014年下半年才开始的投资之路。
2014年,三十而立,过去的三十年没有任何投资的觉悟,或多或少是因为家人在股市中的惨痛教训,让我一时对股市深恶痛绝,势不两立。但是面对着来自生活,家庭,工作的多方压力,以及三十而立期盼的改变,让我放下旧仇故怨,重新认识起股市,更确切点应该是理财。
一个人一生的成功固然离不开自身的天赋与努力,但是也离不开运气和客观因素。走出校园、踏进职场的时候,或许已经决定了一半的成功,但是事业上的成功并不代表一切,公司会有变故,自身或有改变;太多的不定因素,让我们急需未雨绸缪般的危机处理;我喜欢这样子的比喻,一个人在经济上的成功就好比是一个人走路,稳定的工作,逐步的升迁是可以给你带来不错的收入,但这个是主动的收入,一条腿而已;另外一条腿叫做被动收入,通俗点来说就是“钱生钱”的艺术。一个健康的经济收入,应该是两条腿相辅相成的,这样才能更加稳定安全地跨过人生的每个阶段,事业期、退休期、养老期;无论是高峰还是低估,你都能有更加完善保险的体系支持着你的经济,特别是当你有家庭的时候,更需要这种思维。
2014年年首定目标的时候,并没有将理财投资的计划放在里面;也不确定从什么时候开始,突然就觉悟了,从开始阅读理财投资的书籍、注册雪球、加入投资群、开通各种投资的账号,短短半年时间我就整装待发、迫不及待地开启我的理财投资之路;说来也是极其惭愧和懊悔的,前三十年或多或少地也接触到一些投资理财的信息和机会,但是就是不开窍,可能就是所谓的命里有时终须有、命里无时莫强求;时间到了,就醒悟了;
重新翻起早已耳熟能详的《穷爸爸富爸爸》,让我认识到了理财的重要性,和工作之外成功的可能性;加入了论坛的投资群,让我认识到了各位大牛的各显神通;来到雪球,让我领略到了各种不同的投资理财风格;各种投资账号的注册,让我也开始跃跃欲试起来。
投资理财有不同的渠道与方法,结合自己的情况,整理一套初步的投资组合;组合提出根本还是因为需要有一个风险分散的思维;
美国:
401K:
401K是在美国工作的一个福利,能够抵税以及公司会有匹配;这块来讲,我的计划是只cover公司最大的match百分比,将投资定性为保守安全型;
Vanguard RIA:
将自己的之前公司的401K导到了Vanguard,有更多的投资品种可以选择;因为总量也不是很多,所以就选几个综合表现稳定的基金,为保守安全性投资;
Stock Account:
在公司开的股票账户,目前只有导入少量的资金,买了一个股票,小套;以后我想这个应该是作为我在美国的进攻型投资的一个主要渠道,当然,作为一个无论是理财还是股票的菜鸟,我开始的策略可能会选择稳定分红类股票,通过分红做长远的投资打算;极小部分可以尝试分析过后的激进投资;
房产:
美国自08年次贷危机以来,房市一路下滑到2012年低谷,但是2013年开始已经逐步回暖;只可惜,生在危机中的普通人,少有觉悟危机与机遇并存的道理,包括我自己;今年下半年开始下定决心开始着手买自己在美国的第一套房子,好饭不怕晚;当然,买房不同于买菜,陆陆续续看了半年的房子,从一窍不通一抹黑,到基本了解市场行情和自己的定位,也算没白忙活;美国量化宽松政策已经结束,加息的预期在2015年中,所以趁升息之前,把房子搞定也算是房产投资的第一步;至于以后不动产方面的投资,倒并不是说现在有多少实力拓展,但是介于对于美国房市危机后重振,历史上的稳定性,以及自己所在区域的发展信心,我还是希望将之化为自己投资版图中的一块;
其他:
钱生钱固然美好,但是首先得要有钱才行;基于开源节流的原则,在家庭整体收入与开支方面,还需要有更好的规划和努力。开源:信用卡、代购、微创;节流:记账、优惠、减少不必要的开支;
中国:
理财:
感谢雪球,在理财特别是股票方面对我的开窍,也特别感谢David,辛巴两位,让我对于投资理财有个更快捷的入门;从朋友推荐,我开始看David的《低风险投资之路》,了解到高收益的投资也可以低风险,通过不同的等级的提升,慢慢扩展自己投资的渠道与能力,在低风险中谋求高收益;当然路漫漫其修远兮,吾将上下而求索;我近期的目标定为债券与P2P,熟悉债券的属性与大势的关系,寻找靠谱的P2P平台,进行小额的投资尝试;
股票:
进驻雪球,认识到了更多的大V,也让我对于股票有了更加全面的认识,作为所有理财投资里面风险最高同样也是收益最高的渠道,自己不可以因噎废食;相信通过自己的学习与摸索能够找到一种适合自己的操作方法,不求能在股市中翻江倒海,但求能够成为这片残酷战场上的一名勇士;要成为一名勇士,当然少不了装备自己,已经拜读辛巴老师的《重剑无锋》和《百箭穿杨》,唐朝老师的《手把手教你读财报》也已经预定,很多东西可以站在借着巨人的肩膀,让自己事半功倍,但是无论读书多少,能够真正领悟还需自己的不同努力与尝试摸索,适合自己的才是最好的。
11月底,我拥有了自己的股票的账户,起始资金不多10万,用老婆的话说,最多10万,赚多少是你的本事,就算全亏了也就10万块,多了不许;很好,至少这已经在整个家庭的经济体系中有了一个最安全的底线。在这里我也要感谢上帝对于我的眷顾,让我这个菜鸟,一脚踏进股市,迎面就有一阵风吹来,依靠着各位大V的指点,在短短一个月时间里有了不错的收益;当然,或许能够借着这轮牛市的开启,能够进一步获得不错的收获;但是也要清楚地认识股市的风险,力求在牛熊之中,摸索寻求,不断装备自己,提升自己;
其他:
国内的投资更加多样化,机会也更多,虽然近期不能回国发展,但是自己也可以多联系、多关注国内、家乡、身边的一些投资机会;当你有理财投资的思维的时候,你看问题的观点就会不一样;另外,结合自己的IT专业,可以尝试量化投资,拓宽自己的视野,熟悉技术,融会贯通中美投资的手段,这可以是个长远的目标,需要更多时间和精力的投入,但是我越来越觉得这是一条适合自己的长远之路。
最后,虽然这只是自己2014年理财投资方面的总结,在这里也稍带一下自己的家庭与工作;过去的2014充满变化与挑战,在不断的磨砺中行走,但是还是要感恩,当用积极的态度去面对的时候,会得到上天的帮助。在“震荡中”整理,完善自我,行走在健康盼望的道路上,2015,会更好!
2014年12月31日11:35晚
写于美国纽约
2014年12月31日星期三
2014年7月18日星期五
401k账户
401k概述
401k,读作Four One Kay,是一项雇主资助的养老金计划的框架,因发布在the Internal Revenue Code section 401(k)(税法401条k款)而得名。大多数企业都提供基于该条款制定的养老金计划,作为员工福利的一部分,通称401k计划。不同雇主的401k计划不一定完全相同。下文中某些讨论是基于某公司的计划,可能不适用于其他公司,会用星号标出。
401k是IRA的衍生物。与IRA(Individual Retirement Account,或个人养老金计划)的最大区别是,401k对于个人收入没有苛刻的准入限制,于是可以让更多的人受益。
与中国不同,美国的养老金计划(401k和IRA)不是强制性的。那么,如何鼓励个人参与其中呢?联邦政府的鼓励政策主要包括以下两点:
第一,401k(和IRA)的缴纳部分(contribution amount)是推迟收税(tax deferred)的。401k的缴纳部分,不计入个人当年收入,相当于在当年是免税的。税款计算发生在401k(和IRA)的钱被提取出来那一年。
第二,401k(和IRA)的盈利部分是推迟收税的。401k帐户里的钱,拥有者可以在金融市场上自由(*)支配,购买股票债券基金等。投资所得不计入当年收入。税款计算发生在401k(和IRA)的钱被提取出来那一年。
相应的,为了避免401k(和IRA)成为逃税的工具,联邦政府也出台了一些限制,包括:对于年度缴纳额的限制(2008年401k的缴纳上限是15500美元),对于提前支取的罚金(早于59.5岁支取,除税款外,还需额外支付10%的罚金),和对于高层高收入员工的限制(没有仔细研究,反正未来几年我是没有希望的。。)。
大部分企业针对401k计划也有鼓励政策:雇主匹配(employer match)。雇主会缴纳一定的金额(通常与员工缴纳金额成一定比例,通常有上限)到员工的401k帐户。
Roth 401k概述
Roth 401k和Roth IRA分别是401k和IRA的衍生物。与401k和IRA的最大区别是,Roth 401k和Roth IRA的缴纳金额是来自与税后收入的,所以在支取的时候不需要缴税。Roth 401k和Roth IRA的盈利部分(投资所得)也是不需要缴税的,如果符合如下条件:到达退休年龄,并且帐户开通五年以上;否则,需要计入支取当年收入计税,并且缴纳10%罚款。计税的数额按照如下公式计算:计税的数额与支取总额的比例等于Roth帐户的盈利部分与Roth帐户总额的比例。
Roth 401k诞生于2006年,历史并不很久,所以普及率也不很高。国税局(IRS)要求提供Roth 401k计划的雇主必须同时提供401k计划供员工选择。
比较401k和Roth 401k
放到401k帐户里的钱,迟早也要上税,那么,把钱存到401k帐户,而不是普通的银行账户,有什么好处呢?主要有三点:
1.401k的缴纳金额有可能享受到一个更低的税率: 一,依据历史统计,税率是在慢慢降低的,一方面是由于政策的改变,另一方面是由于通货膨胀;二,美国实行累进制税率,收入越高,税率越高,对于大部分人而言,退休之后的收入要明显低于在职期间的收入。
2.投资所得免税。
3.雇主匹配。
那么,把钱存到Roth 401k帐户,而不是401k帐户,有什么好处呢?
Roth 401k的年度缴纳额比401k更高,于是长期的预期收益更高。虽然Roth 401k和401k帐户共享同一个上限(2008年是15500美元),但是由于Roth 401k的上限是基于税后的缴纳额,于是存在退休金账户里的钱更多。
在你到达59岁,可以开始合法支取退休金账户的时候,Roth 401k帐户可以一笔全部支取,而不需要缴纳任何额外费用。而401k帐户则需要合理选择支取时间表分成几年来支取,因为401k的支取是要记入当年收入的,大笔支取会造成税率升高,从而违背了加入401k计划的初衷。
刚刚参加工作的年轻人,如果当前的税率很低,并且预期将来的收入会增加,宜加入Roth 401k。
那么,与Roth 401k相比,401k有什么好处呢?
401k的缴纳部分,不计入当年收入,带来的额外好处是:很多减免税条款是基于当年调整后总收入(AGI)的,参与401k有可能让你享受到额外的减免税条款,或者让你避免额外的税款(此处特指替代最低税,AMT)。Roth 401k没有这项好处。
把钱放到自己的账户里,而不是交给IRS,永远是件好事。也许将来你能找到其他避税的方案呢。
两种计划在其他方面还有什么区别呢?
通常情况下,401k和Roth 401k不可以提前支取,除非是在离开当前雇主之后(*)。
在特定情况下,401k可以申请提前支取,称为困境支取,条件包括:高额医疗费用、教育费用,或者购买主要住所。某公司的规定是,如果申请了困境支取,那么未来半年之内不能缴纳401k,也不能参加ESPP。对于年收入十万的人来说,机会成本是3000元左右(*)。
也可以向自己的401k帐户申请贷款。贷款额不超过总额的一半,上限50000元。借给你钱的人是未来的你,所以利息也还给未来的你,还到你的401k帐户中去。从401k贷款的坏处包括:减缓401k的增长;401k贷款的利息要交两份税(还到401k账户的利息是税后收入,而将来提取的时候还要再次缴税);银行贷款的利息可以用来减税,而401k贷款的利息不能用来减税。
还有什么要注意的呢?
401k和Roth 401k有风险。持续为正的收益率,需要你付出足够的精力来管理。2008年,纽约三大股指跌回了十年前的水平,这意味着,如果在这十年里你没有对自己的投资做任何调整,很有可能颗粒无收。或者血本无归,如果你不幸选择了北电、雷曼兄弟或者华盛顿互惠。
401k的首要好处,未来税率可能会降低,只是若干种未来中的一种。你没有办法预测你在退休时的收入,你也没有办法预测在你退休时的政策,此外,通货膨胀,社会安全福利,你能享受到的或者没有办法继续享受的减税条款,都会影响你在退休时的税率。
参加401k和Roth 401k要尽早。假定投资的年收益率稳定在6.5%,并且每月存进401k(或Roth 401k)的数额是一定的,那么如果路人甲只在二十岁到三十岁这十年间缴纳401k(或Roth 401k),而路人乙在三十岁到六十岁这三十年间缴纳401k(或Roth 401k),你会惊奇的发现,在两个人退休的时候,路人甲有更多的钱可以支配。
下面总结一些典型的场景:
如果希望取得一个近期和远期平衡的退休计划,请考虑401k。
如果对现金有爱,请考虑Roth 401k:在换工作的时候,可以立即变现前雇主匹配;在到达59岁时,可以一次取出全部退休金。
如果对退休后生活的重视程度非常高,请最大化Roth 401k缴纳额,并且开通IRA/Roth IRA。
如果希望尽快买房,那么:如果雇主匹配不超过50%,请不要加入任何计划;否则,可以考虑加入401k。原因是:从401k贷款只能取出一半,如果雇主匹配为50%,那么贷款额度为个人缴纳额的75%,正好相当于不加入养老金计划时手里拿到的现金。与401贷款相比,不加入任何计划是在牺牲退休后利益的同时换取中远期的利益。(记住401k贷款也是要还的。)401k困境提取通常是个更差的选择。
如果在取得绿卡之前永久性离开美国,Roth 401k可以一次性取出,401k则比较麻烦。如果一次性取出,将会面对较高税率和10%罚款。有人认为可以分多年取出,按照非居民(Non-Resident)身份报税,理论上如果每年取出的额度足够低,每年只需缴纳10%罚款,而不需要缴税。听起来不错,不过还未经证实。
1. 什么是401k账户?
401k 账户是一种退休投资账户。基本原理就是你年轻的时候往账户里面存钱投资各种基金及股票,退休后取出来用。
许多公司把401k作为一种福利,match你工资收入的一定百分比。比方说,公司的政策是dollar for dollar match up to 5%。也就是说你每存一美元进去,公司也出一美元存进你的账户,直到存满你工资的5%。之后你再存钱进去, 公司就不再match了。所以如果你一年内contribute 5%, 你的账户里实际有了你工资的10%。但须注意有的公司帮你存的钱可能不是fully vested。公司的contribution虽然在你的账户里显示,但还不真正属于你。如果你公司的规定是4年vested而你在第二年便离开公司,你只获得你自己的contribution加上公司contribution的25%。
2. 应该存多少钱进401k账户
你应该存至少你的雇主所match的工资的百分比。因为公司给match的那部分钱等于是白送,不拿白不拿。假设你公司match 5%,而你的工资是10万。如果你只contribute 3%,你等于白白丢掉了$2000。
那存满公司match的百分比之后呢?你或许听说过401k有避税功能,是不是存得越多越好呢?现在让我们来看看401k是怎么省税的。
a. 降低tax bracket: 把钱存进401k可以降低当前的taxable income。 如果存得足够多,你可以此降低自己的tax bracket。
b. 延迟交税:存进401k账户里的钱并不是不交税,而是推迟交税,取钱时再交税。这样做的好处有两重:一是投资收益能够不受税率影响地利滚利。假设现有1000块,平均每年投资回报率是10%,税率是30%。30年后就是1000*1.1^30*70% = 12214。如果没有推迟交税的优惠政策,30年后这1000块只变为1000*1.07^30 = 7612。当然这个例子有些夸大,因为很少有人能够达到30%的tax bracket。你应根据自己的实际税率来计算。二是如果将来的税率比现在的税率低,这1000元的本金所交的税会比现在少。
现在让我们来分析一下怎样决定放多少钱进401K:
首先,考虑自己的实际需要。你也许很想通过401k来降低当前的taxable income。但要知道,存进401k里的钱要到59岁半之后才能取出来。提前取除了补交税以外,还要付10%的罚款。所以一定要考虑清楚将来可能的花费,例如买房,小孩上学,意外失业等。
其次,比较401k同其他投资的收益。401k里可供选择的基金有限,每个公司提供选择的基金也不一样。有时你会发现,401k里的投资基金不如市面上的一些投资基金好。这样即使401k在税收上有些优势,但如果投资效益不好,又不能随便取出来,也不见得划算。
再次,401k避税优势一部分是建立在退休时的税率比现在低的假设下的。但这个假设并不一定成立。我们辛苦工作,努力赚钱投资,就是为了退休后能过上不错的生活。你并不希望你退休时每年只有两万块的收入或生活水平比现在下降,那为什么会假设退休时的taxable income比现在低呢。
最后,如果你经过慎重考虑,仍然决定maximize contribution, 那么请记住政府对于退休账户的投入有一定限制。在2010年个人最多能存$16,500。同时你的雇主还可能规定你的401k contribution不能超过一定的工资百分比(10%)。
3. 401k里的钱应怎样投资
现在终于进入正题了。在这节里,我将给出非常实用的建议。
Rule NO 1:Diversification
我经常听到周围有人说,反正我们还年轻,不需要diversification。应该把钱放在最aggressive的fund里面,高风险,高回报。一旦亏了,有足够的时间来recover。我并不同意这样的做法。无论你年纪几何,任何时候,你都不想亏钱。何况,从长期来看,一只大起大落的基金,平均回报率并不一定比一支有适当稳定回报率的基金要高。那些把所有钱放到最aggressive的fund里去的人,相信在2008年末的经济危机中已经尝到了苦果。虽说现在涨回来很多,但要知道由于本金变少,原来如果下跌50%,现在需要涨100%才能回到过去的水平。我还有朋友在房地产上涨的那几年,把所有钱放到REITS里,估计好几年也涨不回来了。当然你也可以举例有人就找到了一只super好的基金,所有钱全放里面,好多年了一直赚钱。那么我要说这是在speculation,而不是investment。我并不否认speculation也有可能赚钱,就好像不否认有人去Las Vegas赢了钱回来一样。问题是概率。赌博胜出的概率是远小于正常投资赚取适当回报的概率的。
Buffet的老师Graham在他的The Intelligent Investor里说得好,在任何时候,都不要让你的portfolio里的stocks或bonds超过75%。换句话说,就是stocks和bonds的最大allocation是75%/25%。当你有充足的理由认为这段时间股票比bond好,可以hold 75%的股票。当你有充足的理由认为现在bond比股票较好,hold 75% bond。如果不知道哪个更好,hold 50%/50%.
最近一年里,bond尤其是junk bond大涨。如果你想乘机买入一些bond,我想提醒你,可能已经太晚了。Bond的价钱和interest rate成反比。Interest rate升,bond跌。Interest rate跌,bond升。现在利率处于历史最低,迟早会长上去,到时bond就可能大跌。
Rule NO 2:Buy the funds with cheapest fees
401k的投资选项主要是一些mutual fund。你在研究一个基金时,一定要注意它的expense ratio. 要知道不管你的基金是在赚钱还是亏钱,这些management fees都要从你的基金里扣除。有许多actively managed funds, 费用很高。你可能会想,如果一只基金的回报优于其它基金,收费高一些也没关系。问题是你是没有办法知道一只基金是否优于另一只基金的,估计连这两个基金的投资经理也不知道。某只基金可能在某一年或某几年的回报高于其他基金,但过去的experience不能代表将来,长期来讲谁也说不定。唯一可以确定的是你将会被征收的费用。所以在不能确定两只基金孰优孰劣时,我就买expense ratio最低的。
Rule NO 3: Buy index funds
Index fund顾名思义,也就是这类基金通过增减所持的资产来和某种指数保持一致。比如说S&P 500的index,就会持有S&P 500的公司的股票来match S&P 500 index。这种基金也被归类为passive management。相比active managed fund,他不需要做很多的分析来决定交易,交易的次数也少很多,所以费用就相对便宜。它的原理在于,长期的统计数据证明,98% active managed的基金都没有办法超越大盘的回报。那么为什么要费心挑选股票呢,只要建立一个能match市场的portfolio就好了。
有人会问,那市场跌的时候怎么办,这些fund铁定是跌了。同样,我们没有慧眼能找到那只在熊市逆势增长的资金。在2008年底market crash的时候,我察看了我自己的401k账户和Vanguard的投资基金,发现除了treasury bond,其他没有一只基金的回报不是负数。而且下跌程度比起相应的指数基金来说是只多不少。
对付熊市的唯一方法就是分散投资。可以买一些S&P500的指数,bond的指数,emerging market的指数。
Rule NO 4: Avoid life cycled funds
Vanguard的 Target Retirement 2045就属于life cycled fund。这类基金也叫做fund of funds。它并不直接购买股票或债券。而是持有其他mutual funds作为资产。投资策略是根据你的退休时间来决定的。随着时间的推进,策略将会越来越趋于保守,会不断调整所持基金的百分比。同时,如果买这种基金,理论上就不应再买其它基金。因为一旦买入其它基金,就破坏了计算好的asset allocation百分比。
这类基金的实质就是基金经理帮投资者作了asset allocation决定。投资者失去了很多自由度。只能投资基金经理选定的基金。我前面讲过,我并不认为投资策略应该根据一个人的年龄或是退休时间来决定。同样年纪的两个人,因为他们各自的收入,存款,花销都不一样,怎么可能采用相同的asset allocation?很多人是乐于把这个asset allocation的事交给基金经理的。因为方便,省事。怎么说人家是专家啊。选定的基金一定比我们的合理。那么我这样说,同是target retirement 2045的基金,Vanguard和Fidelity的投资策略就有很大不同。那我们应该相信哪一个专家呢?所以说自己的投资,自己打理,自己做主。
再者,这类基金也分为passive managed和active managed两种。如果是active managed,你会发现它的expense ratio 较高。根据前面的Rule No2,也应尽量避免这类基金。
2014年3月24日星期一
2014年2月5日星期三
沉浮
有一天 你若觉得失去勇气,有一天 你若真的想放弃,有一天 你若感觉没人爱你,有一天 好像走到谷底
那一天 你要振作你的心情,那一天 你要珍惜你自己,那一天 不要忘记有人爱你,那一天 不要轻易说放弃
这个世界真有一位上帝,祂爱你 祂愿意帮助你,茫茫人海 虽然寂寞,祂爱能温暖一切冷漠
祂的双手 渴望紧紧拥抱你,漫漫长夜 陪你走过,祂爱你 伴你一生之久
听着盛晓玫的歌曲,感叹最近发生的很多事情,是啊,人是多么的脆弱,如不是依靠上帝,我们又何以承担这一切。神爱世人,希望爱能改变一切。
这里,特别为xixi的妈妈献上祝福,如果上帝觉得她累了,想让她休息了,就请你让她在新的地方能够得到快乐,让在世上的亲人和朋友得到安慰。xixi是不幸,又是幸运的,希望她的成长道路,你时刻陪伴她,用你的爱来弥补她所失去的,因为她是你的儿女,你的天使。
我的妈妈,我也想跟你说,活着世上是一件多么不容易的事情,不要太要强太苛求,我有不到位的地方,请你谅解,我知道自己很多地方还不到位,还要更加努力,也请你放下你心中的重担,希望你每天都是开心的。我知道这几年,你和爸爸都会很辛苦,但是我希望苦尽甘来,今后的几年你们不用再分开,不用再操劳,也不用再为我操心了。愿上帝保守看顾你们。
孩子们,你们也要快快长大,多多懂事,我们今天经历的一切会成为明天宝贵的回忆。你的成长是要付出代价的,我们现在的付出,希望能够与你们一同创造更好的明天。两个儿子是正气的,希望我们这个家也因你们而荣耀。因为你们不仅是我的孩子,更是神的儿女,你们的道路与未来在神的手中,你们的点点滴滴离不开他。
工作临近转换的过程,不知道选择是对是错,但希望我自己能够在每次改变中都能够有所进步,时常反省,时常审查自己,不要再犯同样的错误,努力,效率,有远见,为自己的三十而立而呐喊。
微软的新总裁和印度人与华人在北美职场上的争斗成为了最近最火的话题,怎样,从点滴做起,扬长避短,不断完善自我,团结,全然交托。简短的总结,不想多说了。
那一天 你要振作你的心情,那一天 你要珍惜你自己,那一天 不要忘记有人爱你,那一天 不要轻易说放弃
这个世界真有一位上帝,祂爱你 祂愿意帮助你,茫茫人海 虽然寂寞,祂爱能温暖一切冷漠
祂的双手 渴望紧紧拥抱你,漫漫长夜 陪你走过,祂爱你 伴你一生之久
听着盛晓玫的歌曲,感叹最近发生的很多事情,是啊,人是多么的脆弱,如不是依靠上帝,我们又何以承担这一切。神爱世人,希望爱能改变一切。
这里,特别为xixi的妈妈献上祝福,如果上帝觉得她累了,想让她休息了,就请你让她在新的地方能够得到快乐,让在世上的亲人和朋友得到安慰。xixi是不幸,又是幸运的,希望她的成长道路,你时刻陪伴她,用你的爱来弥补她所失去的,因为她是你的儿女,你的天使。
我的妈妈,我也想跟你说,活着世上是一件多么不容易的事情,不要太要强太苛求,我有不到位的地方,请你谅解,我知道自己很多地方还不到位,还要更加努力,也请你放下你心中的重担,希望你每天都是开心的。我知道这几年,你和爸爸都会很辛苦,但是我希望苦尽甘来,今后的几年你们不用再分开,不用再操劳,也不用再为我操心了。愿上帝保守看顾你们。
孩子们,你们也要快快长大,多多懂事,我们今天经历的一切会成为明天宝贵的回忆。你的成长是要付出代价的,我们现在的付出,希望能够与你们一同创造更好的明天。两个儿子是正气的,希望我们这个家也因你们而荣耀。因为你们不仅是我的孩子,更是神的儿女,你们的道路与未来在神的手中,你们的点点滴滴离不开他。
工作临近转换的过程,不知道选择是对是错,但希望我自己能够在每次改变中都能够有所进步,时常反省,时常审查自己,不要再犯同样的错误,努力,效率,有远见,为自己的三十而立而呐喊。
微软的新总裁和印度人与华人在北美职场上的争斗成为了最近最火的话题,怎样,从点滴做起,扬长避短,不断完善自我,团结,全然交托。简短的总结,不想多说了。
2014年1月30日星期四
过年了
过年了,今年是离家的第六个年头了,如果家是父母所在的地方,那连家都离家了。哎,科技发达了也不好,因为千里之外发生了什么,你都能够知道。每逢佳节倍思亲,看的到摸不到,思乡亲更切。
已经好久没有好好过过一个年了,因为远了,也或许是因为大了,再难回到以前那种意境了。变了,想回去,也已身不由己。想想有时候,平平淡淡的生活,有亲人在身边,足矣。亲情比起任何的一切身外之物都来得自然而又暖人心。
即使有什么矛盾不开心,也因为流着一样的血,积存不了。
盼着回去的那天,憧憬又有点彷徨,何必去多想。其实生活也是这样,简单点就好,因为活着太累。
背井离乡,还好有主,伴我左右,慈爱恩典,永相随。
有怎样的米,就做怎样的饭。年要过,即使人不同,只要心境相同,年味就有了。
希望每个不在家过年的孩子,新春快乐,马年大吉!
已经好久没有好好过过一个年了,因为远了,也或许是因为大了,再难回到以前那种意境了。变了,想回去,也已身不由己。想想有时候,平平淡淡的生活,有亲人在身边,足矣。亲情比起任何的一切身外之物都来得自然而又暖人心。
即使有什么矛盾不开心,也因为流着一样的血,积存不了。
盼着回去的那天,憧憬又有点彷徨,何必去多想。其实生活也是这样,简单点就好,因为活着太累。
背井离乡,还好有主,伴我左右,慈爱恩典,永相随。
有怎样的米,就做怎样的饭。年要过,即使人不同,只要心境相同,年味就有了。
希望每个不在家过年的孩子,新春快乐,马年大吉!
2014年1月23日星期四
搬完家了
2014年1月20日,趁着马丁路德金日,我们毅然决定搬家,虽然当时转校的事情都还没有着落。感谢主,搬家那天,虽然很慌乱,但是终究是搬完了,看着满满一屋的东西,感叹当年刚踏上美利坚地土的时候还只是一个人两个箱子,现在依然4个人,一屋子家当了。不过家人还是兴奋的,虽然也还是租的房子,但是毕竟换了一个更大更舒适的地方,符合逐渐步入小康的节奏。
更值得感谢主的是,老大的转校事宜峰回路转,搬完家的第二天,我们就开始着手转校的事情,虽然纽约突降大雪,但是我们依然顶着风雪在外面漂了一天,感动了上帝,派下天使来帮助,事情就这样成了,老大有幸被转到了整个纽约市最好的一座公立小学。第二天,我们也接到通知并去学校完成了注册的工作。今天,老大第一天上学,虽然一开始,不情愿转校的他,不过现在看来,他还是很喜欢新的环境的。希望他能够在新的学校里面开心每一天,最主要的还是能够在行为规范上快快长大,懂事一点,老爸老妈就更省心了。
新工作的背景调查还在进行,不知道前面的路如何,但是凡事交托仰望给主耶稣,不去多加考虑,坚定仰望,相信主必有慈爱与恩典。
事挺多的,希望自己与家人都能够顺利度过这段时间。感谢主,哈利路亚!
更值得感谢主的是,老大的转校事宜峰回路转,搬完家的第二天,我们就开始着手转校的事情,虽然纽约突降大雪,但是我们依然顶着风雪在外面漂了一天,感动了上帝,派下天使来帮助,事情就这样成了,老大有幸被转到了整个纽约市最好的一座公立小学。第二天,我们也接到通知并去学校完成了注册的工作。今天,老大第一天上学,虽然一开始,不情愿转校的他,不过现在看来,他还是很喜欢新的环境的。希望他能够在新的学校里面开心每一天,最主要的还是能够在行为规范上快快长大,懂事一点,老爸老妈就更省心了。
新工作的背景调查还在进行,不知道前面的路如何,但是凡事交托仰望给主耶稣,不去多加考虑,坚定仰望,相信主必有慈爱与恩典。
事挺多的,希望自己与家人都能够顺利度过这段时间。感谢主,哈利路亚!
2014年1月13日星期一
最近
最近,发生了很多事情,心境也有点窘迫,新年伊始的挑战不小。
出门开车,需要的是耐心、细心和静心,不争一分半秒,每次安全抵达就是一次成功的驾驶。希望每个开车的人都能够保护好自己,也保护好别人。
遇到突发的情况,静下心来,冷静处理。不慌张、不愤怒,用最好的态度去寻求最有效地解决方法。
工作中,专心,不再分心于工作以外的事情,做好计划,做个有心人,自我激励,在适当的场合和方面突出表现自己。在海外华人要取得职场上的成就是不容易的,希望自己努力克服缺点,积极改变。
面对生活窘境的时候,学会放下重担,投入主的环抱。自己不知所措,担忧纠结的问题,思考再多也无多大益处,试着交给神,让神去做工,相信神一定会把最好的计划留给自己,神的恩典与慈爱永远伴随自己。阿门。
房子的事情基本定了,虽然历经波折,甚至连定了之后,又有些许悔意,但是勇敢向前吧,不要在原地逗留了,明天的担忧就是今天的激励。生活就是一个问题接着一个问题,靠着主,又有什么可担忧的呢。月底之前要搬家了,希望孩子的转校和搬迁过程一次顺利,也希望我们在新的地方,对于孩子,我们全家都是一个新的开始,相信美好的明天等着我们。
希望教会在新的一年中有更好的发展,兄弟姐妹彼此相爱,彼此扶持,让教会在大纽约地区成为神的祝福,也请使用我们在新的一年中,做更大的事,做更荣耀的见证。
常常喜乐,不住的祷告,凡事谢恩。
出门开车,需要的是耐心、细心和静心,不争一分半秒,每次安全抵达就是一次成功的驾驶。希望每个开车的人都能够保护好自己,也保护好别人。
遇到突发的情况,静下心来,冷静处理。不慌张、不愤怒,用最好的态度去寻求最有效地解决方法。
工作中,专心,不再分心于工作以外的事情,做好计划,做个有心人,自我激励,在适当的场合和方面突出表现自己。在海外华人要取得职场上的成就是不容易的,希望自己努力克服缺点,积极改变。
面对生活窘境的时候,学会放下重担,投入主的环抱。自己不知所措,担忧纠结的问题,思考再多也无多大益处,试着交给神,让神去做工,相信神一定会把最好的计划留给自己,神的恩典与慈爱永远伴随自己。阿门。
房子的事情基本定了,虽然历经波折,甚至连定了之后,又有些许悔意,但是勇敢向前吧,不要在原地逗留了,明天的担忧就是今天的激励。生活就是一个问题接着一个问题,靠着主,又有什么可担忧的呢。月底之前要搬家了,希望孩子的转校和搬迁过程一次顺利,也希望我们在新的地方,对于孩子,我们全家都是一个新的开始,相信美好的明天等着我们。
希望教会在新的一年中有更好的发展,兄弟姐妹彼此相爱,彼此扶持,让教会在大纽约地区成为神的祝福,也请使用我们在新的一年中,做更大的事,做更荣耀的见证。
常常喜乐,不住的祷告,凡事谢恩。
2014年1月2日星期四
成功与坚持
做事成功与否的第一步,就是有没有毅力坚持下去。哪怕每天进步一点点,也一定能取得一定的果效。
坚持不一定会成功,但是成功一定要坚持。
就如07年的淘宝我们没有坚持下来;08年的代购我们没有坚持下来。
试试看吧,哪怕再小的事,只要点滴积累就能够一定带来收获的。
坚持不一定会成功,但是成功一定要坚持。
就如07年的淘宝我们没有坚持下来;08年的代购我们没有坚持下来。
试试看吧,哪怕再小的事,只要点滴积累就能够一定带来收获的。
海量数据处理面试题
第一部分、十道海量数据处理面试题
1、海量日志数据,提取出某日访问百度次数最多的那个IP。
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。
或者如下阐述(雪域之鹰):
算法思想:分而治之+Hash
算法思想:分而治之+Hash
1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;
2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
典型的Top K算法,还是在这篇文章里头有所阐述,详情请参见:十一、从头到尾彻底解析Hash表算法。
文中,给出的最终算法是:
第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成统计(之前写成了排序,特此订正。July、2011.04.27);
第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。
即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N'*O(logK),(N为1000万,N’为300万)。ok,更多,详情,请参考原文。
文中,给出的最终算法是:
第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成统计(之前写成了排序,特此订正。July、2011.04.27);
第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。
即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N'*O(logK),(N为1000万,N’为300万)。ok,更多,详情,请参考原文。
或者:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
方案:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,...x4999)中。这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。
对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。
4、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。
还是典型的TOP K算法,解决方案如下:
方案1:
顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。
方案1:
顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。
对这10个文件进行归并排序(内排序与外排序相结合)。
方案2:
一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。
一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。
方案3:
与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。
与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。
5、 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
方案1:可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,...,a999)中。这样每个小文件的大约为300M。
遍历文件b,采取和a相同的方式将url分别存储到1000小文件(记为b0,b1,...,b999)。这样处理后,所有可能相同的url都在对应的小文件(a0vsb0,a1vsb1,...,a999vsb999)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。
方案2:如果允许有一定的错误率,可以使用Bloom
filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom
filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。
Bloom filter日后会在本BLOG内详细阐述。
6、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。
方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32
* 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。
7、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
与上第6题类似,我的第一反应时快速排序+二分查找。以下是其它更好的方法:
方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。
方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。
dizengrong:
方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:
又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:
又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1
1.次最高位为0
2.次最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入相应的文件再查找。
.......
以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。
与要查找的数的次最高位比较并接着进入相应的文件再查找。
.......
以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。
附:这里,再简单介绍下,位图方法:
使用位图法判断整形数组是否存在重复
判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。
使用位图法判断整形数组是否存在重复
判断集合中存在重复是常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重循环法就不可取了。
位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
欢迎,有更好的思路,或方法,共同交流。
8、怎么在海量数据中找出重复次数最多的一个?
方案1:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。
9、上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。
方案1:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第2题提到的堆机制完成。
10、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
方案1:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。
附、100w个数中找出最大的100个数。
方案1:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w*100)。
方案3:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。
第二部分、十个海量数据处理方法大总结
ok,看了上面这么多的面试题,是否有点头晕。是的,需要一个总结。接下来,本文将简单总结下一些处理海量数据问题的常见方法,而日后,本BLOG内会具体阐述这些方法。
下面的方法全部来自http://hi.baidu.com/yanxionglu/blog/博客,对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎讨论。
一、Bloom filter
适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
基本原理及要点:
对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge
大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
扩展:
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
二、Hashing
适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存
基本原理及要点:
hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。
hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。
扩展:
d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。
d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。
问题实例:
1).海量日志数据,提取出某日访问百度次数最多的那个IP。
IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。
1).海量日志数据,提取出某日访问百度次数最多的那个IP。
IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。
三、bit-map
适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下
基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码
扩展:bloom filter可以看做是对bit-map的扩展
问题实例:
1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。
四、堆
适用范围:海量数据前n大,并且n比较小,堆可以放入内存
基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。
扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。
问题实例:
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
五、双层桶划分----其实本质上就是【分而治之】的思想,重在“分”的技巧上!
适用范围:第k大,中位数,不重复或重复的数字
基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。
基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。
扩展:
问题实例:
1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。
问题实例:
1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。
六、数据库索引
适用范围:大数据量的增删改查
基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。
七、倒排索引(Inverted index)
适用范围:搜索引擎,关键字查询
基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
以英文为例,下面是要被索引的文本:
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的反向文件索引:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what","is"和"it"将对应集合的交集。
正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
扩展:
问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。
问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。
八、外排序
适用范围:大数据的排序,去重
基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
扩展:
问题实例:
1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。
九、trie树
适用范围:数据量大,重复多,但是数据种类小可以放入内存
基本原理及要点:实现方式,节点孩子的表示方式
扩展:压缩实现。
问题实例:
1).有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
1).有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
十、分布式处理 mapreduce
适用范围:数据量大,但是数据种类小可以放入内存
基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
扩展:
问题实例:
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?
问题实例:
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?
经典问题分析
上千万or亿数据(有重复),统计其中出现次数最多的前N个数据,分两种情况:可一次读入内存,不可一次读入。
可用思路:trie树+堆,数据库索引,划分子集分别统计,hash,分布式计算,近似统计,外排序
所谓的是否能一次读入内存,实际上应该指去除重复后的数据量。如果去重后数据可以放入内存,我们可以为数据建立字典,比如通过 map,hashmap,trie,然后直接进行统计即可。当然在更新每条数据的出现次数的时候,我们可以利用一个堆来维护出现次数最多的前N个数据,当然这样导致维护次数增加,不如完全统计后在求前N大效率高。
如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形,可以做的改变就是将字典存放到硬盘上,而不是内存,这可以参考数据库的存储方法。
当然还有更好的方法,就是可以采用分布式计算,基本上就是map-reduce过程,首先可以根据数据值或者把数据hash(md5)后的值,将数据按照范围划分到不同的机子,最好可以让数据划分后可以一次读入内存,这样不同的机子负责处理各种的数值范围,实际上就是map。得到结果后,各个机子只需拿出各自的出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是reduce过程。
实际上可能想直接将数据均分到不同的机子上进行处理,这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上,而另一个则可能完全聚集到一个机子上,同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个,我们将1000万的数据分布到10台机器上,找到每台出现次数最多的前 100个,归并之后这样不能保证找到真正的第100个,因为比如出现次数最多的第100个可能有1万个,但是它被分到了10台机子,这样在每台上只有1千个,假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的,比如有1001个,这样本来具有1万个的这个就会被淘汰,即使我们让每台机子选出出现次数最多的1000个再归并,仍然会出错,因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上,而是要根据hash 后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。
而外排序的方法会消耗大量的IO,效率不会很高。而上面的分布式方法,也可以用于单机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。
另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际中出现最多的那些词作为一个字典,使得这个规模可以放入内存。
订阅:
博文 (Atom)
美国交通罚单解密
以下经验都基于本人在纽约市的经验而谈,如有出入,敬请谅解并另行考证。 在美国纽约生活了十年,开车到现在也差不多有7年的时间了。相信每个人的驾车史,特别是对于刚来美国的新移民,总难免受到交通罚单的困恼。 之前我也有提到过罚单的 博文 ,这次主要是结合自己的实际经验给大家分享...
-
以下经验都基于本人在纽约市的经验而谈,如有出入,敬请谅解并另行考证。 在美国纽约生活了十年,开车到现在也差不多有7年的时间了。相信每个人的驾车史,特别是对于刚来美国的新移民,总难免受到交通罚单的困恼。 之前我也有提到过罚单的 博文 ,这次主要是结合自己的实际经验给大家分享...
-
最近交通安全周,警察抓违规开罚单的紧,老婆昨天 local 超速被抓, 203 刀的罚款 +4 个点;阿哥长岛 495 高速被抓,更是连开 7 张罚单。很多华人初在美国开车,难免因为语言或是交规知识匮乏,大受罚单苦恼。还记得自己刚拿车子的第一天,还没开出去几迈,就因为违规停车被...
-
http://en.wikipedia.org/wiki/Trie Unlike most other algorithms, tries have the peculiar feature that the time to insert, or to delete or...