[TIL][文章推薦] 設計高效能的 Hash Table

原文

Felix Chern: 設計高效能的Hash Table(一)

心得

還記得當初在寫 Consistent Hashing 的時候,一直不願意拿人家寫好的 Hash Function 來改,硬要自己寫一個.

結果發現寫出來的 Hashing 一直出問題.才知道原來 Hash Function 是實作 Consistent Hashing 的一個重點.

這一篇文章有了一些基本對於 Hash Function 的介紹,也把幾個好用的 Hash Function 一一的列出來.

其中包括了最近被移到了 Google 的 “highwayhash”

或是之前有介紹過在 Uber/ringpop 下作為 Consistent Hashing 的 farmhash

這篇文章相當推薦,原因如下:

  1. 作者 (Felix Chern) 目前似乎在 Google 工作,部落格文章都相當有深度.
  2. 有 Hash Function 列出的清單並且有簡單的介紹.

參考:

  • ringpop 是 Uber 的去中心化 App :
  • 這篇文章有下集,在這裡

關於實作與相關測試:

其實 Damian Gryski 實作了不少 Hash Function 的 Go 套件

HighWay Hash

其 Benchmark 如下:

 ~/s/g/s/g/d/go-highway   master  go test -bench=.             六  4/29 01:31:56 2017
BenchmarkHighway8-8    	50000000	        26.3 ns/op	 304.36 MB/s
BenchmarkHighway16-8   	50000000	        26.7 ns/op	 599.24 MB/s
BenchmarkHighway40-8   	50000000	        29.7 ns/op	1345.35 MB/s
BenchmarkHighway64-8   	50000000	        33.3 ns/op	1924.53 MB/s
BenchmarkHighway1K-8   	10000000	       137 ns/op	7452.07 MB/s
BenchmarkHighway8K-8   	 2000000	       873 ns/op	9378.40 MB/s

Farm Hash

其 Benchmark 如下:

 !  ~/s/g/s/g/d/go-farm   master  go test -bench=.    257ms  六  4/29 01:30:43 2017
BenchmarkHash32-8    	20000000	       100 ns/op
BenchmarkHash64-8    	20000000	        58.2 ns/op
BenchmarkHash128-8   	20000000	       123 ns/op

xxHash

這不是 Damian Gryski 實作的,是由 LiftOff Caleb Spare 但是做得很好而且也有被 InfluxDB 使用喔.

xxHash 是選定 64bit 輸出的通用 Hash Function ,使用範圍廣泛而且速度快.

結語:

本來想只是寫個簡單的推薦文,後來決定來跑跑看每個 Hash Function 的效能評比.跑完之後,又想去偷看是不是裡面都沒有使用除法.

發現其實 Hash Function 主要還是針對不同 CPU 的優化,讓他們的速度能夠更快.處理的資料類型能夠更多.

P.S.:

  • 其實 Damian Gryski 把幾乎所有 Google 出品的 Hash Function 都重寫成 Golang 版本.

  • Google 出了好幾個的 Hash Function 讓我覺得大公司對於 Hash Function 的注意.

[TIL] Chatbot Day Quick Note

Talks

聊天機器人與對談式商務的未來發展 - Clement Tang

  • Chatbot situation and chatbot types.

Chatbot的智慧與靈魂 - 陳縕儂 – 台大資工系助理教授

  • 前半段:
    • 討論 AI Bot 的分別與差異,目前的 Chatbot 主要都專注在 Conversation .
  • 後半段:

運用對話機器人提供線上客服服務 -Herman Wu -微軟技術傳教士

突破 Facebook messenger platform API 限制 張家豪 - Ucfunnel 工程

Her/Him Her/Her

  • 匿名聊天
  • 貼圖也可以傳
    • 一般 Chatbot 無法傳貼圖
    • 變通方式轉貼截圖
    • Solution:
      • facebook-chat-api can convert AP_ID FB_ID
      • facebook-chat-api can get stick_id
  • 話題產生器
  • 產生交友行為 (交換 FB ID)
    • 一般來說只能拿到 AP_ID 無法拿到 FB_ID
    • Solution:
      • facebook-chat-api to convert it.
  • 如何在 24 小時後回話
    • 在 FB 超過一天 Chatbot 會失敗
    • Solution:
      • Use facebook-chat-api ping if user block
      • If not, we could renew conversion window (TBC)

facebook-chat-api

link

  • Help to convert AP_ID <-> FB_ID

Chatbot 智能溝通策略流程規劃與實做,以電子商務為例 - 戚務漢 - EXMA-Square RD&PM

  • mCommerce 時代來臨,消費習慣的改變

以聊天機器人檢驗與提升服務品質 - 劉明機(機哥)

  • 谷阿莫: 一個創新服務的例子
  • 情感字庫
    • HowNet
    • LIWC http
  • Label Propgation
  • Affinity propagation
    • Input: N*N array
    • Outpu: Label and feature sample.

程式設計週記[2017/04/21]: Golang 可以做的事情越來越底層了

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

  • 主要會貼一些github,但是會盡量寫上一些有用的評語(或是我容易想到的關鍵詞)幫助以後查詢

網路文章心得:

  • 會寫些心得,強迫自己閱讀.

“程式週記”並且定期週期性更新.

大部分內容在我的twitter都會有,這邊只是將一些簡單的心得與感想註解一下.

本週摘要

到了四月了,當初不小心把兩個分享都排在四月,於是又要準備兩個投影片.重要的是, Chatbot Day 的部分還有不少的 code 要準備.



Go

schollz/linkcrawler: Cross-platform persistent and distributed web crawler

是一個跨平台具有分散式與一致性的網頁爬蟲工具.具有可以一次將多個目標全部分散給各個 client 來抓取的功能.充分使用到 Golang 許多的特性,可以好好來看看

justForFunc

justForFunc 是由 Google 傳教士 - Francesc Campoy 所主持的 Youtube 頻道,裡面的內容都是講解 Golang 相關的部分,歡迎大家來訂閱.

此外: Google Cloud Platform Podcast 也是 Francesc 的另外一個的項目,主要就是 Google Cloud Platform 的 Podcast .這也是我經常收聽的. Francesc 跟 Mark 的對談很有趣

Introducing NATS to Go Developers – Shiju Varghese – Medium

NATS 是一個使用 #golang 建置的分散式 Message Queue 系統 (另外還有一個大家熟知的是 NSQ) NATS 原本是由 Ruby 開發而成,經由 Apcera 改寫成 Golang 之後持續維護的, 這篇文章有著基本的介紹,並且講解如何使用..

Mobile Apps by Pure Go with Reverse Binding

這篇討論一個很有趣的方向,在討論如何從 gomobile 裡面的 golang 語言中如何在呼叫 platform 的 code (ex: Android Java)

做法也很傳統,就是多包一層 cgo -> jni -> java . 真是老方法就是好用…. 不過不知道有沒有雷….

DigitalOcean Hsinchu

這活動不錯… 跟 #Golang 有關,不過地點在新竹… 有 HackMD + appleboy + kubernetes

How We Built Testable HTTP API Server

GoConJP 的投影片,講解如何建置一個可以測試的 HTTP API Server. 很多觀念基礎都有點到,搭配 Golang 語言特性 (built-in testing) 實在很方便.

Introducing NATS to Go Developers – Shiju Varghese – Medium

NATS 是一個使用 #golang 建置的分散式 Message Queue 系統 (另外還有一個大家熟知的是 NSQ) NATS 原本是由 Ruby 開發而成,經由 Apcera 改寫成 Golang 之後持續維護的, 這篇文章有著基本的介紹,並且講解如何使用..

ponzu-cms/ponzu

ponzu-cms/ponzu ( 版主? ) 一個透過 CLI 可以很快速建置起來的 CMS 系統. 透過類似 RoR 類似的指令方式,就可以建立出一個 CMS 並且支援 HTTPS/Server Push #golang .

這個專案這幾天獲得大家的注意,迅速的破了 2K stars . 並且被許多人稱為是最適合 Hackathon 使用的小工具.

mattn/go-mastodon

mastodon 是一個 Ruby 開發出分散式的類似 twitter 的 microblogger 這是 mattn 出的 #Golang client

參考:

periph - Peripherals I/O in Go

對於底層的控制 GPIO 方便如果要使用 Golang ,以往大家都是使用 Gobot 這個專案. 現在 Google 自己把許多底層的控制都寫好了.

介面包括了. GPIO, I2C, SPI, 1-Wire ,並且不需要 C Dependency .



Python

Android/JAVA/NODE.JS



Docker

“如何寫出一個好的 Dockerfile”

這一份深入淺出的教學,算是把大家對於撰寫 Dockerfile 一些比較容易犯的錯誤跟疏忽的地方做了很詳細的教學. 比如說:

  • 記得寫 .dockerignore 來避免把一些不必要的檔案(或是密碼 XD) 放入 docker container
  • 一個 container 盡量維持只做一件事情
  • 推薦使用 COPY 而非 ADD

還有更多教學,建議深入地看看..

[由於在我 twitter 上受到不少人推.. ,希望轉到這裡能幫到一些人]

Moby issue: A new upstream project to break up Docker into independent components

Docker CTO 親上火線解釋 Moby 到底定位是什麼? Docker CE, Docker EE 到底跟 Moby 的關係是什麼?

這裡有個示意敘述:

  • Moby = open source development
  • Docker CE = free product release based on Moby
  • Docker EE = commercial product release based on Docker EE.

簡單的說… Moby 就是過往 Docker 底層的開放 (Docker CE) 你可以做自己的 Container 格式或是相關處理. Moby 完全是開源,並且 Docker 自己透過 Moby 來開發成 Docker CE (也就是免費版本的 Docker 給一般人使用)

那麼商業用戶呢? Docker 會提供 Docker EE (也就是完全不給你看的的版本)

其實這一步是險棋,但是對於社群與開源而言是大利多.

連一向對 Docker 比較”嚴格”的 Kelsey Hightower‏ 都跳出來誇獎.. “Docker transitioning open source efforts to project Moby is a great move for both the community and the company.”

iOS/Swift



其他程式語言



論文收集



Kubernetes

CloudNativeCon and KubeCon Europe 2017

Cloud Native Con 與 KubeCon Europe 2017 是我這幾天都在關注的一個研討會. 你可以從裡面的講者就知道各大廠商無不希望能在 Cloud Natvie 的世界裡面站上一角. 裡面充滿了許多 Kubernetes 與 Cloud Native 相關的議程(當然.. 因為第一個加入 CNCF 的就是 Kubernetes ) .

目前先推薦一個跟 Kubernetes 相關的 slide ,其他的就等官方公佈出來了…

Brandon Philips 是 CoreOS 的 CTO ,相當的年輕與有能力外.也由於 CoreOS 目前與 Kubernetes 有著深度的整合.可以看看他的講題: Cluster Operations

裡面提到各種 Kubernetes Cluster 架設的方式 1.5 在 AWS 與 Azure 上面一些部署的建議.並且有探討到如何做 Monitor, Backup, Upgrade 與 Scaling 的相關建議,相當實用.

:Slide

虛擬化2.0 ‘‘Kubernetes’’ 容器 Container 再進化

研討會投影片



Machine Learning



網站文章



網站收集



有聲書/影片心得

[TIL] 關於最近風靡日本的服務 Mastodon (長毛象)

網站鏈結

如何注意到這個軟體

Mattn 是一個日本很厲害的 Gopher ,我長期有在關注他的 github 跟 twitter . 一開始先看到這個專案.

https://github.com/mattn/go-mastodon

那時候還不知道叫什麼專案,也沒有任何的說明.只是覺得像是一個 Web API Client

在 Twitter 上大行其道

接下來一堆 tweet 再討論 mastodon ,我才專心的去看了一下. 於是又找到 Poga 的這一篇文章. 架設你自己的 mastodon instance

也才知道 G0v 其實有架設自己的 masdoton 伺服器 g0v.social

究竟 Mastodon 是什麼?

簡單的來說,他就是一個類似 Twitter 的 microblogging service .

它具有去中心化的概念,也就是他的主機並不是一個類似 twitter 那樣集中的伺服器,而是分散在幾個點的伺服器. 比如說台北可以建一台 mastodon.taipei ,高雄也可以建一台.

但是你可以跨伺服器來 follow, reply 跟 reblog .讓整個變得具有自由化與自主性.

而且它具有以下跟 twitter 差異很多的地方:

  • 時間軸按時序顯示文章,不作多餘處理
  • 公開時間軸
  • 每篇文章最多 500 字
  • 支援顯示 GIFV 短片
  • 可逐篇文章調整隱私設定
  • 完善的封鎖使用者、靜音功能
  • 良心設計︰沒有廣告,不追蹤您的使用行為

其中 500 字跟可以每一篇決定隱私權這件事情很對許多 twitter 的胃口. 讓本來風行 twitter 的日本,在短時間內就紅了起來.

在日本紅的主要原因:

要知道他為什麼會紅,這個還是要找到熟悉日本的一些人. 在臉書好友的文章討論串裡面整理出來的原因如下:

  • 因為東西方對兒童色情的認知差很多,Twitter 會封鎖發二次元 H 圖的帳號,很多日本繪師的帳號常常一夜消失.
  • Twitter 只能全公開或全鎖推, Mastodon 可以個別鎖文(類似私噗)、加上內容警示,而且一則可以發500字. 對於使用者自由度比較高.
  • Mastodon 就剛好對上了日本人胃口,然後 Pixiv 又跳下來自己開了Pawoo .
  • 先前有個 Twister ,是基於 P2P 跟 Blockchain 的技術做出來的 twitter clone。 目前還是有在持續開發,可是為什麼沒紅呢? 我覺得關鍵就是 mastodon 可以直接上網註冊使用,而 Twister 則需要下載 client 才能使用。 後者的加入阻力很大。

參考

[研討會心得][GDG] Google APAC Machine Learning Expert Day 分享

投影片:

內容:

今天總算找機會到 GDG 來分享,三月初去新加坡的經驗與分享.內容主要圍繞著以下三個部分:

  • Tensorflow Dev Summit RECAP
  • Some interesting projects during lightning talk
  • How Linker Networks use Tensorflow

由於 Tensorflow 主要有兩大部分的進展,可以透過 Data Engineer 的角度來看 XLA (Accelerated Linear Algebra) ,也可以去了解該如何有效率的設置 Distributed Tensorflow.

另外一個角度,也需要從 Data Scientist 的角度來看 Tensorflow 有多大的進步.於是我也請了公司的 Data Scientist - Ben Chen 一起參加.

由於 GDG (Google Developer Group) Taipei 並不是主要專注在 Machine Learning 相關的社群,這次的部分盡量以帶給大家粗淺的了解為主.

希望大家都能喜歡….

[Go][TIL] Animal Photo Classification Line Chatbot

Line Bot Animal photo classification

為了 Chatbot Day 準備的聊天機器人第二彈.

功能:

很簡單: 就是你上傳動物照片,他就會告訴你是什麼動物.

背後原理:

背後的機器學習模型就是鼎鼎大名的 Tensorflow Inception

註解: Tensorflow Inception 就是一個透過 CNN 建立出來的動物資料庫分類器

架構:

其實這個 Chatbot 還會連接我後端一個 API Server (tf-go-inception) .上面已經將 Inception 訓練好的 model 讀進來.

當你在 Line Chatbot 上面上傳圖片的時候, LineBotAnimal 就會將 圖片透過 multipart 的方式傳到 tf-go-inception 的 API Server

API Server 會將圖片透過 Tensorflow 來預測你的結果,並且傳回給 LineBotAnimal

參考: