iT邦幫忙

1

透過數學技巧改善程式效能系列-設計判斷式

給定一個任意數字陣列 list,例如
15, 6, 15, 5, 15, 16
要求確認陣列中每一個數字是否都完全相同,要如何比較?

一. 直覺的方法就是逐個比較

// 固定將陣列的第一個值當作參考值
Integer check = 15; 

int sumCheck = 0;            
for (Integer i : list) {
  if (i == check) 
  
    // 在迴圈中計數與參考值相同次數
    ++sumCheck;              
}

// 如果計數次數等於陣列大小表示陣列裡面的值全同
if (sumCheck == list.size()) 
  System.out.println("All the same in the array !");
else
  System.out.println("Not the same !");

上面這個直覺做法,依照給定的陣列大小而言,總共做了
6 + 1 次的 if判斷 (迴圈裡6次 與 最後結論1次)。
當然由於參考值就是第一個,可省去第一個的判斷
逐次比較最少也得比較 6/images/emoticon/emoticon34.gif

二. 空間座標比較法

回想一下「高中」在空間座標學的

兩點相同表示距離為 0 ,兩點重合

依據這個概念,問題就變成
(15, 6, 15, 5, 15, 16) 與 (15, 15, 15, 15, 15, 15)
的距離是否為 0 ?

int check = 15;
int sum = 0;
for (int i : numArray) {

  // 兩點距離公式可省去開平方根動作
  sum += (i-check)*(i-check);      
}
if (sum == 0) 
  System.out.println("All the same in the array !");
else
  System.out.println("Not the same !");

改變思維後,完成相同問題只需要做 1if判斷/images/emoticon/emoticon37.gif
不過卻多了

sum += (i-check)*(i-check);

這個計算。不要懷疑,站在想偷懶的電腦角度來説:
做 『加減乘除』 絕對比 『if判斷』 的工作輕鬆得多。/images/emoticon/emoticon39.gif

三. 樹狀結構

回想「大學」計概第一次接觸到樹狀結構,雖然演算法都忘光了/images/emoticon/emoticon04.gif
好險 Java 裡內建 TreeSet物件了/images/emoticon/emoticon07.gif

// 陣列轉換成 TreeSet 步驟
Integer[] numArray = {15, 6, 15, 5, 15, 16};
List<Integer> list = Arrays.asList(numArray);
TreeSet<Integer> treeSet = new TreeSet<Integer>(list);

// 轉換成樹狀結構後,只要判斷樹狀結構是否為單一節點即為題目所求
if (treeSet.size() == 1)
  System.out.println("All the same in the array !");
else
  System.out.println("Not the same !");

換成樹狀結構後,加上 Set的特性不允許重複值,如下圖所示:
https://ithelp.ithome.com.tw/upload/images/20200319/201091079IGXJpoNuS.png
以第一個值當成『節點』,比它小的在『節點左邊』,大的在『節點右邊』。
實際印出 TreeSet 的結果也會依照上述的邏輯幫我們排列好順序:
https://ithelp.ithome.com.tw/upload/images/20200319/20109107dpR9fJtyx4.png
因此如果陣列裡面的值完全相同,『僅單一節點,長不出樹來』
套用樹狀結構的思維,我們只要比較TreeSet的大小是否等於 1便滿足題目所求!
同樣只需要做 1if判斷/images/emoticon/emoticon37.gif

結論:

我想大部分結構化的資料在SQL下都能被處理得服服貼貼的!
不過在NoSQL的架構下,由於沒有預先的資料表規劃,如何去設計集合的結構
數學的技巧就會派上用場了 !
對於樹狀結構的其他應用,分享前幾天看到的水管影片:

/images/emoticon/emoticon32.gif


尚未有邦友留言

立即登入留言