Saturday, October 27, 2007

Thuật toán sắp xếp: Quick Sort (P.2)

Thuật toán Quick Sort
o Ý tưởng
Ta chọn một phần tử bất kỳ của mảng A giả sử đó là x
Lọc và chia mảng đó thành 3 mảng con:
- mảng A1: A1(i) <>
- mảng A2: A2(i) = x với mọi i
- mảng A3: A3(i) > x với mọi i
Sau đó ta lại tiếp tục các bước trên với mảng A1 và A3. Công việc này còn được gọi là phân hoạch nên Quick Sort còn được gọi là sắp xếp theo phương pháp phân hoạch
Giải thuật này sẽ được cài đặt theo phương pháp đệ qui

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function quickSort(A, lower, upper){
x = A[(lower + upper) / 2];
i = lower;
j = upper;
do{
while(A[i] <>
i ++;
while (A[j] > x)
j --;
if (i <= j){
swap(A[i], A[j]);
i ++;
j --;
}
}while(i <= j);
if (j > lower)
quickSort(A, lower, j);
if (i <>
quickSort(A, i, upper);
}


o Độ phức tạp tính toán: O(nlnn)

Thuật toán Quick Sort tốt nhất trong trường hợp dãy hầu như được sắp xếp và với n khá lớn. Vì vậy ta thường dung Quick Sort trong giai đoạn đầu để phân hoạch, khi đoạn con đủ nhỏ ta sẽ dùng các phương pháp khác để sắp xếp

Friday, October 26, 2007

Sắp xếp mảng (P.1)

Sắp xếp mảng số nguyên một chiều A theo thứ tự tăng dần (hoặc giảm dần)


1.Thuật toán sắp xếp kiểu chọn lựa
o Ý tưởng
Giả sử ta đã sắp xếp mảng cho đến phần tử thứ i – 1 theo thứ tự tăng dần.
Ở bước thứ i ta chọn phần tử có giá trị nhỏ nhất trong đoạn A[i..n], giả sử A(j), ta thực hiện đổi chỗ A(i) với A(j)

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
for(i = 1; i <>
j = i;
for(k = i + 1; k <= n; k ++)
if (A[k] <>
j = k;
swap(A[i], A[j]);
}
}



o Độ phức tạp tính toán: O(n2)

2. Thuật toán sắp xếp kiểu chèn
o Ý tưởng
Giả sử ta đã sắp xếp mảng cho đến phần tử thứ i -1 theo thứ tự tăng dần.
Ở bước thứ i sẽ thực hiện chèn giá trị A(i) vào dãy con A[1..i] sao cho dãy vẫn giữa được trật tự sắp xếp cũ (ý tưởng như vậy ta xếp các quân bài Tú – lơ – khơ từ 1 đến K)
Ta thực hiện như sau: Xuất phát từ j = i -1 xét trở về phía trước
- nếu A(j) <= x = A(i): ta đặt x vào vị trí j + 1
- nếu A(j) > x: ta gán A(j) vào cho A(j + 1), sau đó quay về phía trước 1 phần tử và tiếp tục lại quá trình này
Để bài toán thực hiện được theo ý tưởng này thì ở đầu mảng phải có 1 phần tử làm mốc A(0) không phải thuộc mảng gốc, nó chỉ đóng vai trò là giá trị ‘vô cực’ mà thôi

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
A[0] = VO_CUNG;
for(i = 2; i <= n; i++){
x = A[i];
j = i – 1;
while(x <>
A[j + 1] = A[j];
j --;
}
A[j] = x;
}
}


o Độ phức tạp tính toán: O(n2)

3. Thuật toán sắp xếp kiểu nổi bột hay đổi chỗ
o Ý tưởng
Giả sử ta đã sắp xếp được mảng đến phần tử i – 1
Tại bước i, ta sẽ duyệt đoạn A[i..n] từ n trở về i, nếu A(j – 1) > A(j) thì đổi chỗ, sau khi duyệt xong đoạn A[i..n] thì đoạn từ 1 đến i được sắp xếp

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
for(i = 2; i <= n; i++)
for(j = n; j > i; j--)
if (A[j] <>
swap(A[j], A[j - 1]);
}



Ta cũng có thể cải tiến một chút giải thuật trên, mặc dù độ phức tạp tình toán vẫn vậy. Đến khi nào không thấy có việc đổi chỗ nữa (đoạn sau đã có thứ tự sắp xếp thỏa mãn thì ta dừng luôn)

function sort(A){
i = 2;
do{
flag = true;
for (j = n; j > i; j--)
if (A[j] <>
swap(A[j], A[j - 1]);
flag = false;
}

i ++;
}while (flag = true);
}


o Độ phức tạp tính toán: O(n2)

Tìm kiếm trên mảng

1. Thuật toán tìm kiếm nhị phân
o Bài toán
Cho một mảng các số được sắp xếp tăng dần (giảm dần), cho một giá trị x, xác định xem x có thuộc mảng đó hay không

o Ý tưởng
Giả sử mảng sắp xếp tăng dần A, ta chia đôi mảng, so sánh x với phần tử ở giữa A[mid], nếu:
- x == A[mid] : return true
- x > A[mid]: tiếp tục tìm x trong nửa mảng bên phải
- x < A[mid]: tiếp tục tìm x trong nửa mảng bên trái

o Mô tả thuật toán
- Input: mảng A[1..n] giá trí x
- Output:
+ x thuộc A: true
+ else false
- Method :
function binarySearch(A, x, first, last){
if (first > last)

return false;
else{
mid = (first + last) / 2;
if (x == A[mid])
return true;
else if (x < A[mid])
return binarySearch (A, x, first, mid - 1);
else
return binarySearch (A, x, mid + 1, last);
}
}

o Độ phức tạp tính toán: O(lgn)

2. Thuật toán tìm Min Max
o Bài toán
Tìm giá trí Min và Max trong đoạn [left, right] của mảng A[1,n]

o Ý tưởng
Chia mảng đoạn [left, right] thành 2 phần, tìm Min và Max trong 2 phần đó sau đó so sánh 2 kết quả này với nhau. Tiếp tục việc chia 2 cho đến khi đoạn chia chỉ còn 1 phần tử thì Min = Max và bằng phần tử đó

o Mô tả thuật toán
- Input: Mảng A[1..n]
Left và Right
- Output:
Min và Max của đoạn [Left, Right]
- Method:

function minMax(A, left, right, Min, Max){
if (left == right)
Min = Max = A[left];
else{
minMax(A, left, (right + left) / 2, Min1, Max1);
minMax(A, (right + left) / 2 + 1, right, Min2, Max2);
if (Min1 > Min2)
Min = Min2;
else
Min = Min1;
if(Max1 > Max2)
Max = Max1;
else
Max = Max2;
}
}

o Độ phức tạp tính toán: O(n)

Wednesday, September 26, 2007

Các mẫu thiết kế hướng đối tượng (P.4)

Structural Pattern

Các mẫu Structural diễn tả một cách có hiệu quả cả việc phân chia hoặc kết hợp các phần tử trong một ứng dụng. Những cách mà các mẫu Structural áp dụng vào ứng dụng rất rộng: ví dụ, mẫu Adapter có thể làm cho hai hệ thống không tương thích có thể giao tiếp với nhau, trong khi mẫu Façade cho phép bạn làm đơn giản hóa một giao tiếp để sử dụng mà không cần gỡ bỏ tất cả các tùy biến đã có trong hệ thống



3.1. Adapter Pattern

- Ý nghĩa
Tạo một giao diện trung gian để gắn kết vào hệ thống một lớp đối tượng mong muốn nào đó.

- Cấu trúc mẫu




Trong đó:
o Tagret là một interface định nghĩa chức năng, yêu cầu mà Client cần sử dụng
o Adaptee là lớp chức các chức năng mà Target cần sử dụng để tạo ra được chức năng mà Target cần cung cấp cho Client
o Adapter thực thi từ Target và sử dụng đối tượng lớp Adaptee, Apdater có nhiệm vụ gắn kết Adaptee vào Target để có được chức năng mà Client mong muốn

- Trường hợp ứng dụng
o Muốn sử dụng 1 lớp có sẵn nhưng giao tiếp của nó không tương thích với yêu cầu hiện tại
o Muốn tạo 1 lớp có thể sử dụng lại mà lớp này có thể làm việc được với những lớp khác không liên hệ gì với nó, và là những lớp không cần thiết tương thích trong giao diện.


- Ví dụ mẫu
- Xét ví dụ: ta có một hệ thống PhoneTarget cần thực hiện một chức năng gì đó, trong đó có một phương thức trả về số điện thoại trong một chuỗi đầu vào
- Trước đó ta đã có một lớp có một chức năng là lấy các kí tự số trong một chuỗi
- Giờ ta muốn sử dụng chức năng lấy kí tự số vào hệ thống lấy số điện thoại



public interface PhoneTarget{

public String getPhoneNumber(String message);//lấy số điện thoại trong 1 chuỗi 

}


public GetNumberAdaptee{

public String getNumber(String str){

//lấy ra dạng số trong 1 chuỗi

<…get number>

}


}


public Adapter implements PhoneTarget{

public String getPhoneNumber(String message){

GetNumberAdaptee obj = new GetNumberAdaptee;

String str = obj.getNumber(message);

return “84”+str;

}

}


3.2. Bridge Pattern
- Ý nghĩa
Một thành phần trong OOP thường có 2 phần: phần ảo – định nghĩa các chức năng và phần thực thi – thực thi các chức năng được định nghĩa trong phần ảo. Hai phần này liên hệ với nhau qua quan hệ kế thừa. Những thay đổi trong phần ảo dẫn đến các thay đổi trong phần thực thi.
Mẫu Bridge được sử dụng để tách thành phần ảo và thành phần thực thi riêng biệt, do đó các thành phần này có thể thay đổi độc lập và linh động. Thay vì liên hệ với nhau bằng quan hệ kế thừa hai thành phần này liên hệ với nhau thông qua quan hệ “chứa trong”.

- Cấu trúc mẫu


Trong đó:
o Abstraction: là lớp trừu tượng khai báo các chức năng và cấu trúc cơ bản, trong lớp này có 1 thuộc tính là 1 thể hiện của giao tiếp Implementation, thể hiện này bằng các phương thức của mình sẽ thực hiện các chức năng abstractionOp() của lớp Abstraction
o Implementation: là giao tiếp thực thi của lớp các chức năng nào đó của Abstraction
o RefineAbstraction: là định nghĩa các chức năng mới hoặc các chức năng đã có trong Absrtaction.
o ConcreteImplement: là các lớp định nghĩa tường minh các thực thi trong lớp giao tiếp Implementation

- Trường hợp ứng dụng
o Khi bạn muốn tạo ra sự mềm dẻo giữa 2 thành phần ảo và thực thi của một thành phần, và tránh đi mối quan hệ tĩnh giữa chúng
o Khi bạn muốn những thay đổi của phần thực thi sẽ không ảnh hưởng đến client
o Bạn định nghĩa nhiều thành phần ảo và thực thi.
o Phân lớp con một cách thích hợp, nhưng bạn muốn quản lý 2 thành phần của hệ thống một các riêng biệt

- Ví dụ mẫu



class  MyAbstraction{

private MyImplementation myImp;

public void method01(){

myImp.doMethod1();

}

public String method2(){

myImp.doMethod2();

}

}


interface class MyImplementation{

public void doMethod1();

public String doMethod2();

}


class RefineAbstraction1 extends MyAbstraction{

//các định nghĩa riêng, tường minh

}

class ConcreteImpleA extend MyImplement{

//các định nghĩa riêng, tường minh

}

class RefineAbstraction2 extends MyAbstraction{

//các định nghĩa riêng, tường minh

}

class ConcreteImpleB extend MyImplement{

//các định nghĩa riêng, tường minh

}



3.3. Composite Pattern
- Ý nghĩa
Mẫu này nhằm gom các đối tượng vào trong một cấu trúc cây để thể hiện được cấu trúc tổng quát của nó. Trong khi đó cho phép mỗi phần tử của cấu trúc cây có thể thực hiện một chức năng theo một giao tiếp chung
- Mô hình mẫu


Trong đó:

o Component: là một giao tiếp định nghĩa các phương thức cho tất cả các phần của cấu trúc cây. Component có thể được thực thi như một lớp trừu tượng khi bạn cần cung cấp các hành vi cho tất cả các kiểu con. Bình thường, các Component không có các thể hiện, các lớp con hoặc các lớp thực thi của nó, gọi là các nốt, có thể có thể hiện và được sử dụng để tạo nên cấu trúc cây
o Composite: là lớp được định nghĩa bởi các thành phần mà nó chứa. Composite chứa một nhóm động các Component, vì vậy nó có các phương thức để thêm vào hoặc loại bổ các thể hiện của Component trong tập các Component của nó. Những phương thức được định nghĩa trong Component được thực thi để thực hiện các hành vi đặc tả cho lớp Composite và để gọi lại phương thức đó trong các nốt của nó. Lớp Composite được gọi là lớp nhánh hay lớp chứa
o Leaf: là lớp thực thi từ giao tiếp Component. Sự khác nhau giữa lớp Leaf và Composite là lớp Leaf không chứa các tham chiếu đến các Component khác, lớp Leaf đại diện cho mức thấp nhất của cấu trúc cây
- Trường hợp ứng dụng
o Khi có một mô hình thành phần với cấu trúc nhánh - lá, toàn bộ - bộ phận, ...
o Khi cấu trúc có thể có vài mức phức tạp và động
o Bạn muốn thăm cấu trúc thành phần theo một cách qui chuẩn, sử dụng các thao tác chung thông qua mối quan hệ kế thừa
- Ví dụ mẫu
Trở lại ví dụ về dự án, một Project(Composite) có nhiều tác vụ Task(Leaf), ta cần tính tổng thời gian của dự án thông qua thời gian của tất cả các tác vụ



public interface TaskItem{

public double getTime();

}

public class Project implements TaskItem{

private String name;

private ArrayList subtask = new ArrayList();

public Project(){ }

public Project(String newName){

name = newName;

}    

public String getName(){ return name; }

public ArrayList getSubtasks(){ return subtask; }

public double getTime(){

double totalTime = 0;

Iterator items = subtask.iterator();

while(items.hasNext()){

TaskItem item = (TaskItem)items.next();

totalTime += item.getTime();

}

return totalTime;

}

public void setName(String newName){ name = newName; }

public void addTaskItem(TaskItem element){

if (!subtask.contains(element)){

subtask.add(element);

}

}

public void removeTaskItem(TaskItem element){

subtask.remove(element);

}

}

public class Task implements TaskItem{

private String name;

private double time;

public Task(){ }

public Task(String newName, double newTimeRequired){

name = newName;

time = newTimeRequired;

}

public String getName(){ return name; }

public double getTime(){

return time;

}

public void setName(String newName){ name = newName; }

public void setTime(double newTimeRequired){ time = newTimeRequired; }

}



3.4. Decorator Pattern
- Ý nghĩa
Bổ sung trách nhiệm cho đối tượng tại thời điểm thực thi. Đây được xem là sự thay thế hiệu quả cho phương pháp kế thừa trong việc bổ sung trách nhiệm cho đối tượng và mức tác động là ở mức đối tượng thay vì ở mức lớp như phương pháp kế thừa.

- Mô hình mẫu


Trong đó:
o Component: là một interface chứa các phương thức ảo (ở đây là defaultMethod)
o ConcreteComponent: là một lớp kế thừa từ Component, cài đặt các phương thức cụ thể (defaultMethod được cài đặt tường minh)
o Decorator: là một lớp ảo kế thừa từ Component đồng thời cũng chứa 1 thể hiện của Component, phương thức defaultMethod trong Decorator sẽ được thực hiện thông qua thể hiện này.
o ConcreteDecoratorX: là các lớp kế thừa từ Decorator, khai báo tường minh các phương thức, đặc biệt trong các lớp này khai báo tường minh các “trách nhiệm” cần thêm vào khi run-time

- Trường hợp ứng dụng
o Khi bạn muốn thay đổi động mà không ảnh hưởng đến người dùng, không phụ thuộc vào giới hạn các lớp con
o Khi bạn muốn thành phần có thể thêm vào hoặc rút bỏ đi khi hệ thống đang chạy
o Có một số đặc tính phụ thuộc mà bạn muốn ứng dụng một cách động và bạn muốn kết hợp chúng vào trong một thành phần

- Ví dụ
Gỉa sử trong thư viện có các tài liệu: sách, video... Các loại tài liệu này có các thuộc tính khác nhau, phương thức hiển thị của giao tiếp LibraryItem sẽ hiển thị các thông tin này. Giả sử , ngoài các thông tin thuộc tính trên, đôi khi ta muốn hiển thị độc giả mượn một cuốn sách (chức năng hiển thị độc giả này không phải lúc nào cũng muốn hiển thị), hoặc muốn xem đoạn video(không thường xuyên).


Giao tiếp LibraryItem định nghĩa phương thức display() cho tất cả các tài liệu của thư viện



public interface LibraryItem{

public void display();   // đây là defaultMethod

}


Các lớp tài liệu



public class Book implements LibraryItem{

private String title;

private int page;

public Book(String s, int p){

title = s;

page = p;

}

public void display(){

System.out.println("Title: " + title);

System.out.println("Page number: " + page);

}

}

public class Video implements LibraryItem{

private String title;

private int minutes;

public Video(String s, int m){

title = s;

minutes = m;

}

public void display(){

System.out.println("Title: " + title);

System.out.println("Time: " + minutes);

}

}



Lớp ảo Decorator thư viện



public abstract class LibDecorator implements LibraryItem{

private LibraryItem libraryitem;

public LibDecorator(LibraryItem li){

libraryitem = li;

}

public void display(){

libraryitem.display();

}

}



Các lớp Decorator cho mỗi tài liệu thư viện cần bổ sung trách nhiệm ở thời điểm run-time



public class BookDecorator extends LibDecorator{

private String borrower;

public BookDecorator(LibraryItem li, String b){

super(li);

borrower = b;

}

public void display(){

super.display();

System.out.println("Borrower: " + borrower);

}

}

public class VideoDecorator extends LibDecorator{

public VideoDecorator(LibraryItem li){

super(li);

}

public void display(){

super.display();

play(); //phương thức play video

}

}


3.5. Facade Pattern
- Ý nghĩa
Cung cấp một giao tiếp hợp nhất của một tập các giao tiếp trong hệ thống con. Façade định nghĩa một giao tiếp mức cao hơn để làm cho hệ thống con dễ sử dụng

- Mô hình mẫu



Trong đó
o Class1Class2 là các lớp đã có trong hệ thống
o Façade là lớp sử dụng các phương thức của Class1 và Class2 để tạo ra một giao diện mới, thường được sử dụng, đỡ phức tạp hơn khi sử dụng riêng Class1 và Class2

- Trường hợp ứng dụng
o Làm cho một hệ thống phức tạp dễ sử dụng hơn bằng cách cung cấp một giao tiếp đơn gian mà không cần loại bỏ các lựa chọn phức tạp
o Giảm bớt sự ràng buộc giữa client và các hệ thống con
- Ví dụ mẫu
Giả sử hệ thống cũ đã có các lớp: Địa chỉ, Số điện thoại, Tên tuổi về thông tin của một người, giờ ta muốn quản lý các thông tin trên của một người, ta tận dụng lại hệ thống cũ, xây một lớp Người sử dụng lại các lớp ở trên.




3.6. Flyweight Pattern
- Ý nghĩa
Làm phương tiện dùng chung để quản lý một cách hiệu quả một số lượng lớn các đối tượng nhỏ có các đặc điểm chung, mà các đối tượng nhỏ này lại được sử dụng tuỳ thuộc vào hoàn cảnh, điều kiện ngoài.

- Mô hình mẫu


Trong đó:
o FlyweightFactory: tạo ra và quản lý các đối tượng Flyweight
o Flyweight là một giao tiếp định nghĩa các phương thức chuẩn
o ConcreteFlyweightX: là các lớp thực thi của Flyweight, các thể hiện của các lớp này sẽ được sử dụng tuỳ thuộc vào điều kiện ngoài.

- Trường hợp sử dụng
o Ứng dụng sử dụng nhiều đối tượng giống hoặc gần giống nhau
o Với các đối tượng gần giống nhau, những phần không giống nhau có thể tách rời với các phần giống nhau để cho phép các phần giống nhau có thể chia sẻ
o Nhóm các đối tượng gần giống nhau có thể được thay thế bởi một đối tượng chia sẻ mà các phần không giống nhau đã được loại bỏ
o Nếu ứng dụng cần phân biệt các đối tương gần giống nhau trong trạng thái gốc của chúng

- Ví dụ mẫu
Một ví dụ cổ điển của mẫu flyweight là các kí tự được lưu trong một bộ xử lí văn bản (word processor). Mỗi kí tự đại diện cho một đối tượng mà có dữ liệu là loại font (font face), kích thước font, và các dữ liệu định dạng khác. Bạn có thể tưởng tượng là, với một tài liệu (document) lớn với cấu trúc dữ liệu như thế này thì sẽ bộ xử lí văn bản sẽ khó mà có thể xử lí được. Hơn nữa, vì hầu hết dữ liệu dạng này là lặp lại, phải có một cách để giảm việc lưu giữ này - đó chính là mẫu Flyweight. Mỗi đối tượng kí tự sẽ chứa một tham chiếu đến một đối tượng định dạng riêng rẽ mà chính đối tượng này sẽ chứa các thuộc tính cần thiết. Điều này sẽ giảm một lượng lớn sự lưu giữ bằng cách kết hợp mọi kí tự có định dạng giống nhau trở thành các đối tượng đơn chỉ chứa tham chiếu đến cùng một đối tượng đơn chứa định dạng chung đó.



Giao tiếp Character định nghĩa phương thức vẽ một kí tự



public interface Character {

public void draw();

}



Lớp kí tự thực thi từ giao tiếp Character
Sở dĩ ta định nghĩa Character và ConcreteCharacter riêng là vì trong cấu trúc sẽ có một phần nữa: phần không giống nhau giữa các đối tượng Character (mà ta không bàn tới)



public class ConcreteCharacter implements Character{

private String symbol;

private String font;

public ConcreteCharacter(String s, String f){

this.symbol = s;

this.font = f;

}

public void draw() {

System.out.println("Symbol " + this.symbol + " with font " + this.font );

}

}


Lớp khởi tạo các kí tự theo symbol và font, mỗi lần khởi tạo nó sẽ lưu các đối tượng này vào vùng nhớ riêng của nó, nếu đối tượng ký tự symbol + font đã có thì nó sẽ lấy ra chứ không khởi tạo lại



import java.util.*;

public class CharacterFactory {

private Hashtable pool = new Hashtable();

public int getNum() {

return pool.size();

}

public Character get(String symbol, String fontFace) {

Character c;

String key = symbol + fontFace;

if ((c = (Character)pool.get(key)) != null) {

return c;

} else {

c = new ConcreteCharacter(symbol, fontFace);

pool.put(key, c);

return c;

}

}

}


Lớp Test



import java.util.*;

public class Test {

public static void main(String[] agrs) {

CharacterFactory characterfactory = new CharacterFactory();

ArrayList text = new ArrayList();

text.add(0, characterfactory.get("a", "arial"));

text.add(1, characterfactory.get("b", "time"));

text.add(2, characterfactory.get("a", "arial"));

text.add(0, characterfactory.get("c", "arial"));

for (int i = 0; i <>
Character c = (Character)text.get(i);
c.draw();
}
}
}



Như vậy 'a' + 'arial' gọi 2 lần như chỉ khởi tạo có 1 lần mà thôi

3.7. Proxy Pattern
- Ý nghĩa
Đại diện một đối tượng phức tạp bằng một đối tượng đơn giản, vì các mục đích truy xuất, tốc độ và bảo mật

- Mô hình mẫu


Trong đó:
o Service: là giao tiếp định nghĩa các phương thức chuẩn cho một dịch vụ nào đó
o RealService: là một thực thi của giao tiếp Service, lớp này sẽ khai báo tường minh các phương thức của Service, lớp này xem như thực hiện tốt tất cả các yêu cầu từ Service
o Proxy: kế thừa Service và sử dụng đối tượng của RealService

- Trường hợp ứng dụng
o Sử dụng mẫu Proxy khi bạn cần một tham chiếu phức tạp đến một đối tượng thay vì chỉ một cách bình thường
o Remote proxy – sử dụng khi bạn cần một tham chiếu định vị cho một đối tượng trong không gian địa chỉ(JVM)
o Virtual proxy – lưu giữ các thông tin thêm vào về một dịch vụ thực vì vậy chúng có thể hoãn lại sự truy xuất vào dịch vụ này
o Protection proxy – xác thực quyền truy xuất vào một đối tượng thực

- Ví dụ mẫu
Ví dụ lớp Image là một interface định nghĩa các phương thức xử lý ảnh, nó có các lớp con là GIFImage và JPGImage.
Theo hướng đối tượng thì thiết kế như thế có vẻ hợp lý, Client chỉ cần sử dụng lớp Image là đủ, còn tuỳ thuộc vào loại ảnh sẽ có các phương thức khác nhau
Nhưng trong trường hợp, trên ứng dụng web chẳng hạn, một lúc ta đọc lên hàng trăm ảnh các loại và ta còn muốn xử lý tuỳ vào một điều kiện nào đó (ví dụ chỉ xử lý khi là ảnh JPG hoặc GIF). Nếu ta đặt điều kiện IF Image (sau đó sẽ tùy điều kiện này rồi xử lý riêng) thì không hợp lý, nếu đặt trong Client, nếu mỗi lần cần thay đổi IF ta lại sửa Client => không hợp lý khi Client là một ứng dụng lớn.

Ta sử dụng Proxy, lớp ImageProxy chỉ là lớp đại diện cho Image, kế thừa từ Image và sử dụng các lớp GIFImage hay JPGImage. Khi cần thay đổi ta chỉ cần thay đổi trên Proxy mà không cần tác động đến Client và Image.





public interface Image {

public void process();

}

public class JPGImage implements Image {

public void process() {

System.out.print("JPG Image");

}

}

public class GIFImage implements Image {

public void process() {

System.out.print("GIF Image");

}

}

public class ImageProxy implements Image {

private Image image;

public void process() {

if (image == null)

image = new JPGImage();//tạo đối tượng ảnh JPG, chỉ mang tính minh họa

image.process();

}

}



Ở đây ta sẽ xử lý khi Image là ảnh JPG trong trường hợp muốn thay đổi ta sẽ thay đổi ở ImageProxy và client sẽ không bị ảnh hưởng
* Đây là ví dụ cho trường hợp Virtual Proxy