Lập trình

Lập trình

Thứ Bảy, 30 tháng 12, 2017

RAII (Resource Acquisition is Initialisation) - Cách thức quản lý tài nguyên trong C++

Bạn đã bao giờ gặp rắc rối trong việc quản lý tài nguyên trong C++, ví dụ như bộ nhớ ? Trong 1 project lớn nếu không quản lý bộ nhớ tốt sẽ rất dễ xảy ra memory leak. Mà nếu bạn có cẩn thận quản lý bộ nhớ thì với cách quản lý thông thường với new và delete sẽ rất mệt khi chúng ta cấp phát nhiểu lần và mỗi lần delete chúng ta phải cần biết bộ nhớ đó đã được delete trước đó chưa.

RAII trong C++ cung cấp một cách quản lý lý tài nguyên rất tốt - với phương châm, khởi tạo tài nguyên phải đặt trong hàm constructor hoặc một hàm của một biến local (trong stack) nào đó. Giải phóng tài nguyên phải đặt trong destructor của biến local (stack) nào đó.

Trước tiên hãy xem code dưới đây. Điều gì sẽ xảy ra ? Chắc chắn function sẽ chạy đến dòng throw Exception. Đồng nghĩa với việc bộ nhớ của MyClass Object được cấp phát bởi new không được thu hồi, từ đó dẫn đến việc bị Memory Leak.


Nhưng nếu ta sử dụng cấp phát tĩnh cho MyClass object (dung MyClass my(1)) thì sẽ không xảy ra Memory Leak vì nó là biến local nên nó sẽ tự gọi hàm hủy và dellocation bộ nhớ của nó khi ra khỏi không gian sống của nó (cụ thể đây là hàm myFunc()).

Dựa trên ý tưởng như vậy, Stroustrup cung cấp ý tưởng RAII trong C++, ý tưởng của nó là mọi tài nguyên mà chương trình cần được quản lý với local variabels (tức biến cục bộ), và hàm destructor của biến này sẽ hủy hết tài nguyên khi ra khỏi không gian sống của biến. Nó thực sự đơn giản và hữu ích, giúp chúng ta không phải lúc nào cũng nhớ new và delete song song, và với cách lập trình này nó rất có ích trong việc ngăn chặn memory leak.

Vậy tài nguyên ở đây là gì ? Nó có thể là bộ nhớ, file, ... .

Chúng ta cùng đến với một ví dụ :

class MyClass giả sử là class mà ta muốn định nghĩa để sử dụng trong chương trình.
class MyClassFactory là class định nghĩa object sẽ quản lý tài nguyên là bộ nhớ của biến đối tượng của MyClass.
class RaiiFactory ta chỉ cần định nghĩa một lần với template class mà có thể dùng cho tất cả mọi class khác với, class này cần 2 chức năng chính là create()hàm destructor, hàm create() cung cấp cho người dùng gọi mỗi lần muốn tạo một đối tượng mới của class MyClass, hàm destructor giải phóng hết bộ nhớ mà các đối tượng đang nắm giữ. Các hàm khởi tạo sao chép và toán tử gán được che giấu. Bạn có thể cái đặt nhiều chức năng khác cho class RaiiFactory như insert() hay delete một phần tử tại vị trí nào đó.
- create() chính là đại diện cho ý tưởng tài nguyên khởi tại bởi constructor hoặc một hàm của một biến
- destructor là thành phần quan trọng nhất trong RAII, thu hồi tài nguyên đặt trong destructor.

Chúng ta hãy nhìn vào hàm myFunc, giả sử đây là một chương trình, ta cần tài nguyên là 10 thực thể của class MyClass. Bình thường ta cấp phát với new và giải phóng bộ nhớ với delete, nhưng RAII không làm như vậy, RAII gộp các tài nguyên đưa vào biến local quản lý (ở đây là myFac nó thuộc class MyClassFactory). Muốn tạo tài nguyên mới ta gọi myFac.create().

Khi hàm myFunc() kết thúc, thì biến cục bộ myFac bị hủy đồng nghĩa với việc thuộc tính resources của nó bị hủy khi đó hàm hủy của resources cũng được gọi và mọi tài nguyên được giải phóng hết.
Kết quả:


Như vậy:
+ Ta đã lợi dụng được cách giải phóng bộ nhớ của biến local (trong stack) để giải phóng bộ nhớ cấp phát trong heap. Nó luôn giải phóng kể cả khi gặp Exception.
+ Ta đã tránh được new và delete tường minh. Khi đó khi code, bạn không cần hỏi chỗ này ta đã delete con trỏ trỏ đến heap chưa ?
+ Các thủ tuc allocation và deallocation được thực hiện tự động.
+ RAII có nghĩa là Resource được yêu cầu cấp phát trong constructor hoặc một số hàm (ta coi như class) và thu hồi (release) resource PHẢI được đặt trong destructor của class.
Nguồn tham khảo :
[1]https://www.codeproject.com/Articles/10141/RAII-Dynamic-Objects-and-Factories-in-C [2]https://www.tomdalling.com/blog/software-design/resource-acquisition-is-initialisation-raii-explained/

Thứ Bảy, 21 tháng 1, 2017

[Machine learning] K-means, giới thiệu về bài toán phân cụm

K-means

I. Tư tưởng
- Xét bài toán cho :
    + Một số K (number of cluster)
    + Tập data (X)
- Thuật toán K-means sẽ phân loại cho ta K cụm data, với mỗi một cụm sẽ có tâm (centroid) của nó.
- Ứng dụng : Phân loại đối tượng trong market, phân loại người dùng trong social network, ...

II. Thuật toán
- Input : K và tập data X
- Ta chọn random một tập K centroids (tức tâm của các cụm)
- Thuật toán gồm 2 bước chính :
+ findClosetCentroids : tạo một mảng ci có độ dài bằng số example trong tập data. ci chứa "nhãn" (số thứ tự từ 1..K) là centroid là example thứ i gần nhất. Công thức để xét xem tâm nào gần 1 example nhất là :
sum(power(example - centroids(1, :), 2)) (ở Octave/Matlab) // Với centroids là tập các centroid (tâm) của các cụm (cluster);example là 1example của tập data

+ ComputeCentroids : Tính lại tâm (move centroids) bằng cách : mỗi tâm (centroid) được tính lại bằng cách là trung bình cộng của tập data hiện tại trong cụm của nó.

III. Tối ưu
- Mục tiêu tối ưu của ta là hàm :
    J = (1 / m) * sum( sum(power(example - centroids(1, :), 2)) ) (code in Octave)
- 2 bước của thuật toán K-means sẽ minimize hàm trên.

IV. Randomly Initialize   
- Thuật toán K-means đặc biệt liên quan đến việc chọn cụm (cluster), vì vậy việc khởi tạo giá trị cho các cụm rất quan trọng, thông thường ta chọn K giá trị cho cụm nằm trong tập data m phần tử (k <= m). Nhưng việc khởi tạo như vậy rất nhiều rủi ro vì các cụm có thể hội tụ không như mong muốn. Như vậy ta có một cách để chọn được một cụm tối ưu, liên quan đến hàm mục tiêu (như đã trình bày ở mục III.)
- Mã giả :
   
    for i = 1 to 100  : // ta có thể thay 100 là 200, …
        Chọn K cluster có giá trị là K phần tử được lấy ngẫu nhiên trong tập data set
        Chạy K-means :
            + FindClosetCentroids
            + ComputeCentroids
        Tính hàm mục tiêu J
    Chọn cụm nào có hàm mục tiêu J nhỏ nhất trong các cụm đã tính ở trên .

- Trong octave có thể dùng lệnh sau để pick randomly K centroids từ tập data det X :
randidx = randperm(size(X, 1));
centroids = X(randidx(1:K), :);


V. Ứng dụng

Ví dụ : khi ta có một sites có 100000 thánh viên ta phân thành 10 cụm (thành viên tích cực, tương đối tích cực, ....) sau đó website sẽ có chế độ để "đối đãi " với từng cụm thành viên.
Hoặc ta có thể dùng K-means để nén ảnh: Khi ta có ảnh 3 channel : 128 * 128 khi đó ta đưa ảnh về 2 chiều : A * 3 với A = 128 * 128. Khi đó giả sử ta có 16 cụm 3 features, ta phân các pixels này vào các cụm, sau đó chuyển hết giá trị cả pixel trong cụm về giá trị của centroid của cụm đó.