Sam Altman co-found 的公司 Open AI 在強化學習 (Reinforcement Learning)上有了進展

http://blog.samaltman.com/reinforcement-learning-progress

Sam Altman co-found 的公司 Open AI 在強化學習上有了進展，證明專精於特定領域的強化學習演算法可以有效的解決問題，在這篇文章中 Dota 機器人的勝率已經高達 95%


強化學習被稱作「近似動態規劃」（approximate dynamic programming，ADP）

https://zh.wikipedia.org/zh-tw/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0

bcrypt, devise, and rails secret_key_base

devise 用 secret_key_base 當作產生 token 的依據
devise 用 bcrypt hashify password 然後儲存
rails 的 has_secure_password 也是用 bcrypt 實現


bcrypt() is a hashing algorithm designed by Niels Provos and David Mazières of the OpenBSD Project.


題外話，如果要改 secret_key_base ，那 devise 裡的token, 包含confirmation, reset_password 都會 invalid 需要重新生成。

https://github.com/codahale/bcrypt-ruby
https://coderwall.com/p/sjegjq/use-bcrypt-for-passwords

拓撲排序 - Topological Sorting

上一篇講到 DAG 有向無環圖 - Directed Acyclic Graph

這篇來研究 拓撲排序 - Topological Sorting

這篇文章講得很清楚：

https://songlee24.github.io/2015/05/07/topological-sorting/

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

就是在 DAG 中找到只出不進的點，然後移除，然後再繼續找只出不進的點移除，這樣依序移除的順序就是 拓撲排序

上面的排序就是 1 -> 2 -> 4 -> 3 -> 5

一个有向无环图可以有一个或多个拓扑排序序列。

DAG - 有向無環圖 - Directed Acyclic Graph

最近想要研究一下 IOTA 在幹嘛，看到有中文翻譯白皮書 ：https://hackmd.io/c/rkpoORY4W/https%3A%2F%2Fhackmd.io%2Fs%2FryriSgvAW

裡面提到 DAG 有向無環圖 - Directed Acyclic Graph

先看一下定義：

在圖論中，如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖（DAG圖）。

https://zh.wikipedia.org/wiki/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE

就是出去後就沒辦法繞回來的意思，這張圖很明顯：

常見的「拓墣排序」好像就跟這個有關，有人提到 ETH 好像也有用到這個概念

拓扑排序，我们可以从寻找图中节点之间的路线，最短，以及最长的路线。通过动态规划，无论这张网多么庞大，都能以较快速度将结果正确计算出来。

比如闪电网络，ETH智能合约，为了找到正确的交易线路，使用DAG，拓扑来寻找路线

關於拓撲排序：

https://songlee24.github.io/2015/05/07/topological-sorting/

終於在工作中實際用到了紅黑樹 - 交易所配對引擎

首先了解紅黑樹跟一般的二分查找樹的區別可以看下面連結中的漫畫，清楚明瞭：

https://mp.weixin.qq.com/s/0RKuO0Pk7R09wGzgyA43mw

簡單來講最大的差別在於

二分查找樹有可能會左右極度不平衡，造成查找時效率變慢
而紅黑樹有自平衡系統，可以確保樹的深度是平衡的，缺點是增加或是減少節點時會比較耗資源


最近在開發交易所，研究了 Peatio 的交易所撮合引擎，其中有一段就有用到紅黑樹

確切的 code 在這：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L11

所以不禁就想問為什麼這邊要用紅黑樹呢？

原因就是因為在這個演算法中我們是根據 order 的 price 來當排序，假設交易所的 orders 中我們第一個 laoding 進來的 order 是最便宜的或是最貴的，那麼用 binary tree 就會變成左右極不平衡的情況，造成搜尋效率低落，相對的如果用紅黑樹就可以讓整個樹長成左右平衡的大樹，這樣搜尋效率就比較高。

其實 base on 演算法的實作，在 peatio 的演算法中是把 orders 一次 load 進 memory 裡面，所以只有在第一次 loading orders 的時候會花很多資源在紅黑樹自平衡，但一但 loading 完之後大部分的時候都會是在查找 order 而不是新增刪除 order，所以這樣的設計是比較合理的。

查找 order 的部分：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L44

摘要算法和對稱加密算法

摘要算法不可逆，對稱加密可逆

所謂對稱加密就是用私鑰（也就是密碼）幫訊息加密，所以只要再用私鑰就能解密，例如 AES 算法

而摘要算法呢？就是沒有私鑰的概念，只要是一樣的字串加密出來的內容就會是一樣的，但是摘要算法會確保加密出來的字串無法（應該說：很難）被逆推回原本的值，所以常常用來做 API 訊息的驗證，常見的算法有 MD5 和 SHA 系列

由於以上特性，對稱加密通常用來保護隱私相關的東西，而摘要算法則是確保文檔的正確性，以下舉例說明用法

對稱加密：

最長用來做點對點加密，確保中間人不能得到訊息原文，可以用作在通訊軟體加密

摘要加密：

常用在 API 訊息認證，最常用的作法就是在要傳送的 Params 時多加 API key 到的 Params 裡面, 由於攻擊者不知道公鑰所以即使要竄改 params 內容也沒辦法重新產生正確的加密字串

蒙地卡羅演算法

很簡單易懂的介紹，很棒

原理就是產生極多數的樣本，根據樣本的分佈狀態來預估真實狀態

其中交通堵塞的例子真的是很經典，很久以前就聽過但不知道是用蒙地卡羅演算法證明的

http://mp.weixin.qq.com/s/Ca6-zfA3LzijrMFhJcfnMA

B+ tree (B plus tree)

前一篇學習了 什麼是 B- balance tree，立馬再來補習一下 B+

其實 B+ tree 就是 B- 的升級版

主要的差別在於「子節點有母節點的資訊」，並且「出現在子節點中的母節點元素都是子節點中最大的元素」，不囉唆，看圖：

我們看第三層的所有子節點可以發現，每個子節點最右邊（也就是最大）的元素都是母節點的元素

如此一來就變成一個依照順序排序的子節點

優點：

1. 可以減少 IO 次數，因為子節點有所有的 data，母節點只有索引而已
2. 在做範圍查詢的時候，B- 如果查詢的範圍橫跨節點的兩邊就必須要先走左邊再走右邊去查資料，但 B+ 可以在最底層的子節點往右邊直接找就行了（因為子節點有所有的 data）
3. 更矮胖
4. 所有查詢都要查到子節點，代表查詢的速度比較一致，不會有些快有些慢（穩定性高）（相對的也可以說成是「一樣快」或是「一樣慢」）



圖片以及資訊來源：
http://mp.weixin.qq.com/s/cK_GIhCuGoUwJpDpoaETxw

什麼是 btree (balance tree) (b-)

常常看到 postgresql 的 index 都是用 btree 的方式 index，但一直沒時間去研究什麼是 btree，最近發現一個不錯的維信號用漫畫的方式解釋各種演算法相關的東西，剛好看到 b- b+ 的介紹，該是時候學習一下了～


所謂的 b- 其實唸作 balance tree 或是 b tree，是跟二元樹有點相關的東西，但最大的差別在於他每個節點最多可以包容兩個值，這樣做的原因是如果我們用二元樹來下 index，雖然時間複雜度很低，但是由於每個節點都寫入在硬碟的不同位置，一旦運氣不好我們要找的節點剛好是在樹的最底端，那硬碟就要從最上面的節點一路讀取到最下面的節點，雖然時間複雜度低但是硬碟讀取的效率差，為了讓硬碟讀取的次數變少於是有了 b- 的結構。

b- 讓一個節點可以容納兩個數值，如此一來下面就可以有三個節點，並且可以在節點內定位省了一次到不同硬碟空間的時間。

另外新增刪減節點的時候也是比較耗時的，為了確保最有效率地運作，新增刪減節點是有機會去更動到母節點的

總之 postgres 是預設使用 btree，瞭解一下更清楚自己平時在做什麼事ＸＤ

另外也寫了一篇 關於 B+ tree的介紹


圖片和資訊來源：

http://mp.weixin.qq.com/s/raIWLUM1kdbYvz0lTWPTvw