Programming blog

This is a programming blog


  • Home

  • Tags

  • Categories

  • Archives

  • Sitemap

  • Search

[Java] Semaphore的使用時機

Posted on 2016-12-09 | Edited on 2016-12-13 | In Java |

Java所提供的Semaphore跟Operating System Concepts上所講的Semaphore一樣。

可以用它來解決:

  • Producer and Consumer Problem
  • The Readers-Writers Problem
  • The Dining-Philosophers Problem
  • Pool的實作
  • 控制critical region

####範例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.concurrent.Semaphore;

public class SemaphoreDemo {

Semaphore pool = new Semaphore(10);

public static void main(String args[]) {
final SemaphoreDemo demo = new SemaphoreDemo();

for (int i = 0; i < 30; i++) {
new Thread(new Runnable() {

@Override
public void run() {
demo.mutualExclusion();
}

}, "Thread" + i).start();

}
}

private void mutualExclusion() {
try {
pool.acquire();

System.out.println(Thread.currentThread().getName() + " inside mutual exclusive region");
Thread.sleep(1000);

}
catch (InterruptedException e) {
e.printStackTrace();
}
finally {
pool.release();
System.out.println(Thread.currentThread().getName() + " outside of mutual exclusive region");
}
}

}

當pool為空的時候,想要使用pool資源的thread會進入blocking狀態,直到有其他thread執行release()釋放pool資源,喚醒其中在blocking狀態的thread。

參考資料:

Counting Semaphore Example in Java 5 – Concurrency Tutorial

[Java] Difference between synchronized vs ReentrantLock

Posted on 2016-12-09 | Edited on 2018-05-09 | In Java |

根據參考資料整理了ReentrantLock和synchronized的比較表:

ReentrantLock synchronized
鎖定對象 可以對任何對象上鎖 class literal, the instance of class
效能 較好 較差
中斷 可以放棄取鎖 一旦嘗試獲取鎖就會一直等待直到獲取到鎖
lock的鎖定和釋放 程式設計師控制 JVM控制
  • ReentrantLock的控制程度比較大,synchronized的控制程度比較小。
  • 正確使用的情況下,使用ReentrantLock會比使用synchronized的效能較好。
  • 若對同步問題不熟悉,鎖定和釋放ReentrantLock的順序不對容易造成deadlock。

參考資料

ReentrantLock Example in Java, Difference between synchronized vs ReentrantLock

[Java] ThreadLocal

Posted on 2016-12-09 | Edited on 2016-12-13 | In Java |

當多個thread共享某些變數,可以透過synchronized或是lock來保護共享變數,避免產生race condition問題。這樣的作法安全但是效能會變慢,是以時間換空間的方法。

將共享變數各複製一份給thread,這樣既達安全性並且提升效能,是以空間換時間的方法。可以使用ThreadLocal來達到這樣的效果。

例如:

  1. 多個thread共享SimpleDateForamt變數,因為SimpleDateForamt不是ThreadSafe,因此會有同步問題。可以使用ThreadLocal解決。
  2. Database connection pool中的thread會共享某些變數,假如透過lock方式避免同步問題發生,但會導致效能較差。可以使用ThreadLocal解決,以空間來換取時間。
  3. Java Application Server利用ThreadLocal管理transaction和security資訊。

參考資料:

  • Design Pattern: Thread-Specific Storage 模式
  • ThreadLocal in Java - Example Program and Tutorial
  • Java Thread Local – How to Use and Code Sample

Find running median from a stream of integers

Posted on 2016-12-09 | In Algorithm |

依序輸入多個數字,如何有效率找出中位數(median)?

例如:依序輸入7、13、2、6、9,中位數為7。

解法:

  1. 將所有數字排序,即可以得出中位數。
    時間複雜度為$O(nlogn)$
  2. 利用max heap和min heap:

    • 新增數字到heap:
      • 若max heap為空,數字新增到min heap。
      • 若max heap不為空並且數字小於max heap的root,數字新增到max heap。
      • 若max heap不為空並且數字大於max heap的root,數字新增到min heap。
    • rebalance:
      • 若max heap size - min heap size > 1, 刪除max heap的root並且新增到min heap。
      • 若min heap size - max heap size > 1, 刪除min heap的root並且新增到max heap。
    • 計算中位數:
      • 若max heap size > min heap size,中位數為max heap的root。
      • 若max heap size < min heap size,中位數為min heap的root。
      • 若max heap size == min heap size,中位數為$(max\ heap的root + min\ heap的root) / 2$ (根據定義決定)。

    時間複雜度為$O(1)$

    此方法是利用中位數的特性:

    • 左半部的數字一定小部右半邊。

      例如:2、3、7、13、15 或是2、3、7、13、15

    • 左半部和右半部的大小差值不能超過1,否則不能透過上述方法找出中位數。

    • 左半部的數字(包含中位數)建成max heap,max heap的root即為中位數。

      例如:2、3、7、13、15

      2、3、7建成max heap,13、15建成min heap

    • 右半部的數字(包含中位數)建成min heap,min heap的root即為中位數。

      例如:2、3、7、13、15

      2、3建成max heap,7、13、15建成min heap

程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class FindMedian<E> {
private Queue<E> queue;
private Queue<E> maxHeap;
private Queue<E> minHeap;
private Comparator<E> comparator;

public FindMedian(Comparator<E> comparator) {
queue = new LinkedList<>();
maxHeap = new PriorityQueue<>(Collections.reverseOrder(comparator));
minHeap = new PriorityQueue<>(comparator);
this.comparator = comparator;
}

public void enqueue(E e) {
if (e == null)
throw new IllegalArgumentException();

this.queue.add(e);

addElementToHeap(e);

rebalance();
}

public E dequeue() {
E removeObject = this.queue.remove();
this.maxHeap.remove(removeObject);
this.minHeap.remove(removeObject);

return removeObject;
}

public E peekMedian() {
if (maxHeap.size() == minHeap.size()) {
// Depends on definition
return maxHeap.peek();
}
else if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
}
else {
return minHeap.peek();
}
}

private void addElementToHeap(E e) {
E tmp = maxHeap.peek();
if (tmp == null) {
minHeap.add(e);
}
else if (comparator.compare(tmp, e) > 0) {
maxHeap.add(e);
}
else {
minHeap.add(e);
}
}

private void rebalance() {
int sizeDiff = maxHeap.size() - minHeap.size();
if (sizeDiff > 1) {
minHeap.add(maxHeap.remove());
}
else if (sizeDiff < -1) {
maxHeap.add(minHeap.remove());
}
}
}

FindMedian

參考資料:

Find running median from a stream of integers

[Java] How do I switch between Java8, Java 7 and Java 6 on OS X

Posted on 2016-12-09 | Edited on 2016-12-13 | In Java |

解決方法:

將以下程式碼加入到.bash_profile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function setjdk() {  
if [ $# -ne 0 ]; then
removeFromPath '/System/Library/Frameworks/JavaVM.framework/Home/bin'
if [ -n "${JAVA_HOME+x}" ]; then
removeFromPath $JAVA_HOME
fi
export JAVA_HOME=`/usr/libexec/java_home -v $@`
export PATH=$JAVA_HOME/bin:$PATH
fi
echo JAVA_HOME set to $JAVA_HOME
java -version
}
function removeFromPath() {
export PATH=$(echo $PATH | sed -E -e "s;:$1;;" -e "s;$1:?;;")
}

使用方式:

1
setjdk 1.8

參考資料:

How do I switch between Java 7 and
Java 6 on OS X 10.8.2?

[Java] Test Java mail by GreenMail

Posted on 2016-12-09 | Edited on 2016-12-13 | In Java |

要如何對JavaMail-API做單元測試呢? 在Stack Overflow上不少人推薦 GreenMail,GreenMail支援SMTP, POP3, IMAP,可以對sender和receiver進行測試,就來試用看看。

Sender

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class MailSenderTest {

private GreenMail greenMail;
private MimeMessage message;

@Before
public void setUp() throws Exception {
greenMail = new GreenMail(ServerSetupTest.SMTP);
greenMail.start();

Properties properties = System.getProperties();
properties.put("mail.smtp.host", "localhost");
properties.put("mail.smtp.port", ServerSetupTest.SMTP.getPort());
Session session = Session.getInstance(properties);
message = new MimeMessage(session);
message.setFrom(new InternetAddress("test@test.com"));
message.setRecipients(Message.RecipientType.TO,
InternetAddress.parse("test1@test.com", false));
message.setSubject("subject");
message.setText("text");
message.setSentDate(new Date());
}

@After
public void tearDown() throws Exception {
greenMail.stop();
}

@Test
public void testSend() throws Exception {
// [Start] Replace this with your send code
// Sender.send(message);
// [End]

MimeMessage[] messages = greenMail.getReceivedMessages();
Assert.assertNotNull(messages);
Assert.assertEquals(1, messages.length);
MimeMessage m = messages[0];
Assert.assertEquals("subject", m.getSubject());
Assert.assertTrue(String.valueOf(m.getContent()).contains("text"));
Assert.assertEquals("test@test.com", m.getFrom()[0].toString());
}
}

Receiver

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class MailReceiverTest {

private GreenMail greenMail;
private String subject;
private String body;

@Before
public void setUp() throws Exception {
greenMail = new GreenMail(ServerSetupTest.SMTP);
greenMail.start();

subject = GreenMailUtil.random();
body = GreenMailUtil.random();
GreenMailUtil.sendTextEmailTest("test@localhost.com", "test1@localhost.com", subject, body);
}

@After
public void tearDown() throws Exception {
greenMail.stop();
}

@Test
public void testReceiver() throws Exception {
// [Start] Replace this with your receive code
// Message message = Receiver.receive();
// [End]

Assert.assertNotNull(message);
Assert.assertEquals(message.getTo(), "test@localhost.com");
Assert.assertEquals(message.getFrom(), "test1@localhost.com");
Assert.assertEquals(message.getSubject(), subject);
Assert.assertEquals(message.getBody(), body);
}
}

使用GreenMail進行測試,嚴格來說並不屬於unit test,某種程度來說它也是屬於mail server,否則就必須mock Transport和Session。是否能透過mock Transport和Session來達到測試效果,這跟你的mail class設計有關。以實用性、方便性和功能性,GreenMail算是一個不錯測試mail的framework。

參考資料:

  • GreenMail
  • Integration Testing IMAP, SMTP and POP3 with GreenMail
  • How to test… Java Mail

[LOGBack] "hidden" cost of parameter construction

Posted on 2016-12-09 | Edited on 2016-12-13 | In LOGBack |

以往寫程式的時候,對於log的使用通常像這樣:

1
logger.debug("The new entry is "+entry+".");

但是這樣的做法會有效能影響。
不管log debug模式是否有打開,都會將"The new entry is "+entry+"."轉成字串。

當entry是一個很大的物件,且在production環境(log debug模式是關閉),很有可能造成效能低落。

較好的作法如下(只有在log debug模式是打開的時候,才會將"The new entry is "+entry+"."轉成字串):

1
logger.debug("The new entry is {}.", entry);

有多個參數的時候:

1
2
Object[] paramArray = {newVal, below, above};
logger.debug("Value {} was inserted between {} and {}.", paramArray);

參考資料:

http://logback.qos.ch/manual/architecture.html

[Jersey] RESTful service starter-kit (1)

Posted on 2016-12-09 | Edited on 2016-12-13 | In Java |

JAX-RS有提供類似AOP功能,我們可以集中處理所有的Exception。

在Clean Code說到:


The short chapter seven of «Clean Code» is dedicated to error handling. The one point it stresses with vigor is:
Do not use checked exceptions!
The price of checked exceptions is an Open/Closed Principle violation. If you throw a checked exception from a method in your code and the catch is three levels above, you must declare that exception in the signature of each method between you and the catch. This means that a change at a low level of the software can force signature changes on many higher levels.
—Robert C. Martin, «Clean Code», page 107

我會習慣將checked exception轉成runtime exception,統一集中處理。

例如:只要沒有處理到的exception,一律回Internal Server Error

只要實作ExceptionMapper,選擇要捕捉exception放到generic,最後再加入@Provider就可以統一處理想要處理的Exception。

1
2
3
4
5
6
7
8
9
10
11
@Provider
public class GenericExceptionMapper implements ExceptionMapper<Throwable> {

@Override
public Response toResponse(Throwable exception) {
return Response.status(Response.Status.INTERNAL_SERVER_ERROR)
.entity(exception.getMessage())
.type(MediaType.APPLICATION_JSON)
.build();
}
}


Glassfish有提供LoggingFilter,可以自動log每個request和response。
假如對於輸出格式比較要求,可以實作屬於自己的LoggingFilter,實作方式可以參考LoggingFilter.java。

使用LoggingFilter可以在web.xml或程式碼中開啟。可以參考Registering Resources and Providers in Jersey 2。

例如:

client端發出:

http://localhost:8080/jersey-starterkit/hello```
1
2
3
4
5
6
7
8
9
10
11
12
server端會紀錄相關資訊:
```bash
15:34:40.087 [qtp1671915608-80] INFO application.MyApplication - 3 * Server has received a request on thread qtp1671915608-80
1 > GET http://localhost:8080/jersey-starterkit/hello
1 > Accept: */*
1 > Host: localhost:8080
1 > User-Agent: curl/7.37.1

15:34:40.091 [qtp1671915608-80] INFO application.MyApplication - 4 * Server responded with a response on thread qtp1671915608-80
2 < 200
2 < Content-Type: application/json
hello

程式碼:

https://github.com/pandaforme/jersey-starterkit

參考資料:

  • Error handling in REST API with Jersey
  • Testing error handling in RESTful application with jersey and jbehave
  • Registering Resources and Providers in Jersey 2

[Scala] Tail recursion

Posted on 2016-12-09 | Edited on 2017-04-26 | In Scala |

在學習Functional programming過程中,學到遞迴可以分為兩類:

  • Tail recursion
1
If a function calls itself as its last action, the function’s stack frame can be reused. This is called tail recursion.
  • Tail call
1
If the last action of a function consists of calling a function (which may be the same), one stack frame would be sufficient for both functions. Such calls are called tail-calls.

分別以計算最大公因數(gcd)和階層(factorial)為例:

  • gcd

    1
    2
    3
    4
    5
    6
    def gcd(a: Int, b: Int): Int = {
    if (b == 0)
    a
    else
    gcd(b, a % b)
    }
  • factorial

    1
    2
    3
    4
    5
    6
    def factorial(n: Int): Int = {
    if (n == 0)
    1
    else
    n * factorial(n - 1)
    }

例如:

1
gcd(21, 14) -> gcd(14, 7) -> gcd(7, 0) -> 7
1
2
3
4
5
6
factorial(5) -> 
5 * factorial(4) -> 5 * 4 * factorial(3) ->
5 * 4 * 3 * factorial(2) ->
5 * 4 * 3 * 2 * factorial(1) ->
5 * 4 * 3 * 2 * 1 * factorial(0) ->
5 * 4 * 3 * 2 * 1 * 1

可以發現:

  1. 在gcd範例中,每一步不會依賴上一步的結果,上一步的結果是以參數方式傳入到函式裡面。
  2. 在factorial範例中,每一步會依賴上一步的結果,所以需要 stack 來記錄每一步的狀態。
    等走到盡頭後,再取出 stack 內的元素並且計算之,逐一合併結果。

假如執行 factorial(100000) 可以預期會發生 stack overflow,我們可以將原本的程式改成Tail recursion版本,就不會有 stack overflow 發生。
在Scala中會對Tail recursion做最佳化,或是可以透過 @tailrec 標註此函數是Tail recursion。

  • 測試範例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.concurrent.TimeUnit

import com.google.common.base.Stopwatch

def factorial(n: Int): Int = {
if (n == 0)
1
else
n * factorial(n - 1)
}

def factorialTailrec(n: Int, result: Int): Int = {
if (n == 0)
result
else
factorialTailrec(n - 1, n * result)
}

val sw = Stopwatch.createUnstarted()
sw.elapsed(TimeUnit.MILLISECONDS)
sw.start()
factorial(15)
sw.stop()
println(sw.toString)
sw.reset()

sw.start()
factorialTailrec(15, 1)
sw.stop()
println(sw.toString)
  • 測試結果:
    1
    2
    1.611 ms
    677.4 μs

可以看出來改成Tail recursion版本效率會大幅改善。

參考:

  1. What is tail recursion?
  2. Tail recursion

[Git] Moving A Git Repository To A New Server

Posted on 2016-12-09 | Edited on 2016-12-13 | In Git |

[更新]有更簡潔的做法,請參考 Duplicating a repository

在工作上遇到要將git repository從舊的server轉移到新的sever,參考這篇文章Moving A Git Repository To A New Server進行轉移.

Step 1: fetch所有的remote branch

1
git fetch origin

Step 2: 將所有remote branch clone到本地端

1
2
3
4
5
for branch in `git branch -a | grep remotes | grep -v HEAD`; do
git branch --track ${branch##*/} $branch
done
git fetch --all
git pull --all

Step 3: 新增新的repository,名稱為new-origin

1
git remote add new-origin git@[new server url]:[group]/[project].git

Step 4: push所有的branch和tag到新的repository

1
2
git push --all new-origin
git push --tags new-origin

Step 5: 砍掉舊的repository,並且新的repository改名為origin

1
2
git remote rm origin
git remote rename new-origin origin

將以上的操作步驟寫成script:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/bin/bash
rm -rf $1
git clone git@old-repo:old-group/$1.git
cd $1
git fetch origin
for branch in `git branch -a | grep remotes | grep -v HEAD`; do
git branch --track ${branch##*/} $branch
done
git fetch --all
git pull --all
git remote add new-origin git@new-repo:new-group/$1.git
git push --all new-origin
git push --tags new-origin
git remote rm origin
git remote rename new-origin origin

參考:

  • Moving A Git Repository To A New Server
  • Clone all remote branches with Git?
  • Duplicating a repository
1234

pandaforme

This is a programming blog

33 posts
7 categories
17 tags
RSS
GitHub Linkedin
© 2018 pandaforme
Powered by Hexo v3.7.1
|
Theme — NexT.Gemini v6.2.0