# NoPoint 算法入门笔记 - 11 - where to go next | further learning

gitCavendish · 2018年05月09日 · 最后由 gitCavendish 回复于 2018年05月09日 · 679 次阅读

#### 主要内容

• Trees - 树（一种数据结构）
• Inverted indexes （反向索引）
• The Fourier transform （傅里叶变换）
• Parallel Algorithms （平行算法）
• MapReduce
• Bloom filters and HyperLogLog
• The SHA algorithms （Secure Hash Algorithm）
• Locality-sensative hashing - 局部敏感hash function
• Diffie-Hellman key exchange 迪菲-赫尔曼密钥交换
• Linear programming - 线性规划

#### 1 Tree

Tree (data structure), a widely used computer data structure that emulates a tree structure with a set of linked nodes

Tree(数据结构)，指的是一种广泛应用的计算机数据结构，它使用一系列相互连接的节点构成一种类似自然界的树的结构。

binary search tree

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

Algorithms (4th Edition) 4th Edition
by Robert Sedgewick,‎ Kevin Wayne

sorted array 的insertion/deletion操作会是 O (n), 而binary search tree 的 insertion/deletion操作的算法复杂度是 O(log n), 这一点上快了很多。

downsides

binary search tree 还有很多变种形式，那些是应用中使用较多的？ B-tree是一个例子。其他相关的例子还有

#### 2 Inverted indexes 反向索引

https://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95

``````0: "it is what it is"
1: "what is it"
2: "it is a banana"
``````

``````"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}
``````

#### 3 The Fourier transform

https://en.wikipedia.org/wiki/Fourier_transform

“The Fourier transform is one of those rare algorithms: brilliant, elegant, and with a million use cases.”

https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

“The Fourier transform tells you exactly how much each note contributes to the overall song. So you can just get rid of the notes that aren’t important. ”

#### 4 Parallel algorithms 平行算法

• MapReduce
• Bloom filters
• HyperLogLog

1 Overhead of managing the parallelism

##### 4.1 MapReduce

“Distributed algorithms are great when you have a lot of work to do and want to speed up the time required to do it. MapReduce in particular is built up from two simple ideas: the map function and the reduce function.”

map

The map function is simple: it takes an array and applies the same function to each item in the array.

reduce

The idea is that you “reduce” a whole list of items down to one item. With map, you go from one array to another.

ruby 中的map和reduce

``````2.5.0 :003 > array = [1,2,3,4]
=> [1, 2, 3, 4]

2.5.0 :005 > mapped = array.map { |e| e**2 }
=> [1, 4, 9, 16]

2.5.0 :009 > reduced = array.reduce { |acc, e| acc + e**2 }
=> 30
``````

MapReduce就是基于这两个简单的概念跨计算机执行复杂的数据查询，当你有一个很大的数据集时，MapReduce可以让你把查询时间从传统方式的几小时缩短到几分钟。

##### 4.2 Bloom filters and HyperLogLog

https://zh.wikipedia.org/wiki/Bit.ly

https://zh.wikipedia.org/wiki/%E7%B8%AE%E7%95%A5%E7%B6%B2%E5%9D%80%E6%9C%8D%E5%8B%99

##### 4.2.1 Bloom filters

Bloom filter是一个基于概率的数据结构，他用来判断一个对象是否在某个数据集中。和hash table查询不同，bloom filter 只能告诉你一个很可能的答案，或说大概率上正确的答案。

• 回答可能是 False positive的，也就是错误的判断给出的 item 已经包含在数据集中，而实际上没有
• 回答也可能是 False negative的，也就是错误的判断给出的 item 不在数据集中个，而实际上在数据集中

##### 4.2.2 HyperLogLog

HyperLogLog 可以估算数据集中 unique elements 的数量。和 bloom filter 一样，HyperLogLog 给出的也是一个近似的答案，但它只占用很少的内存。如果你有一个很大的数据集用于查询，而你可以接受一个近似的答案，你可以查找probalilistic algorithms基于概率的算法的相关内容。

#### 5 The SHA algorithms

SHA代表 Secure Hash Algorithm，也就是安全散列算法，这个术语中的 hash 不再指代hash function, 而是指 '散列'，也就是经过 SHA 这个hash function 计算后得出的一个字串。

• hash table 中的hash function是给出string返回位置
• SHA 本身就是一个hash function, 他也是接受一个string, 但返回的是一个经由SHA计算的 hash 散列。

http://ruby-doc.org/stdlib-2.5.0/libdoc/digest/rdoc/index.html

``````2.5.0 :002 > require 'digest'
=> true

2.5.0 :003 > Digest::SHA2.new(256).hexdigest 'abc'

2.5.0 :004 > Digest::SHA2.new(384).hexdigest 'abc'
=> "cb00753f45a35e8bb5a03d699ac65007272c32ab0eded1631a8b605a43ff5bed8086072ba1e7cc2358baeca134c825a7"

2.5.0 :005 > Digest::SHA2.new(512).hexdigest 'abc'
=> "ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f"
2.5.0 :006 >
``````

SHA 是一个家族的算法，包含 MD5, SHA-0, SHA-1, SHA-2, SHA-3。不同的算法应用场景不同，安全性之间也有差别。上面例子中的 256, 384, 512 指的是 output size(bits)，也就是算出来的hash长度，一般来说是越长越安全。

##### 5.1 comparing files

SHA 可以用来比较文件的一致性。比如AB两个人都下载了某个文件，现在二人想校验各自下载的文件是否完全一样，这时如果文件很大不方便传输，那么就可以双方都用 SHA 算出这个文件的 hash, 然后比较这个hash是否一样。

SHA 的另一个应用是用于密码存储，很多应用都涉及到存储用户密码。如果gmail被黑客攻击了，拿到了数据库中所有的用户信息，那么黑客是否能进行进一步的操作？

SHA 是一个 `one-way` 也就是单向的SHA，给出 string 可以算出 hash, 但反过来从 hash 出发是无法算出原始的 string 的。

##### 5.3 SHA 的 locality insensative 特性

SHA 算法有一个特点是，如果给出的字串只有少量的不同，算出来的 hash 就完全不同。这种特性可以描述为对局部变化不敏感。

``````2.5.0 :004 > Digest::SHA2.new(256).hexdigest 'abc'

2.5.0 :005 > Digest::SHA2.new(256).hexdigest 'Abc'
=> "06d90109c8cce34ec0c776950465421e176f08b831a938b3c6e76cb7bee8790b"
2.5.0 :006 >
``````

wikipedia

In computer science, SimHash is a technique for quickly estimating how similar two sets are. The algorithm is used by the Google Crawler to find near duplicate pages.

• 一个老师可以使用 SimHash 来检查学生提交的作业是否有抄袭嫌疑。
• Scribd （一个电子读物订阅网站）允许用户上传文档或书籍与其他人共享。这时它就可以使用 SimHash 来检查用户上传的内容是否存在版权侵犯嫌疑或与之前的内容重复。

“Simhash is useful when you want to check for similar items.”

#### 6 Diffie-Hellman key exchange

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Diffie-Hellman 解决了这个问题。

• 双方都不需要有个密码本，也不需要见面交换这个密码本
• 被加密的信息极难被破解

Diffie-Hellman 加密有两个key, 一个是 public key， 另一个是 private key

public key 可以公开发送给你的朋友，或其他人，你不需要隐藏他。 当你的朋友想要发送信息给你的时候，他们会用这个 public key 来加密信息，当你收到这个加密信息后，可以使用 private key 解开这个信息。而你是唯一拥有 private key 的人，所以只有你能揭开加密后的信息。其他人能做的只是将信息加密。

Diffie-Hellman 算法依旧在使用，比如继承他思想的加密方式 RSA。

#### 7 Linear programming - 线性规划

• 你的公司生产两种产品，T恤和手提包，做一件T恤需要1米的织物和5个纽扣，做一个手提包需要2米的织物和2个纽扣，你有11米的织物和20个纽扣。每件T恤能赚2美元，每件手提包能赚3美元。你应该怎么分配生成以达到利润最大化？ 这里你试图最大化利润，而被原料的数量限制。
• 你是一个政客，你想要最大化你的投票数量。你的研究显示，你平均需要花费1小时的努力以及2美元能获得一张来自SF的选票，需要花费1.5小时以及1美元获得一张来自芝加哥的选票。你的可用时间是50天，你的总预算是 1500美元，你应该怎么分配时间和金钱资源以获得最多数量的选票？ 这里你有两个限制，时间和钱。

### The end

##### 此贴已暂时被屏蔽!

1. 标题/正文描述不清不楚;
2. 无意义的发帖;
3. 存在广告嫌疑；
4. 招聘信息描述不清楚，未按照招聘节点的要求发帖，或职位信息不符合社区用户群需求；
5. 新注册的帐号发布产品推广贴是不允许的哦，付出和回报是相等的，当然如果你的产品确实非常有意思，或是和 Ruby 有关的东西，是不会进入这个栏目的。
6. 太过弱的提问会被直接转移到此节点，请在提问前多尝试，多搜索；
7. 理论上，不允许发布 QQ 群、微信群之类讨论群。

• 排版请按 Ruby China 的 Markdown 格式要求，具体请认真阅读: 排版指导，并参考 这篇招聘 的排版;
• 招聘内容过少，缺少公司介绍，产品介绍，职位介绍，或待遇，工作地，联系方式等必要信息；
• 重复发帖（一家公司每月限制只能发一次招聘）；
• 专业不对口（个别不对口，但有特点的，我们会放过）；

jasonliu 回复

ok

lidashuang 回复

gitCavendish 回复

Rei 内容不符合版规屏蔽此话题 05月09日 23:27

Rei 回复