Home » Posts tagged "algorithm"

Rust 是不錯啦,不過...

作者寫了一篇「Creating Rust-based NodeJS modules」講同樣演算法 Node.js 要跑 3.5 秒,Rust 只要跑 130ms,所以 Rust 很棒棒之類的...

So about 3.5 seconds for an answer, in web time that is like an eternity. Our algorithm is a very straight forward one, basically just a filter on a large array.

The exact same algorithm, with the exact same CSV and coordinates is now executing in about 130ms.

然後仔細看了一下他的範例,holy...

這讓我想到之前在「看到 zmx 貼了之前的連結,更確信 Uber 的問題不是技術問題了...」這篇提到的文章「Unwinding Uber’s Most Efficient Service」:

很想講「傻逼你先把演算法修好再來怪 Node.js 慢」,程式會愈來愈難維護都是你們這種人引入一堆複雜的東西 -_-

為什麼我還繼續用 RSS (Feed)

最近在一些地方冒出兩篇文章 (應該是 NuzzelHacker News,放在 tab 上好幾天,不是那麼確定來源...),一篇是最近發的「The Case for RSS」,另外一篇是五月的文章「RSS: there's nothing better」。這邊講的 RSS 比較廣義,不侷限於 RSS {0.91,1.0,2.0},而是包括了各式的 feed,像是後來標準化的 Atom

消息的來源大致分成兩種:

  • 已知的來源:這些人只要有新的文章你就會想看。
  • 未知的來源:你可能也會有興趣的文章。

前者你不會想要漏掉 (你就是想看才會訂啊)。而後者在早期有 Zite 這類用演算法推薦的產品,後來在 Zite 併入 Flipboard 整個爛掉後我就跳去用 Nuzzel (透過好友機制推薦,演算法相對單純)。

Facebook 將這兩者混在一起,讓「已知的來源」未必會出現,而是用演算法包起來並且用 PR 手段混淆:美其名稱為「個人化推薦」,實際上是想辦法讓內容提供者掏錢出來。這點在 Instagram 上也可以看到一樣的作法:把 timeline 打散,用演算法包裝起來,再美其名為「個人化推薦」。

而 RSS reader 可以避免「已知的來源」這塊漏掉。

另外也因為 RSS reader 因為設計的目標就是「有效率的閱讀」而不是「賺錢」,所以大多數都會有「已讀」與「未讀」的功能,這讓你同樣的資訊你不需要讀很多次。

而 RSS reader 容易分群閱讀 (有些 RSS reader 會提供 folder 或是 tag 的功能) 也讓你可以帶著不同的 mindset 看不同群的文章,像是科技類的文章與心靈雞湯文就可以分開。

強制 Facebook 的「時間軸」依照時間排序

TechCrunch 的「How I cured my tech fatigue by ditching feeds」這篇提到了 Social Network 成隱的問題:

Many people have deleted the Facebook app from their phone to avoid this mindless habit. “What’s going on in my feed?” they think. Then they scroll, scroll, scroll, get bored and close the app. Repeat this process every 30 minutes. Deleting the app is the best way to take a stance and say that Facebook is a waste of time.

砍掉 Facebook 是一個還不錯的方法,但如果還是有使用 Facebook 需求,就只好想辦法降低 Facebook 帶來的影響。其中我找的方法是強制切到 Most Recent 版本,降低 Facebook 演算法的介入。

昨天剛好在重新處理機器,發現之前用的那個 Google Chrome 套件不見了,只好找看看有沒有替代方案,後來翻到這個:「Facebook Most Recent News Feed」。

如果看裡面程式碼,其實做的事情很簡單,就是硬切過去:

chrome.webRequest.onBeforeRequest.addListener(
    function(info) {
        if (info.url === 'https://www.facebook.com/') {
            return {
                redirectUrl: 'https://www.facebook.com/?sk=h_chr'
            }
        }
    }, {
        urls: [
            "https://www.facebook.com/*"
        ],
        types: ["main_frame"]
    }, ["blocking"]
);

當然,如果能考慮整個移除的話也是不錯啦...

Amazon 的多變數最佳化

在「An efficient bandit algorithm for real-time multivariate optimization」這邊提到了 Amazon 不是走傳統的 A/B testing,而是同時進行多變數的最佳化:

Consider the problem of trying to find a near-optimal version of a promotional message such as this one, which has 5 variable parts and 48 different combinations in total.

在這樣的測試數量下,作者預估需要 66 天才能夠得到有效的結果,而這也表示當變數更多的時候問題就更大了:

Based on the Amazon success rate and traffic size, the authors calculated it would take 66 days to conduct a 48 treatment randomized experiment. Often this isn’t practical.

也就是開頭提到的,如何一個禮拜就提昇 21% conversion rate:

Aka, “How Amazon improved conversion by 21% in a single week!”

作者也提到了這個方法其實打臉了他先前提到的另外一篇論文,在 2014 年提出測試應該要盡可能簡單 XDDD:

Yesterday we saw the hard-won wisdom on display in ‘seven myths‘ recommending that experiments be kept simple and only test one thing at a time, otherwise interpreting the results can get really complicated.

只能說狀況愈來愈複雜,導致需要新方法解決問題。而且這些電商會遇到在測試時不同的 factor 之間有可能會有相依性 (也就是說這些 factor 不是 i.i.d.),你用本來的方式反而會測不出來。

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題:

  • The inability to delete items
  • Poor scaling out of RAM
  • The inability to resize dynamically
  • The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求,但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯,尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。

BitTorrent 對 SHA-1 的改善計畫?

最新一版的 Tails 不再支援透過 BitTorrent 下載,會被導去「Biterrant attack」這邊的連結,裡面有一些關於在 SHA-1 打穿後要怎麼判斷。

BitTorrent 的討論 (包括 BitTorrent 發明人 Bram Cohen 的參與) 則是在 GitHub 上:「Transitioning to stronger hash function · Issue #58 · bittorrent/bittorrent.org」,不過看起來連要用什麼 hash algorithm 的定案都還沒有啊... 而且二月底比較熱鬧一點,三月後都沒什麼動作了。

看起來短時間也不會有動作了...

NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。

類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key crytpsystem 的部份而發的...

投稿時間在 2017 的十一月底,大約一年後就可以看到有哪些演算法要參加競賽了... 不過因為 NSA 的惡名,不知道會不會有其他單位在同個時段啟動類似的活動...

Archives