Debbie

VineetKumar at English Wikipedia 2007

Merge sort 使用到的是 Divide and conquer 這個方法,把大問題先切割成一個個小問題,等所有小問題解決之後,大問題也解決了。有點像規劃一個旅遊行程時,你會先處理其中的小問題,比方要住哪裡,要去哪邊,用甚麼交通工具… 等你把這些小問題全部想清楚了,整個旅遊計畫也就完成了。

Merge Sort

💡 先排序小陣列,利用遞迴方式慢慢排序到整個陣列

演算法主要分成兩個步驟,分別是切割以及合併。

步驟:

  1. 將陣列切割到最小單位,也就是一個元素的長度
  2. 接著兩兩元素進行排列,並慢慢增加排序數量,直到完成排序

切割

--

--

Photo by Kind and Curious on Unsplash

這次要來介紹的排序演算法是 Bubble Sort,之所以會叫這個可愛的名字是因為使用這個演算法會慢慢將元素移動到最右側,有點像是水中的泡泡慢慢往水面漂一樣,現在還無法領會沒關係,相信跟著步驟走過一遍就會了解這個名字為什麼這樣取了!

Bubble Sort

💡 兩兩一組依序進行比較,慢慢把數值大的元素換到陣列最右側

步驟:

  1. 未分類陣列兩兩一組依序做比較
  2. 若左側元素大於右側元素則互相交換位置,否則繼續進行比較
  3. 一輪排序結束後若還沒完成整個陣列的排序則回到步驟1,反覆執行直到完成排序

陣列一開始為 const array = [67, 14, 28, 2, 35]

--

--

Photo by Andre Taissin on Unsplash

寫程式的時候,遇到排序問題常常都是直接呼叫built-in function來用,卻沒有真正去思考過它背後的演算法為何,這陣子面試剛好有被問到遇到排序的演算法,這才知道原來排序有這麼多種方法,決定用筆記的方式紀錄每個方法的差異。

首先從最直覺好懂的 Selection Sort 開始介紹。

Selection Sort

💡 不斷從未排序陣列中找出最小的元素並放到陣列最左側

步驟:

  1. 找出未排序陣列中最小的元素
  2. 將最小的元素和最左邊的元素交換位置,並回到步驟1,直到整個陣列都完成排序

圖示解說:

🟦 未排序元素 🟩 已排序元素 🟧 該次排序時位置有變動的元素

首先將整個陣列視為已排序過(sorted subarray)以及未排序過(unsorted subarray)的陣列。

陣列初始化為 const array = [50, 2, 31, 10, 67],此時整個陣列都未排序。首先找出陣列中最小的元素並和未排序陣列(藍色)最左元素交換位置

--

--

Photo by Mohammad Rahmani on Unsplash

在實作爬蟲專案時,有時候需要連續發幾個HTTP request到server端請求資料(比方搜尋頁數較多時),我直覺想到的是這樣的做法:

同時發送所有request, 等全部的request完成再進行下個步驟

一次發送 5 個請求可能沒什麼問題,不過當請求數量變大,你很可能會遇到這個報錯 Error: read ECONNRESET 原因是因為Node沒有辦法一次處理太多請求。

解決辦法

使用Bluebird Promise.map 設定 concurrency:原先使用的Promise.all並沒有設定處理事件的上限,也就是說假設放了100個item在Promise.all裡面,這100個item會同時啟動。這時候可以使用Bluebird幫我們達成任務。

Bluebird是一個第三方的promise庫,它相容原本的promise物件,並提供額外的擴充功能。

我們要使用的就是其中的 promise.map,官方文件的操作方法如下:

Promise.map(
Iterable<any>|Promise<Iterable<any>> input,
function(any item, int index, int length) mapper,
[Object {concurrency: int=Infinity} options]
) -> Promise

第一個參數放可迭代的對象,第二個參數放callback function,第三個參數放concurrency,也就是一次要運行的promise數量

這樣的寫法就可以控制一次發送request的數量,避免連線中斷或是造成他人伺服器的負荷。

其它作法

使用 es6-promise-pool或是 promise-limit 也可以達到類似的效果

參考文章

以上就是本次除錯的紀錄,如果文章有任何錯誤或反饋歡迎留言告訴我!

--

--

Debbie

Debbie

Who dares, wins. | Backend Engineer | Voracious Reader | Dog Person | Being open to challenge