第四堂:「Data Wrangling」

有陣子沒寫了,來還個債...

這個系列是從『MIT 的「The Missing Semester of Your CS Education」』這邊延伸出來的,這邊講的是「Data Wrangling」這篇。

這篇是在講 pipe 的用法,在講這些工具之前,其實有個很重要的概念應該要說明 (但沒有在這篇文章裡被提到),也就是 Unix philosophy,這個哲學是指 unix 環境下的工具,都會設計成只做好一件事情。

而要怎麼把這些工具串起來,最常見的就是 pipe,你可以在文章裡看到 grepsedsort 這些工具的用法,以及怎麼用 pipe 串起來。

這邊剛好也可以提一下,利用 pipe 可以把不同功能打散到不同的 process 上,剛好也可以稍微利用到現在常見的多 CPU 的環境。

另外上面因為提到了 grep,文章內花了不少篇幅在講 Regular expression 這個在 CS 課程裡面也是重要的基礎。

會放這種篇幅長度,一方面是 Regular expression 的實用性很高,另外一方面,學術上與自動機理論中的 DFANFA 都有關,算是學習計算理論的起點:

然後後面就有提到 AWK 這個工具,這邊要注意的是,雖然可以用 Perl 之類的工具作到類似的事情 (而且更強大),但 AWK 有被放到 POSIX 標準裡,所以在各種作業系統內幾乎都一定會出現,加上語法算是簡單,學起來還是很有幫助...

然後再最後面的段落冒出一個 gnuplot 畫個圖,以及示範 xargs 這種神器要怎麼用 (這邊會更建議看一下 manpage,可以配合 find 之類的工具用,並且平行化同時處理)。

然後最後示範了 binary data 怎麼處理。

Amazon Redshift 會自動在背景重新排序資料以增加效能

Amazon Redshift 的新功能,會自動在背景重新排序資料以增加效能:「Amazon Redshift introduces Automatic Table Sort, an automated alternative to Vacuum Sort」。

版本要到更新到 1.0.11118,然後預設就會打開:

This feature is available in Redshift 1.0.11118 and later.

Automatic table sort is now enabled by default on Redshift tables where a sort key is specified.

重新排序的運算會在背景處理,另外帶一些行為學習分析:

Redshift runs the sorting in the background and re-organizes the data in tables to maintain sort order and provide optimal performance. This operation does not interrupt query processing and reduces the compute resources required by operating only on frequently accessed blocks of data. It prioritizes which blocks of table to sort by analyzing query patterns using machine learning.

算是丟著讓他跑就好的東西,升級上去後可以看一下 CloudWatch 的報告,這邊沒有特別講應該是還好... XD

引用自己論文的問題...

Nature 上點出來期刊論文裡自我引用的問題 (這邊的自我引用包括了合作過的人):「Hundreds of extreme self-citing scientists revealed in new database」。

開頭舉了一個極端的例子,Vaidyanathan 的自我引用比率高達 94%,而學界的中位數是 12.7%,感覺是有某種制度造成的行為?

Vaidyanathan, a computer scientist at the Vel Tech R&D Institute of Technology, a privately run institute, is an extreme example: he has received 94% of his citations from himself or his co-authors up to 2017, according to a study in PLoS Biology this month. He is not alone. The data set, which lists around 100,000 researchers, shows that at least 250 scientists have amassed more than 50% of their citations from themselves or their co-authors, while the median self-citation rate is 12.7%.

會想要提是因為想到當年 Google 的經典演算法 PageRank,就是在處理這個問題... 把 paper 換成 webpage 而已。

JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡,各種 sort 都沒有保證 stable,而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化,提案在規格裡加入 stable 的要求,可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下,當時還在從 Firebird 轉換名稱到 Firefox 的時期):「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm,之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法,與 Merge sort 的情況類似,除了 stable 外,還可以保證最差的情境下的時間複雜度是 O(n*log(n))

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列,藉此降低記憶體操作次數而提昇效能,符合真實環境裡常見到的資料:

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外,其他常見的包括了 PythonAndroid 上的 Java SE:

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.

對於按讚數排名的方法

前幾天看到一篇 2009 年的老文章,在討論使用者透過「喜歡」以及「不喜歡」投票後,要怎麼排名的方法:「How Not To Sort By Average Rating」。

基本的概念是當使用者投票數愈多時就會愈準確,透過統計方法可以算一個信賴區間,再用區間的下限來排... 但沒想到公式「看起來」這麼複雜 XDDD

Score = Lower bound of Wilson score confidence interval for a Bernoulli parameter

但實際的運算其實沒那麼複雜,像是 Ruby 的程式碼可以看出大多都是系統內的運算就可以算出來。其中的 z 在大多數的情況下是常數。

require 'statistics2'

def ci_lower_bound(pos, n, confidence)
    if n == 0
        return 0
    end
    z = Statistics2.pnormaldist(1-(1-confidence)/2)
    phat = 1.0*pos/n
    (phat + z*z/(2*n) - z * Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)
end

The z-score in this function never changes, so if you don't have a statistics package handy or if performance is an issue you can always hard-code a value here for z. (Use 1.96 for a confidence level of 0.95.)

作者後來在 2012 年與 2016 年也分別給了 SQL 以及 Excel 的範例程式碼出來,裡面 hard-code 了 95% 信賴區間的部份:

SELECT widget_id, ((positive + 1.9208) / (positive + negative) - 
                   1.96 * SQRT((positive * negative) / (positive + negative) + 0.9604) / 
                          (positive + negative)) / (1 + 3.8416 / (positive + negative)) 
       AS ci_lower_bound FROM widgets WHERE positive + negative > 0 
       ORDER BY ci_lower_bound DESC;
=IFERROR((([@[Up Votes]] + 1.9208) / ([@[Up Votes]] + [@[Down Votes]]) - 1.96 * 
    SQRT(([@[Up Votes]] *  [@[Down Votes]]) / ([@[Up Votes]] +  [@[Down Votes]]) + 0.9604) / 
    ([@[Up Votes]] +  [@[Down Votes]])) / (1 + 3.8416 / ([@[Up Votes]] +  [@[Down Votes]])),0)

而更多的說明在維基百科的「Binomial proportion confidence interval」可以翻到,裡面也有其他的方法可以用。

Go 1.6 把 HTTP/2 變成預設支援的功能

Go 的官方公告「Go 1.6 is released」提到了把 net/http 的 HTTP/2 預設啟用了:

In Go 1.6, support for HTTP/2 is enabled by default for both servers and clients when using HTTPS, bringing the benefits of the new protocol to a wide range of Go projects, such as the popular Caddy web server.

另外值得一提的是 sort 演算法的效能改善:

The algorithm inside sort.Sort was improved to run about 10% faster, but the change may break programs that expect a specific ordering of equal but distinguishable elements.

這應該算還蠻基本常用到的東西,會改善很多程式效能...