Powered by
Murph Cooper Lab
  • Home
  • Growing n Evolving
  • Competence Circle
    • Philosophy >
      • Her
      • Quotes
      • Day One
      • Wu Jun
      • Outside >
        • There
      • North Star
    • Analyzing >
      • Investment >
        • Primary Market
        • Secondary Market
        • Cryptocurrency
      • Companies >
        • Meitua美团
        • Amazon
        • Amino Capital
        • Alphabet >
          • Jeff Bezos
        • Berkeshire Hathaway
        • Tesla
        • JD
        • Microsoft
        • Apple >
          • Steve Jobs
        • Nvidia
        • SpaceX
        • Blue Origins
        • Softbank
        • Alibaba
        • Tencent
        • Huawei华为
      • Industries / Sectors >
        • P1 >
          • Mining
          • Healthcare
          • Supply Chain
          • Retailing
          • Blockchain
          • Cloud Computing
          • AR/VR/MR
        • P2 >
          • Aerospace
          • Computer Vision
          • Autonomous Vehicle
          • Manufacturing
          • IoTs
      • Figures/Stars
      • Designs /Aesthetics >
        • Designers >
          • Jony Ive
        • Products
        • Houses
        • Apartments
        • Cars
        • Swords
        • Aircrafts
        • Spacecrafts
      • Civilizations >
        • Egypt
        • China
        • Greece
        • Baylon
        • Persia
        • Rome
        • Carthage
        • Arab
        • Japan
        • Spain
        • Italy
        • Portugal
        • France
        • Germany
        • Kievan Rus
        • Russia
        • Sweden
        • United Kingdom
        • Netherlands
        • Uniited States
        • Singapore
    • Coding >
      • SQL
      • Python
      • R
      • Data Visualizations
    • Numbers >
      • Statistics
      • Probability
      • Logic
      • Linear Algebra
      • Matrix
    • Languages >
      • Chinese
      • English
      • Japanese
      • German
      • Russian
      • Swedish
      • Latin
    • Physical >
      • Kendo
      • Workout >
        • Health
      • Mixed Fighting
      • Shooting
  • About Me

064 | 计算机科学中的随机化 —— Bitcoin的基础之一

10/18/2018

 
我们通常比较喜欢确定性,不喜欢随机性。但是在计算机科学中,很多时候我们故意要把确定性变成随机的,这种思维显然和我们人类的思维不同。我们前几天提到了查到和搜索需要用到这种方法,今天我们填上这个坑。另外,每个人都不知不觉地使用信息加密,也离不开随机化。我们今天说比特币是安全的,其实也是靠随机化来做保障。当然,我们还是从查找信息这件事说起。

之前几次讲到有效查找信息可以借助搜索这个工具。比如说我们要找李强的信息,有了索引之后,计算机可以先在索引中找到李强的信息所存放的位置,然后才是进一步获取所要的信息。有了索引之后,计算机可以先在索引中找到李强的信息所存放的位置,然后才是进一步获取所要的信息。但是在前几天的课中,我们忽略了一个问题,就是在索引中,我们怎么找到李强的位置?如果我们的索引包含北京市户籍中所有的人名,这个索引本身就很大,可能有几百万,或者上千万。虽然在索引中找到李强比在数据库中找到他容易,但毕竟是件不小的事情。类似地,在搜索引擎中,虽然我们根据每一个词把所有的文档建立了索引,但是在Google的词表中,全世界有千万个不同的词,要在索引中找到“得到”这个词,也不容易。(是啊,感觉是之前做过的爬虫逻辑有点像。)

解决办法是,把索引排个序,用二分查找即可。没错,这确实是一个好方法。对于规模不大的数据库,索引也是这么建立的。这种方法最大的好处是不会浪费任何空间,储存的效率比较高。那么用二分查找,在索引中找到“李强”要查找多少次呢?假设北京市人名索引中有800万个不同的人名,或者Google的词表中有800万个单词,通过二分查找需要23次可以找到“李强”,或者”得到”,也就是Log(8,000,000)。23次算不算多呢?(为什么我得出的是6.9呢?)这对计算机科学家来讲不算一件了不得的事情,但是在工程上这个次数算不算多,得看具体的应用了。对于查户籍这件事,23次查找真算不上什么,但是对于语音识别或者机器翻译,识别或者翻译一句需要查找上万次词语,如果每一个词都要先在索引查23次才能找到,就是一个大负担了。我们希望最好有一个办法,能否三下两下就找到“李强”或者“得到”在索引中的位置,这样可以节省十倍的时间了。

上面这样的想法现实不现实呢?事实上是可以做大的,但是要付出一点代价,它就需要用到我所说的随机化了。下面我就来讲讲随机化是怎么样进行的。

#方法一
首先,我们来看一个笨办法,有些时候,笨办法是好办法的基础。我们知道,汉字大约有两万多个,我们就放大一下,假设是3万个吧。这样每个汉字就对应了一个从0~29999的数字。加入“李”这个字对应3500,“强”这个字对应“4003”(哇,那英语怎么办呀?俄语呢?其他特别的语言呢?比如阿拉伯语?),那么,“李强”就对应就对应一个数字组3500和4003。注意这个对应是唯一的,没有歧义性。

接下来,我们做一个简单的数学变换,把上面两个数字变成一个,方法是:30000 * 3500 + 4003 = 105,004,003,也就是说拿105,004,003这个数字作为“李强”这个名字的编号。注意,这个数字和“李强”这个名字的对应关系也是唯一的。类似地,我们假设“得”对应509,“到”对应10032,作为“得到”这个词的编号。这样以一来,每一个中国人的名字,或者汉语的词都可以对应一个数字。

再接下来就简单了,我们建立索引的时候,直接把“李强”存放到第105,004,003个储存单元,把“得到”存放到第15,280,032个储存单元,将来查找时,无论是看到一个词,还是看到一个名字,只要用上面的公式做一次计算,就能直接找到“李强”,或者“得到”在索引中的位置了。这个方法确实快,把原来23次查找变成了一次,但是什么事情都是有成本的,这个方法有两个大问题:
  • 其一,非常浪费。不会有人起名为“猪狗”后者类似的名字,于是对应数字所占据的单元就被浪费掉了(原来如此啊!)。大约会浪费掉多少呢?如果汉字是3万个,每个人都是两字的名字,一共有9亿个不同的编号。再假如北京市不重复的人名是800万个,大约浪费了99%以上的编号(以及对应的内存单元)(99%是怎么算出来的呢?)。这显然不是一个好办法。
  • 其二,也是更糟糕的,当大家齐了三字名,甚至是四字名后,名字对应的编号就可能非常大,以至于超出计算机的存储范围。


所以,问题一方面是浪费,另一方面是空间不够用。为了解决问题,我们就要用到第二个方法了。方法二,只保留编号的尾数。

#方法二
我们注意到无论是“李强”的编号,还是“得到”的编号,都特别长,这么长的编号是不太会重复的,那么稍微短一点行不行?比如我们不管编号多少位,只保留最后的7位数字,也就是说将编号的范围从9亿缩小到1000万。由于北京市只有800万不同的人名,照理说准备1000万个代号是够用的,之所以不够用是因为不同的人名计算出的编号,位数可能恰巧重复,这种情况并不少见。那么接下来怎么办?这其实也是我给你的问题。通常这时候人会有两种态度,一种是退回来,另一个种是遇到问题,解决问题。

在Google时,每当下属对我讲什么事情有苦难时,我一般会先判断一下能解决的可能性有多大,如果我觉得还是能解决的,就会对他们说,“遇到问题,解决问题,这时候正是显示你们科班出身的工程师水平的时候,否则你和半路出家的人有什么区别?”几乎所有的时候,他们发挥主动性,问题还真就解决了。对于上述问题,当年研究算法的科学家们也是本着这个态度解决问题的。具体讲,就是在尾号出现相同的情况时,想办法找到一个没有那个词或者名字对应的尾号,作为备选方案。我们既然有1000万个代号,只有800万个名字,这个备选的号码,一定是能够找到的。

为了便于你理解其中的原理,我们不妨看这样一个例子。假如火车站买票时是随机安排座位的,到了火车上,一定有一些人拿到相同的座号。但是,但是如果火车能载1000人,只卖了800张票,一定有办法安排每一个人就座的。具体的做法是,先来的先坐下,如果后来的发现自己的票上的座位已经被占据了,那么没关系,找最近的坐下即可(不是等到所有人都坐下,被占座的被统一安排到空余座位上)。如果火车上真的有20%的空座,大家其实都能在附近找到一个空座。在计算机中,安排这种相同位数的编号的方法和火车上安排座位的原理是一样的。当然,对于任何事情,我们都应该问问,是否还有更好的方法。对于这个问题也是有的,那么就要讲到方法三了。

#方法三
方法三,随机指定一个名字或者词语的编号。我们在方法一和方法二中,其实是按照一个公式,将人的名字或者一个词,变成一个编号的,然后再取它的尾数。这时,两个不同的名字有可能得到相同的编号尾数。后来计算机科学家们发现,如果随机地给每个名字,后者词语进行编号,重复的可能性最小(hmmmm,为什么呢?)。于是,计算机科学又有了一个小分支,如何产生伪随机数(Pseduo-Random Nubmers)。为什么说是伪随机数呢?因为它们并非真的随机,只是看上去非常像随机产生的。至于为什么随机的比确定性的好,我们这里就省略了,大家记住这个结论就好。伪随机数想要像真的随机数,就需要懂得很多数学原理,于是很多数学家也就加入了这方面的研究。后来,数学家和计算机科学家们发现,如果一个信息(比如名字或者词语),对应的伪随机数足够长,别人是无法通过这个数字还原出来原来的信息的,但是产生这个伪随机数的人却可以(Jezz,这个好有意思啊)。于是,这个方法就能用来进行数据加密。当然,这里面还有一个问题,如果加密的人和接受到信息后解密的人不是一个人,解密的人需要知道加密的方法。如果这个方法给了对方,万一泄露了出去,就麻烦了。后来,数学家们想出了一个不让对方知道自己怎么加密,却能够让某个信息解密的方法。这种方法在密码学上被称为公开密匙,今天大部分加密算法都采用这种技术。

比特币产生的算法,外面的人是不知道的,即使挖币的矿工也不知道,否则你就自己能制造比特币了。产生比特币的过程,和我们说的将“李强”对应一个数字类似,它要产生一个比特币对应的随机数,也被称为私钥(不公开的),谁拿到它,就拥有了比特币。这个随机数不能丢,否则比特币就不是你的了。那么大家怎么知道你的比特币是真的呢?比特币协议还会产生一个公开的秘钥,它可以用来验证比特币的真假。你可以把比特币产生的协议看成印钞机,它怎么印钞,不能让你知道。而比特币的公开秘钥,则相当于验钞机,你可以拿它验证比特币的真伪。如果验证完了确认为真,你瘦了那个比特币,私钥就归你了(哎,怎么保证不泄密啊),当然,比特币的所有权和使用权就给了你了。

​
我们从今天查找讲到比特币,内容跨度很大,我把他们总结如下:
  • 1. 从查找到比特币,很多技术背后的道理是相同的,这也就是我喜欢讲原理,不喜欢讲具体的实战技术的原因,原理搞懂了,一通百通。一些朋友讲,能不能将一些我明天就用得上的内容。非常抱歉,我只能说他们找错人了。我希望我的读者朋友都是能举一反十的,不是死记硬背方法的。
  • 2. 我们今天的内容是一层层递进的,这样讲的目的是要强调一种做事情的方法,就是遇到问题解决问题。(层层递进 —》 等于遇到问题解决问题。)
  • 3. 今天我们队对急性和随机化开了一个头,今后我们还会讲到相关的内容。从随机性在一些领域比确定性的好处,我们应该了解,世界上很多时候,好和坏和我们想象的不一样,而且这种客观性不随我们的好恶改变。
  • 4. 回顾这一周的内容,我们讲查找信息的成本从几千万次,甚至十多亿次降到了几十次,又通过随机化降到了几次,甚至是一次直接成功,这也说明了技术无止境,我们队自己的要求也不该有止境。


有了这些铺垫,接下来可以讨论一些技术性较强的Google面试题了。

































Comments are closed.
  • Home
  • Growing n Evolving
  • Competence Circle
    • Philosophy >
      • Her
      • Quotes
      • Day One
      • Wu Jun
      • Outside >
        • There
      • North Star
    • Analyzing >
      • Investment >
        • Primary Market
        • Secondary Market
        • Cryptocurrency
      • Companies >
        • Meitua美团
        • Amazon
        • Amino Capital
        • Alphabet >
          • Jeff Bezos
        • Berkeshire Hathaway
        • Tesla
        • JD
        • Microsoft
        • Apple >
          • Steve Jobs
        • Nvidia
        • SpaceX
        • Blue Origins
        • Softbank
        • Alibaba
        • Tencent
        • Huawei华为
      • Industries / Sectors >
        • P1 >
          • Mining
          • Healthcare
          • Supply Chain
          • Retailing
          • Blockchain
          • Cloud Computing
          • AR/VR/MR
        • P2 >
          • Aerospace
          • Computer Vision
          • Autonomous Vehicle
          • Manufacturing
          • IoTs
      • Figures/Stars
      • Designs /Aesthetics >
        • Designers >
          • Jony Ive
        • Products
        • Houses
        • Apartments
        • Cars
        • Swords
        • Aircrafts
        • Spacecrafts
      • Civilizations >
        • Egypt
        • China
        • Greece
        • Baylon
        • Persia
        • Rome
        • Carthage
        • Arab
        • Japan
        • Spain
        • Italy
        • Portugal
        • France
        • Germany
        • Kievan Rus
        • Russia
        • Sweden
        • United Kingdom
        • Netherlands
        • Uniited States
        • Singapore
    • Coding >
      • SQL
      • Python
      • R
      • Data Visualizations
    • Numbers >
      • Statistics
      • Probability
      • Logic
      • Linear Algebra
      • Matrix
    • Languages >
      • Chinese
      • English
      • Japanese
      • German
      • Russian
      • Swedish
      • Latin
    • Physical >
      • Kendo
      • Workout >
        • Health
      • Mixed Fighting
      • Shooting
  • About Me