# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br> NTU Advenced JAVA programming
:::info
授課老師: 盧政良 (Zheng-Liang Lu)
Email: d00922011 at ntu.edu.tw
:::

# 5/9
## OOP: a quick review
OOP: https://www.csie.ntu.edu.tw/~d00922011/java2/java2_oop.pdf
Memory Usage : https://web.stanford.edu/class/archive/cs/cs106a/cs106a.1152/lectures/Memory.pdf

API就是你的操作介面 set() get() ...

### JAVA memory layout
全部都heap去操作

JAVA memory usage:
https://web.stanford.edu/class/archive/cs/cs106a/cs106a.1152/lectures/Memory.pdf

### Constructor
JAVA中static真的只有一份 很像C++的global

#### Constoructor Changing
從爺爺到爸爸...呼叫各自的constructor
- Once the constructor of the subclass is invoked, JVM will invoke the constructor of its superclass, recursively.

- In this sense, we could say that every class is an immediate or a distant subclass of Object.

### Instance Memebers

- Be aware that data members and function members are declared w/o static in this lecture.
- They are called instance members, which are available only after one object is created.

### Static Memeber
Static members are ready once a class is loaded.
• For example, main().
• You may try static initialization blocks.4
• These members can be invoked directly by class name in
absence of any instance.
• For example, Math.PI.
• In particular, static methods perform algorithms.
• For example, Math.random() and Arrays.sort().
• Note that a static method can access other static members.
(Trivial.)
• However, static methods cannot access to instance members
directly. (Why?)


#### Singleton Pattern

### GC: Garbage Collection
GC is a daemon thread, which searches for those unreferenced
objects.
- An object is unreferenced when it is no longer referenced by any part of your program. (How?)
- To make the object unreferenced, simply assign null to the reference variable

- Note that you may invoke `System.gc()` to execute a deallocation procedure.
- However, frequent invocation of GC is time-consuming.

### Unified Modeling
Unified Modeling Language (UML) is a tool for specifying,
visualizing, constructing, and documenting the artifacts of
software systems, as well as for business modeling and other
non-software systems

Free software:
• http://staruml.io/ (available for all platforms)

starUML

#### HAS-A Relationship

If A uses B, then it is an aggregation, stating that B exists
independently from A.
• For example, knight ↔ sword; company ↔ employee.
• If A owns B, then it is a composition, meaning that B has no
meaning or purpose in the system without A. (We will see this
later.)
• For example, house ↔ room.
:::info
看不太懂Aggregation 和 composition差異
:::

#### IS-A RelationShip
JAVA是單一繼承
JAVA 萬物都是物件

### Super()
Recall that this is used to refer to the object itself.
• You can use super to refer to (non-private) members of the
superclass.
• Note that super() can be used to invoke the constructor of its
superclass, just similar to this().
### Overriding
- re-implement the method inherited from its superclass
- Note that you cannot override the static methods.(不能override static members)
- You should use the annotation11 @Override to help you


#### toString()
JAVA直接打印object 是跑出**hash code**
覆寫toString()
Point 打印範例

ArrayList不用給定大小

int[] A = new int[3];
ArrayList<Integer> B = new ArrayList<>();

system.out.println(A);
system.out.println(B);


#### 念法
A是一個指標 指到一個陣列 裡面每個元素都是integer
<----------
int[] A

### Polymorphism

The word polymorphism literally means “many forms.”
• One of OOP design rules is to separate the interface from
implementations and program to abstraction, not to
implementation.13
• Subtype polymorphism fulfills this rule.
• How to make a “single” interface for different
implementations?
• Use the superclass of those types as the placeholder.


## Why OOP ??
• OOP is the solid foundation of modern (large-scale) software
design.
• In particular, great reuse mechanism and abstraction are
realized by these three concepts:
• encapsulation isolates the internals (private members) from the
externals, fulfilling the abstraction and providing the sufficient
accessibility (public methods);
• inheritance provides method overriding w/o changing the
method signature;
• polymorphism exploits the superclass as a placeholder to
manipulate the implementations (subtype objects).
• We use PIE as the shorthand for these three concepts.

### Casting
For convenience, let U be a subtype of T.
compiler會讓你過(讓compiler閉嘴) 但是run time還是會GG
- solution: **instanceof**
- We can use instanceof to check if the referenced object is of the target type at runtime.

// GG
U u = (U) new T();


// OK
T t = new U();
U u = (U)t

calss T{}
class U extends T{};

### instaceof
為何繼承關係圖是孩子指向父親
:::info
可以知道那個人是不是你爸爸
:::

### final
:::info
很像const進階版
:::
A final variable is a variable which can be **initialized once** and
cannot be changed later.
• The compiler makes sure that you can do it only once.
• A final variable is often declared with static keyword and
treated as a constant, for example, Math.PI.
• A final method is a method which cannot be overridden by
subclasses.
• You might wish to make a method final if it has an
implementation that should not be changed and it is critical to
the consistent state of the object.
• A class that is declared final cannot be inherited.
• For example, again, Math
### abstract calsses
:::info
沒辦法被new
類似C++的 virtual
:::
An abstract class is a class declared abstract.
• Typically, abstract classes sit at the top of one class hierarchy,
acting as placeholders.21
• The abstract classes may have some methods without
implementation22 and declared abstract.
• They are abstract methods.
• If a class has one or more abstract methods, then the class
itself must be declared abstract.
• All abstract classes cannot be instantiated.
• When inheriting an abstract class, the editor could help you
recall every abstract methods.

abstract classs T{
    abstract void doAction();
}

斜體function代表abstract class

### 單一繼承(JAVA)
C++是多重繼承
object是java最大的父類別 只有定義一些最基本的函數


讓兩個都會飛的人有共同介面

這樣擴充很多會飛的東西 會很麻煩...

void getFly(Object o){
    if(instanceof Bird)
        ((Bird)o).fly();
    if(instanceof airplane)
        ((airplane)o).fly()
}

可以創共同介面的function
### Another IS-A Relationship: Interface Inheritance
:::info
因為JAVA是單一繼承，用來處理多重繼承的關係
interface定義出來後 要用implement去接 不想寫那API就要宣告abstract
https://openhome.cc/Gossip/Java/Interface.html
:::


### Autoboxing and UNboxing of Primitives
- The Java compiler automatically wraps the primitives in their wrapper types, and unwraps them where appropriate.

### package

package www.csie.ntu.edu.tw;
public class Util {
    void doAction1() {}
    public void doAction2() {}
    protected void doAction3() {}
    public static void doAction4() {}

}


## Hiding Fields

# 5/10
## imutable object
string

String str1 = "NTU"
str1.toLowerCase();

String str1 = "NTU"
str1 = str1.toLowerCase();

String str1 = "NTU"
String str2 = "ntu"
str1 = str1.toLowerCase();
System.out.println(str1 == str2); // 裡面裝的東西是否相同 記憶體位置是否相同? java沒有operator override 只能用equal
System.out.println(str1.equals(str2));

## package import and access controls
## nesting class
其實就是封裝

## anonymous class demo2(匿名類別
## iterator
### for(int n:arr)
### iterator pattern


### try-catch-finally

## Generic(泛型)
https://courses.cs.washington.edu/courses/cse331/19au/lectures/lec13-generics.pdf
CSE 331 Software & Implementation
### Fail Fast
python3.8幫你加type的檢查宣告

### Generics and subtyping
- convariance
add(num) 有可能是 add float dobule int ....
INT DOUBLE INT INT FLOAT ....
add進去可能會長得不一樣

- contravirance
get(num) 出來可能沒有關係

- E1是 E2的upper bound
- dst: producer

T extends E
? extends Type
T: producer
?: wildcard


List<Integer> dist1;
List<Number> dist2;
copyTo(dist1, dist2);

因為他存的是Object的位址
和C++的

String[] A;
String S1 = "CSIE"
String S2 = "NTU"

A[0] = S1;
A[1] = S2;


# 5/16
## comparing objects
https://courses.cs.washington.edu/courses/cse331/11sp/lectures/slides/04a-compare.pdf

- 為什麼相減沒辦法用double
- 浮點數在儲存時本來就有誤差(IEEE754)
- 有poker的sample code
- 有使用匿名函數(anonymous function)

    System.out.println(0.5 - 0.1 - 0.1 - 0.1 - 0.1 - 0.1)
    System.out.println(0.2 + 0.1)

不同語言的統計
https://0.30000000000000004.com/

NOTE: This trick doesn't work for doubles (but see Math.signum)
Sample code: ComparableDemo.zip

## Lambdas and streams
### Lambdas
Lambdas and streams (try StreamDemo.zip)

- 必須要是functionanlInterface才能使用lambdas
- 只能有一個抽象method

@FunctionalInterface
interface Operator {
     int compare
 }

- some functional interface
- `15-214`

- 匿名函數為什麼可以assign給變數?
- 很像C++的fucntino pointer

opearator XXX = (x,y) -> x - y;
xxx.compute(10, 20);

### Streams
幹 這個人是他馬的有病是不是...
- 可以直接call平行化的API

Euler 常數
:::info
e = 1/1 + 1/1*2 + 1/1*2*3 ....
:::

 // 1 .s = x + s   
 // 2. 合併 多個變一個 (s, x 變成只有s) 
.reduce((0.0), (s, x)-> s + x)

#### null pointer
quick sort發明者後悔的故事
https://www.oracle.com/technical-resources/articles/java/java8-optional.html

String version = "UNKNOWN";
if(computer != null){
  Soundcard soundcard = computer.getSoundcard();
  if(soundcard != null){
    USB usb = soundcard.getUSB();
    if(usb != null){
      version = usb.getVersion();
    }
  }
}

String name = computer.flatMap(Computer::getSoundcard)
                          .flatMap(Soundcard::getUSB)
                          .map(USB::getVersion)
                          .orElse("UNKNOWN");

OptionalXXX
如果dreference null也不會GG

## reflation && annotation
- reflection: 和template(gnerial)很像，但是他是run time 決定的，不是compiler time。

:::info
其實還是不太懂QQ
用一個程式創造另外一個程式
:::
### meta programming
如何更改private變數
所以其實java這邊沒有真的保護效果

suit.setAccessible(true)

https://userpages.uni-koblenz.de/~laemmel/pttcourse/slides/meta.pdf

- fields, methods, constructors

這樣就可以印型態出來

int[] A = new int[3];
println(A.getClass().getName())

# 5/17
Java classloader
[老錢, 老大難的Java ClassLoader再不理解就老了, 2018](https://juejin.im/post/5c04892351882516e70dcc9b)
:::info
和Androidmainfest.xml有關 會把該專案相依於某些套件寫出來
:::

Class<?> clz2 = Pocker.class;
Class<?> clz2 = Class.forName("Pocker"); //


### Metaprogramming vs metadata

### annotation
- 中文有人說這叫**標註**
- python叫decarator
- 盡量不要做大家重複的事情 code也會都長得差不多

@Test
@override
@Deprected


#### Junit
eclispe 可以new一個junit case單元測試
::info
Q: -0 * 0 == 0 ??
Ans: No
:::

class PockerTest {
    @Test
    void testGetRankOne(){
        Poker p = new Poker(suit.Club, Rank.eight);
        assertTrue(p.getRank() != Rank.eight);
    }
    
    // 如果把@Test拿掉 就不會測 (CTS有這樣嗎?
    @Test
    void testGetRankTwo(){
        Poker p = new Poker(suit.Club, Rank.eight);
        assertTrue(p.getRank() != Rank.eight);
    }
}

https://www.csie.ntu.edu.tw/~d00922011/java2/TinyJUnitDemo.zip

### JVM
[Java Virtual Machine](http://www.cse.psu.edu/~axs53/497b/lectures/lecture5.pdf)

[JVM](http://faculty.cse.tamu.edu/hlee/csce314/lec17-JVM.pdf)

- JVM的記憶體配置長什麼樣子呢?

- byte code
- loop unrolling
值得注意的是，他確實做了 unrolling，但是 unroll 後的結果是遞迴的函式呼叫，雖然這樣的遞迴呼叫基本上也是可已經過優化後轉變成最純粹的運算 (g++ 4.8 的話用 -O1 就可以了，而 g++ 4.8 的 loop unrolling 要在 -O2 才會做)，因此是好是壞很難說，端看使用的時機與場合。
https://shininglionking.blogspot.com/2014/10/c-loop-unrolling-using-metaprogramming.html

## Concuurent Programing
### Basics of operating systems(OS)
- processes and threds
- [process](https://web.cs.wpi.edu/~cs3013/c07/lectures/Section03-Processes.pdf)
- [thread](https://web.cs.wpi.edu/~cs3013/c07/lectures/Section04-Threads.pdf)

### concurrecy vs parallel
- parallel才是真的平行(可以同時多人工作
- batch : sequence
- concurrency: 介在concurrency and parallel
- kernel thread vs user thread
:::info
- 用nice加速?
- 綁process到某個cpu去工作?
:::

[operating system: three easy spices](http://pages.cs.wisc.edu/~remzi/OSTEP/)

- JAVA 語言原生就支援thread，不像C還要透過POSIX，不同的環境套件來支援。
- 新的java用thread pool去節省資源。
- 被指派的時候 那個thread才知道要做什麼 所以沒辦法用繼承的方式
- design pattern: runnable
- thread: worker
- runnable: run

new Thread(task).start()
new MyThread().start()
new MyThread().start()

- thread safe

# 5/23
## Java Threads
https://www.csie.ntu.edu.tw/~d00922011/java2/multithreading/JavaThreads.pdf
1. join() : main() have to wait until other thread finished
2. synchronization could work on full object or sub objects

### synchronized

### wait() and notiy()

- 有可能會有dead lock
- 多了一個notifyall() 去避免這問題

- 消除了deadlock所以有可能會有starvation
- 用aging 把一直等不到資源的process 增加他的priority

### join()

### interrupt()

### setDaemon()
- 背景執行:background

## JAVA Synchronization
有沒有辦法做出 gerneal的lock機制呢?
### semaphore
用donw()和up()去控制數量

https://www.csie.ntu.edu.tw/~d00922011/java2/multithreading/SemaphoreDemo.java

### acquire, release
`A2.acquire()` <=> `down()`
`A1.release()` <=> `up()`

### Additive semaphore
是不是可以不要+1 -1
讓我們來個+2 -3 之類的

### Torvalds
[之前和工程師吵架](https://www.ithome.com.tw/news/135226)
Linus Torvalds, a reply to discussion about spinlock implementation and Linux scheduler
([1](https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723), [2](https://www.realworldtech.com/forum/?threadid=189711&curpostid=189752), [3](https://www.realworldtech.com/forum/?threadid=189711&curpostid=189755), [4](https://www.realworldtech.com/forum/?threadid=189711&curpostid=189759)), 2020.1.3 (also read news)

其他相關知識:
[Java多執行緒的基本知識](https://popcornylu.gitbooks.io/java_multithread/content/)
- Synchronization
- Threads pools
- Asynchronous

- Automic Integer
- 可以宣告變數是automic

## Socket Programming
- 聊天室
https://www.csie.ntu.edu.tw/~d00922011/java2/multithreading/client_server_model_sample.zip

linux13.csie.ntu.edu.tw

# 5/24
## data structures and algorithms
- inorder() and postorder() 可以決定唯一的tree
-
## Asymptotic notation
### big-O
### 名詞

### exponetial time
- TSP(Traveling Salesman Problem)
- Halting Problem
- 所有演算法　都可以在電腦上面執行嗎？(必須要在有限時間內做完)
- https://zh.wikipedia.org/wiki/%E5%81%9C%E6%9C%BA%E9%97%AE%E9%A2%98
### 對數演算法
https://www.csie.ntu.edu.tw/~d00922011/java/log-time_algorithm.pdf

### NP問題
驗證是polynomail time
但是解題是exponential time

- Ｈamitonal cyccle
- TSP(多了預算要考慮)
- 現實生活中：
- 驗證密碼（很快）
- 破解密碼（exponential time）

### Amortized analysis.
- 均攤時間


### infix, prefix, postfix

### Prority Queue

Heap
- Insert()
- Delete()

### HeapSort
heapsort
https://www.bigocheatsheet.com/

# 5/30
## DS
### Iterator

### Heap Sort
- 空間固定(in-place)
- unstable 所以實務上不好用 因為實際搜索的東西都是多個欄位


:::info
Max Heap的特徵是「第一個node具有最大值」，如果要將資料「由小到大」排序，步驟如下：

- 把「第一個node」和「最後一個node」互換位置。
- 假裝heap的「最後一個node」從此消失不見。
- 對「第一個node」進行MaxHeapify()。
:::success
ref:
https://alrightchiu.github.io/SecondRound/comparison-sort-heap-sortdui-ji-pai-xu-fa.html#hs
:::
### stable

### collision
https://www.csie.ntu.edu.tw/~d00922011/java2/CollisionSystem.zip

### quick sort
quick srot = BST + inorder traversal

### 2-3 tree
用把node往上升的方式 解決skewed tree問題
- 用rotate去完成這件事

### red black tree

對各種樹形結構的總結
https://warmgrid.github.io/2019/06/14/about-trees.html

## Design Pattern
https://github.com/kib06277/Head-First-Design-Patterns

# 5/31

## hashing
https://algs4.cs.princeton.edu/lectures/keynote/34HashTables.pdf

-7 % 3　會是多少

- signed integer 的最大或最小

int x = 0x7fffffff;
int y = 0x80000000;

system.print.out(x)
system.print.out(y)
system.print.out(Math.abs(y))

https://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C


### 單向雜湊函數(One-way Hash Functions).
去很容易　回來很難

### Cuckoo Hashing

cuckoo hashing处理碰撞的方法，就是把原来占用位置的这个元素踢走，不过被踢出去的元素还要比鸟蛋幸运，因为它还有一个备用位置可以安置，如果备用位置上 还有人，再把它踢走，如此往复。直到被踢的次数达到一个上限，才确认哈希表已满，并执行rehash操作。
http://blog.foool.net/2012/05/cuckoo-hash-%E5%B8%83%E8%B0%B7%E9%B8%9F%E5%93%88%E5%B8%8C/

## Graph
### un-directed Graph
https://algs4.cs.princeton.edu/lectures/keynote/41UndirectedGraphs.pdf

influence maximizatino problem
找網紅可以影響最多的範圍

- DFS
- BFS
- bipartite graph
- 七橋問題(edge走完)

- Ｈamitoniam Cycle(點走完)
- 點要走完 但要考慮edge cost(TSP)

- Page Rank
- Web crawler output
https://sites.google.com/site/jiyinyansuanfa/gong-zuo-nei-rong/lue-xing-tui-xiao-yuan-wen-ti-tsp-cheng-shi-jie-mian-hua

- Topological sort
- Directed Acyclic Graph （ DAG ）
- 在枚舉所有排列的問題之中，如果我們另外再限制誰要排在誰前方、誰要排在誰後方，那麼在這些限制之下，合理的排列還會剩下哪些呢？
- Minimum spanning tree
- Krustal's alogorithm
- Prim's algo
- 大部分用priority queue去實作
- Shortest Path
- Dijkrsta's algo
- bellman forward

- Combinational Search

- backtracking
- 八皇后問題
- TSP
- SAT

- DP
- maximum flow
- minimum cut

https://www.csie.ntu.edu.tw/~d00922011/java2/Vivian/181004_DynamicProgramming1.pdf

# 6/6

# 6/7

# 6/13
## Design Pattern
老師推薦這兩本書
Head first design patterns, 2014, O'Reilly (中文翻譯版)
Dive Into Design Patterns

https://github.com/kib06277/Head-First-Design-Patterns

- power point
## Design patterns by example,
- strategy, bridge, and factory design patterns
- https://www.cs.colorado.edu/~kena/classes/5448/f12/lectures/07-designpatterns.pdf

### Duck

- 把要用的東西抽出來 放在interfaces 需要的人自己去實作

- inheritance
- 不是每個sub class都有這個性質


### strategy
- favor delegation over inheritance
- setFlyBehavior()可以run time去改變飛的行為
- 把會變動的東西抽離出來

- structure of strategy(策略設計模式)

### bridge
把東西拆成 service去工作
bridge proxy adapter

### factory


### model view controller(MVC)

http://www.cs.cornell.edu/courses/cs3152/2013sp/lectures/11-ArchitecturePatterns.pdf

### Reactive Programming
netflix 處理串流
https://www.slideshare.net/kasun04/reactive-programming-in-java-8-with-rxjava

### Restful API
spring : java 平台的open source 的full stack應用程式框架 與 控制反轉的container實現

## others
快速review 每種design pattern
https://link.springer.com/content/pdf/bbm:978-1-4302-0725-2/1.pdf

### anotation
用這技巧 不用改LOG的CODE

### spring

### Profiling
VisualVM
Java Microbenchmark Harness (JMH)
Jenkov, JMH Tutorial