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

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.

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