iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 4
0
自我挑戰組

菜鳥工程師的奇幻漂流:跟著kata活化手指和意識系列 第 4

Smallest unused ID

今日kata

原始題目如下:(8kyu)
You've got much data to manage and of course you use zero-based and non-negative ID's to make each data item unique!
Therefore you need a method, which returns the smallest unused ID for your next new data item...
Note: The given array of used IDs may be unsorted. For test reasons there may be duplicate IDs, but you don't have to find or remove them!

翻譯:
給一陣列,每一元素代表id編號,根據此陣列找出未被使用的最小id

範例:
nextId([0,1,2,3,4,5,6,7,8,9,10])->回傳 11
nextId([1,2,0,2,3,5])-> 回傳 4


構想&解法

function nextId(ids){
  let unused;
  for(let i=0; i<=ids.length;i++){
   if( !ids.includes(i)){
     unused =i;
     return unused===undefined?0:unused
   }
  }
}

input為一陣列ids,每一個元素代表id編號,編號由0開始

在理想沒有跳號的情況下:
ids=[0,1,2,3,4] 下一組最小可用編號,剛好為ids.length-->5

於是想到的土法煉鋼法,從0開始檢查1,2,3,4....一直到ids.length
使用includes一個一個確認array中的元素

觀摩其他解法

 function nextId(ids){
  var x = 0;
  while (ids.includes(x)) x++;
  return x;
}

一樣也是includes的概念,使用while,若ids陣列包含x,繼續檢查ids陣列是否包含x+1。


整理用法

常見使用迴圈有幾種方式:

  • For Loop
  • While Loop
  • Do-While Loop
  • For-In Loop (取得物件的屬性時使用)

很多文章可能都會爭論討論哪種效能好,事實上,這4種寫法,只有for-inloop效能會明顯的差於其他3者。不過到底該選擇哪種loop,主要還是取決於需求,而不是因為哪個效能好選哪個。

For-In Loop主要用來列舉物件中的屬性,也包含繼承來的方法

若要提高loop的效能可以考慮朝兩方面調整:

  • 減少每次迭代要做的事 (work done per iteration)
  • 減少迭代的數量 (number of iterations)

以For Loop為例

for (var i = 0; i < 10; i++){    //loop body}

拆解for loop包含四個部分:

  • initialization
    • 初始化/起始值。(Ex: var i=0)
  • pretest condition
    • 條件式,符合才會進入loop body執行。(Ex: i<10 )
  • loop body
    • 執行的內容
  • post-execute
    • loop body完成後,須執行的post-execute(翻成:後執行?)。(Ex:i++)

優化

for (var i = 0; i < items.length; i++){
    process(items[i]);
}

每次執行完process(items[i])後,i=i+1 --> 找出items.length值 --> 檢測i是否小於items.length
每次都要再重新找items.length的值,可以簡化成:

for (var i = 0, len = items.length; i < len; i++){
    process(items[i]);
}

先將len儲存起來,避免每次iteration重複執行。

for (var i = items.length; i--; ){
    process(items[i]);
}

這是另一種寫法,不是因為i--i++好,而是因為compare with 0不需要特別宣告,預設就是它。
可以想成:

for(var i = array.length; i--; )

//  pseudo code
 i=array.length
 :LOOP_START
 decrement i
 if [ i = 0 ] goto :LOOP_END
 ... BODY_CODE
 :LOOP_END

其中i=0,是一個常數

而一般常用的寫法,會給初始值、終止條件及遞增值:

for(var i = 0 ; i < array.length; i++ )

// pseudo code
 end=array.length
 i=0
 :LOOP_START
 if [ i < end ] goto :LOOP_END
 increment i
 ... BODY_CODE
 :LOOP_END

將原本[i=0]的部分替換成[i< end]
以上參考自stack overflow: Are loops really faster in reverse?,裡面有很多的討論

其他推薦閱讀:
MDN web docs:Loops and iteration
How to optimize your JavaScript apps using Loops
JS之for迴圈優化

以上為今日分享的內容,若有錯誤或是建議,請再隨時和我聯繫。


上一篇
Get the mean of an array
下一篇
Find the smallest integer in the array
系列文
菜鳥工程師的奇幻漂流:跟著kata活化手指和意識30

尚未有邦友留言

立即登入留言