統治世界的 10 大演算法

軟體正在統治世界。而軟體的核心則是演算法。演算法千千萬萬，又有哪些演算法屬於「皇冠上的珍珠」呢？Marcos Otero 給出了他的看法。

什麼是演算法？

通俗而言，演算法是一個定義明確的計算過程，可以一些值或一組值作為輸入並產生一些值或一組值作為輸出。因此演算法就是將輸入轉為輸出的一系列計算步驟。 

—Thomas H. Cormen，Chales E. Leiserson，演算法入門第三版

簡而言之，演算法就是可完成特定任務的一系列步驟，它應該具備三大特徵：

1. 有限
2. 指令明確
3. 有效

以下是 Marcos Otero 推薦的十大演算法：

1、合併排序、快速排序及堆排序

最好的排序演算法跟需求密切相關，很難評判。但是從使用上說，這三種的使用頻率更高。

合併排序由馮．諾依曼於 1945 年發明。這是一種基於比較的排序演算法，採用分而治之的辦法解決問題，其階是 O(n^2)。

快速排序可採用原地分割方法，也可採用分而治之演算法。這不是一種穩定的排序演算法，但對於基於 RAM（記憶體）的陣列排序來說非常有效。

堆排序採用優先順序佇列來減少資料中的搜尋時間。該演算法也是原地演算法，並非穩定排序。

這些排序演算法相對於以前的冒泡排序演算法等有了巨大改進，實際上我們今天的資料採擷、人工智慧、連結分析及包括 web 在內的大多數電腦工具都要感謝它們。

2、傅立葉變換與快速傅立葉變換

我們的整個數位世界都使用這兩個簡單但非常強大的演算法，其作用是將訊號從時域轉為頻域或者反之。實際上，你看得到這篇文章得感謝這些演算法。

網際網路、你的 WiFi、智慧型手機、電話、電腦、路由器、衛星，幾乎所有內建有電腦的東西都會以各種方式使用這兩演算法。如果不研究這些演算法，你就拿不到電子、計算或通信方面的學位。

3、迪科斯徹（Dijkstra）演算法

Dijkstra是一種圖譜搜尋演算法。許多問題都可以建模為圖譜，然後利用 Dijkstra 尋找兩個節點之間的最短路徑。如果沒有 Dijkstra 演算法，網際網路的運作效率必將大大降低。雖然今天我們已經有了更好的尋找最短路徑的解決方案，但出於穩定性的要求，Dijkstra 演算法仍然被很多系統使用。

4、RSA加密演算法

如果沒有密碼術和網路安全，網際網路就不會像今天一樣重要，因為電子商務和電子交易需要這些技術來確保交易安全。而RSA演算法是最重要的密碼學演算法之一。該演算法由同名公司的創始人（Ron Rivest、Adi Shamir 和 Leonard Adleman）開發，它讓密碼學普及到了千家萬戶並奠定了密碼術的應用基礎。RSA 要解決的問題既簡單又複雜：如何在獨立平台與最終用戶之間共用公開金鑰。其解決方案是加密。

RSA 加密的基礎是一個十分簡單的數論事實：將兩個大質數相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密金鑰。但在分散式運算和量子電腦理論日趨成熟的今天，RSA 加密安全性受到了挑戰。

5、安全雜湊演算法（SHA）

這個實際上並不算是演算法，而是由美國國家標準技術研究所開發的一系列密碼雜湊函數。但是這系列函數是全世界運作的基石。應用程式商店，電子郵件、反病毒、瀏覽器等在使用SHA系列函數，SHA 函數可用來確定下載的東西是否自己想要的東西，還是說遭遇了中間人攻擊或釣魚攻擊。

6、質因數分解

這是一個在電腦領域使用頻繁的數學演算法。如果沒有這一演算法，密碼技術就會變得不安全得多。質因數分解是用來將一個合數分解成一系列質因數的一系列步驟。質因數分解可被視為是 FNP 問題（FNP 是難以解決的典型 NP 問題的擴展）。

許多密碼協定均基於難以分解的大型合數或相關問題。比方說前面提到的 RSA 問題。如果有演算法能夠有效分解任意數位，那麼就會使得基於 RSA 的公開金鑰密碼系統陷入不安全的境地。

而量子電腦的誕生則讓此問題的解決變得容易，從而也打開了一個全新的領域，可利用量子世界的屬性來讓系統更加安全。

7、連結分析

在網路時代，不同實體間關係的分析至關重要。從搜尋引擎和社群網路到行銷分析工具，每個人都想找出網路的真正結構。

連結分析無疑是公眾對演算法的最大困惑與迷思之一。其問題在於進行連結分析有不同的方式，而增加一些特徵就會令每一演算法略有不同（從而使得演算法受到專利保護），但基本上這些演算法都是類似的。

連結分析演算法首先由 Gabriel Pinski 和 Francis Narin 在 1976 年發明。其背後的思路很簡單，即把圖譜以矩陣的形式表示，從而轉為特徵值問題，而特徵值有助於瞭解圖譜結構及每個節點的相對重要性。

Google 的 PageRank，Facebook 展示新聞源，Google+，Facebook 朋友推薦，LinkedIn 工作及連絡人推薦，Netflix 與 Hulu 的電影推薦，YouTube 影片推薦等均使用了連結分析演算法。雖然每個都有不同的目標和參數，但其背後的數學是一樣的。

8、比例積分微分演算法

如果你用過飛機、汽車、衛星服務或手機網路，如果你在工廠待過或者見過機器人，那麼你已經見識過這一PID演算法的作用了。

該演算法利用了控制迴路機制來讓期望輸出訊號與實際輸出訊號之間的錯誤降到最小。只要需要訊號處理或需要電子系統來控制自動化的機械、水力或熱力系統就要用到它。

因此可以說如果沒有這一演算法，人類的現代文明將不復存在。

9、資料壓縮演算法

資料壓縮演算法無疑是非常重要的，因為幾乎在所有的結構中都要用到。除了最明顯的壓縮文件以外，網頁下載時也會壓縮，影片遊戲、影片、音樂、資料存儲、雲端計算、資料庫等等也都要使用壓縮演算法。可以說幾乎所有應用都要使用壓縮演算法。壓縮演算法讓系統更有效成本更低，但是要想確定哪一個最重要卻很困難，因為應用不同，使用的壓縮演算法從 zip 到 mp3、JPEG 或 MPEG-2 各異。

10、亂數產生演算法

很多應用都需要亂數。像 interlink connection，密碼系統、影片遊戲、人工智慧、最佳化、問題的初始條件，金融等都需要生成亂數。但實際上目前我們並沒有「真正」的亂數產生器，儘管有一些偽亂數產生器也是非常有效的。

當然，十大演算法也可能有湊數之嫌，審視的角度不同對演算法的重要性看法也會很不一樣，如果你認為這一榜單有錯漏的地方，不妨在評論中貢獻你的意見。(medium.com)

IoC - Annotation (@Service)

At the moment, @Service serves as a specialization of @Component, allowing for implementation classes to be autodetected through classpath scanning. What this means is that you could annotate your service-layer classes with @Component, but by annotating them with @Service instead, your classes are more properly suited for processing by tools or associating with aspects, since @Service makes an ideal target for pointcuts. Of course, it is possible that @Service may carry additional semantics in the future; thus, if you are making a decision between using @Component and @Service, @Service is clearly the better choice for your service-layer.


@Component and similar annotations (@Service, @Repository, etc. )and its JSR-330 counterpart @Named allow you to declare beans that are to be picked up by autoscanning with <context:component-scan/> or @ComponentScan they register the bean definition for the classes, so they are roughly equivalent to declaring the specified beans with the <bean ... /> tag in XML. This bean types will adhere to the standard proxy creation policies.


@Component is equivalent to <bean>,
@Configuration is equivalent to <beans>.

在blogger中插入程式碼

https://pjchender.blogspot.hk/2016/06/prism-syntax-highlighting.html

http://prismjs.com/#languages-list

http://www.opinionatedgeek.com/DotNet/Tools/HTMLEncode/Encode.aspx

var person = {
    firstname: 'Jeremy',
    lastname: 'Lin',
    getFullName: function(){
  
        var fullname = this.firstname + ' ' + this.lastname;
        return fullname;

    }
}

IoC - Annotation (@Value)

@Value("#{controllerProperties.defCountryId}")private Integer defCountryId;

將 controllerProperties.defCountryId  注入 defCountryId

IoC - Annotation (@Autowired)

在 spring 早期版本，只能透過 xml 進行配置設定，這會讓設定與程式是分開的，當程式很大、類別很多時，維護非常不容易，現在 spring framework 提供 annotation 的方式，把設定直接寫在程式上，可大量減輕維護的工作量。這裡說明怎麼以 annotation (註釋) 的方式進行 IoC，這個簡單的例子是一家公司有老闆，也有員工，我們要印出老闆名字和員工人數，整個專案會有如下幾個檔案:

MyTest 是測試程式，內容如下:

package tw.idv.leader;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;
import tw.idv.leader.pojo.Company;

public class MyTest {

    public static void main(String[] args) {
        ApplicationContext context = new ClassPathXmlApplicationContext("tw/idv/leader/beans-config.xml");
        Company company = (Company) context.getBean("company");
        System.out.println("老闆名字: " + company.getBoss().getName());
        System.out.println("員工人數: " + company.getEmployee().getCount());
    }
}


現在看一下傳統 IoC 和使用 annotation IoC 的方式有什麼不一樣。

【傳統方式】

Company.java
package tw.idv.leader.pojo;

import org.springframework.beans.factory.annotation.Autowired;

public class Company {
    private Boss boss;
    private Employee employee;

    public Boss getBoss() {
        return boss;
    }

    public void setBoss(Boss boss) {
        this.boss = boss;
    }

    public Employee getEmployee() {
        return employee;
    }

    public void setEmployee(Employee employee) {
        this.employee = employee;
    }
}

注意上面兩個 setter method，設定檔將使用這兩個 setter method 進行注入; 下方紅色部份即是利用這兩個 setter method 進行注入。

beans-config.xml
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

    <bean id="company" class="tw.idv.leader.pojo.Company">
        <property name="boss" ref="myBoss"/>
        <property name="employee" ref="ourEmployee"></property>
    </bean>

    <bean id="myBoss" class="tw.idv.leader.pojo.Boss">
        <property name="name" value="Steven" />
    </bean>

    <bean id="ourEmployee" class="tw.idv.leader.pojo.Employee">
        <property name="count" value="10" />
    </bean>
</beans>


【annotation方式 (1)】
類別 Company 的屬性上加上 @Autowired，取消 setter method。

Company.java
package tw.idv.leader.pojo;

import org.springframework.beans.factory.annotation.Autowired;

public class Company {
    @Autowired
    private Boss boss;
    @Autowired
        private Employee employee;

    public Boss getBoss() {
        return boss;
    }

    public Employee getEmployee() {
        return employee;
    }
}

設定檔中最重要的是加上綠色部份，現在類別 Company 沒有 setter method 了，所以，也拿掉兩個 property，spring 容器啟動時，AutowiredAnnotationBeanPostProcessor 會自動掃描所有的 bean，當發現 bean  中的屬性有 @Autowired 註釋時，就會找到與其匹配的 bean，並注入到對應的地方去。
beans-config.xml
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

 <bean class="org.springframework.beans.factory.annotation.AutowiredAnnotationBeanPostProcessor"/>

    <bean id="company" class="tw.idv.leader.pojo.Company" />

    <bean id="myBoss" class="tw.idv.leader.pojo.Boss">
        <property name="name" value="Steven" />
    </bean>

    <bean id="ourEmployee" class="tw.idv.leader.pojo.Employee">
        <property name="count" value="10" />
    </bean>
</beans>

【annotation方式 (2)】
這是另一種 annotation 的方式，將 @Autowired 寫在 setter method。

Company.java
package tw.idv.leader.pojo;

import org.springframework.beans.factory.annotation.Autowired;

public class Company {
    private Boss boss;
        private Employee employee;

    @Autowired
    public void setBoss(Boss boss) {
        this.boss = boss;
    }

    @Autowired
    public void setEmployee(Employee employee) {
        this.employee = employee;
    }

    public Boss getBoss() {
        return boss;
    }

    public Employee getEmployee() {
        return employee;
    }
}

【annotation方式 (3)】
還有一種，把 annotation 寫在建構子上。

Company.java
package tw.idv.leader.pojo;

import org.springframework.beans.factory.annotation.Autowired;

public class Company {
    private Boss boss;
    private Employee employee;

    @Autowired
    public Company(Boss boss, Employee employee) {
        this.boss = boss;
        this.employee = employee;
    }

    public Boss getBoss() {
        return boss;
    }

    public Employee getEmployee() {
        return employee;
    }
}


【備註】
當不能確定 spring 容器中一定擁有某個 bean 時，可以在需要自動注入該 bean 的地方，可以使用 @Autowired(required = false)，這等於告訴 spring 在找不到匹配的 bean 時也不要拋出 exception，否則只要 spring 找不到匹配的 bean 就會拋出 BeanCreationException 異常訊息。

Source: https://sites.google.com/site/stevenattw/java/spring-framework/ioc---annotation-autowired

Introduction to Spring 3 MVC Framework

Request Processing Lifecycle

Image courtesy: Springsource

Spring’s web MVC framework is, like many other web MVC frameworks, request-driven, designed around a central servlet that dispatches requests to controllers and offers other functionality that facilitates the development of web applications. Spring’s DispatcherServlet is completely integrated with Spring IoC container and allows us to use every other feature of Spring.

Following is the Request process lifecycle of Spring 3.0 MVC:

1. The client sends a request to web container in the form of http request.
2. This incoming request is intercepted by Front controller (DispatcherServlet) and it will then tries to find out appropriate Handler Mappings.
3. With the help of Handler Mappings, the DispatcherServlet will dispatch the request to appropriate Controller.
4. The Controller tries to process the request and returns the Model and View object in form of ModelAndView instance to the Front Controller.
5. The Front Controller then tries to resolve the View (which can be JSP, Freemarker, Velocity etc) by consulting the View Resolver object.
6. The selected view is then rendered back to client.

GitHub Pages

之前見過有人用 GitHub 來 host 網頁，但未有時間試，今日終於試左。

原來好簡單，只要開番一個 Repository 叫 xxx.github.io (xxx=GitHub用戶名稱) 就得

* 只可以 host 靜態網頁 ( ie HTML)

Limit:

GitHub Pages source repositories have a recommended limit of 1GB .

Published GitHub Pages sites have a 1GB recommended limit.

GitHub Pages sites have a recommended bandwidth limit of 100GB or 100,000 requests per month.

GitHub Pages sites have a recommended limit of 10 builds per hour.

https://amzfree.github.io/

Using Jekyll as a static site generator with GitHub Pages

JSTL

JSTL Core <c:param> Tag

The <c:param> tag allows proper URL request parameter to be specified with URL and it does any necessary URL encoding required.

Example:

If you need to pass parameters to a tag, use the tag to create the URL first as shown below:

<c:url value="/index.jsp" var="myURL">
   <c:param name="trackingId" value="1234"/>
   <c:param name="reportType" value="summary"/>
</c:url>
<c:import url="${myURL}"/>

Above request would pass URL as below

"/index.jsp?trackingId=1234;reportType=summary"

JSTL Core <c:url> Tag

The <c:url> tag formats a URL into a string and stores it into a variable. This tag automatically performs URL rewriting when necessary. The var attribute specifies the variable that will contain the formatted URL.

The JSTL url tag is just an alternative method of writing the call to the response.encodeURL() method. The only real advantage the url tag provides is proper URL encoding, including any parameters specified by children param tag.

Example:

<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
<html>
<head>
<title><c:url> Tag Example</title>
</head>
<body>
<a href="<c:url value="/jsp/index.htm"/>">TEST</a>
</body>
</html>

This would produce following result:

TEST

OAuth 和 Facebook 登入原理

OpenID：用作「身份認證」，如果某網站支援 OpenID，你登入其他網站不需要記憶密碼，只要拿你的 OpenID 登入就好。

OAuth：用作「授權」，舉例而言，如果你需要授權某相片列印公司的網站取得你在 Facebook 的相片，只要該相片列印公司支援 OAuth，你也授權，那該公司就可以取得你在 Facebook 的相片。

OAuth有分1.0和2.0，只討論比較新的2.0

首先，分四個角色

• 資源擁有者 (Resource Owner): 擁有 Facebook 帳號的用戶 ( 用戶甲 )。
• 授權伺服器 (Authorization Server): kkbox向 facebook 取得使用者授權的伺服器
• 資源伺服器 (Resource Server): 保管用戶甲 facebook 資料的 server
• 用戶端 (Client): 想要取得用戶甲 facebook 資料的 kkbox

整體的流程是：


首先，kkbox在 facebook 有一個應用程式。

有一天，用戶甲到 kkbox 網站想聽音樂， kkbox 必須要取得用戶甲的 facebook 帳號授權，才可以取得用戶甲在 facebook 的資料。

因此  kkbox 把用戶甲重新導向到 facebook，用戶甲必須向 facebook 說明「我授權給  kkbox 」，之後 facebook 會告訴  kkbox 的網站「我已經取得用戶甲的授權了」，證明的方法是發送一個授權token給  kkbox 的網站。

但這時  kkbox 不能確定這個授權token真的是 facebook 給的，因此  kkbox 必須要把這個token送回給 facebook，讓 facebook 告訴  kkbox 這個授權是真的，如果是真的，facebook 會交給  kkbox 一串「access_token」，這個東西就是萬能的鑰匙！  kkbox 公司用這個就可以向 facebook 取得所有用戶甲授權的資料了！