Đánh giá độ phức tạp thuật toán – Algorithmic complexity

Ở bài trước, mình đã giới thiệu hai giải thuật khá căn bản đó là tìm kiếm nhị phân và đệ quy. Trong bài viết, mình hay dùng cụm từ độ phức tạp của giải thuật này, độ phức tạp của giải thuật kia…, vậy O(n), O(logn) là gì và dựa vào đâu mà mình có thể khẳng định độ phức tạp của giải thuật này là O(n), độ phức tạp của giải thuật kia là O(logn)… Thì bài viết hôm nay mình sẽ giới thiệu về Big O và một vài nguyên tắc của Big O để đánh giá mức độ hiệu quả hay kém hiệu quả của một giải thuật.

Giới thiệu

Giải thuật đơn giản chỉ là cách để giải quyết vấn đề nào đó trong lập trình, việc đánh giá giải thuật chính là lựa chọn cách viết code (implement) sao cho hiệu quả nhất. Trong thực tế khi giải quyết vấn đề nào đó chúng ta cũng thường phân tích ưu nhược điểm các cách giải quyết để lựa chọn cách giải quyết có lợi hơn.

Ví dụ, khi mình cần di chuyển từ TP HCM về Bình Định, thông thường mình sẽ có 2 sự lựa chọn. Thứ nhất là đi bằng máy bay và thứ hai là đi bằng xe khách. Đi bằng máy bay có ưu điểm là sẽ nhanh nhưng nhược điểm là chi phí cao, và ngược lại đi bằng xe khách tuy chậm nhưng chi phí lại rẻ. Vậy thì mình đã dựa vào chi phí và thời gian để đánh giá là cách di chuyển nào là hiệu quả hơn. Do đó tùy vào trường hợp mình cần tiết kiệm khoản nào thì mà sử dụng phương tiện di chuyển cho hợp lý.

Tương tự trong lập trình, để giải quyết vấn đề nào đó thì chúng ta cũng cần sử dụng các phép tính toán hay còn gọi là độ phức tạp thời gian bởi và vùng nhớ để lưu trữ hay còn gọi là độ phức tạp không gian. Để đánh giá giải thuật này là hiệu quả hơn giải thuật khác ta cần phải đánh giá dựa trên cùng một tập dữ liệu và với kích thước dữ liệu là lớn (vì với tập dữ liệu nhỏ thì sẽ rất khó để đánh giá, vì tốc độ xử lý của máy tính là rất lớn). Tất nhiên cũng giống như trong ví dụ trên của mình, chúng ta cần tùy vào trường hợp để lựa chọn giải thuật phù hợp.

Phạm vi của bài viết này mình chỉ tổng hợp lại một vài thuật ngữ và quy tắc để đánh giá độ phức tạp về thời gian.

BigO

BigO là chỉ số để đánh giá độ phức tạp của một giải thuật được sử dụng phổ biến nhất trong lập trình (ngoài ra còn có Big Ô-mê-ga và Big Thê-ta).

BigO đánh giá dựa vào thời gian chạy lớn nhất của một giải thuật trên các dữ liệu cùng cỡ.

Ví dụ: Giải thuật tìm kiếm tuyến tính trong trường hợp tốt nhất chỉ cần thực hiện 1 phép tính, trường hợp xấu nhất là n phép tính và trường hợp trung bình là n/2 phép tính (với n là số lượng phần tử). Thì với BigO, độ phức tạp của giải thuật tìm kiếm tuyến tính là O(n).

Một số chỉ số độ phức tạp phổ biến theo mức độ tăng dần.
– Constant time: O(1) số phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. vd: a + b
– Logarithmic time: O(logn) số phép tính (thời gian thực hiện) tăng theo kích thước dữ liệu theo hàm logarit. vd: tìm kiếm nhị phân
– Linear time: O(n) số phép tính phụ thuộc vào dữ liệu đầu vào theo 1 biến. vd: tìm kiếm tuyến tính
– Log-linear time: O(nlogn) tổng hợp của n và logn (lồng nhau). vd: Heap sort, Merge sort
– Polynimial time: O(n^c) các vòng lặp lồng nhau
– Exponential time: O(c^n)  bài toán tìm số fibonacci thứ n
– Factorial time: O(n!)  bài toán TSP

Biểu đồ thời gian với số lượng phần tử với các độ phức tạp

Đánh giá độ phức tạp

– Quy tắc hằng: O(k*f(n) = O(f(n)) đơn giản là ta bỏ hằng số đi. vd: O(100n) = O(n)
– Quy tắc cộng: O(f(n) + O(g(n)) = max(f(n),g(n), ta lấy độ phức tạp lớn hơn. vd: O(n^2 + n) = O(n^2)
– Quy tắc nhân: O(f(n) * O(g(n)) = O(f(n)) * O(g(n)) ta lấy tích. vd: O(n) * O(logn) = O(nlogn)

Bài tập:

int count = 0;
        for (int i = N; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                count += 1;
            }
        }

Các bạn hãy dựa vào nguyên tắc trên để đánh giá độ phức tạp của đoạn code trên nhé. Have fun!

Sử dụng Memcached với Memcached Java Client

Chào mừng các bạn đã đến với thachleblog, ở bài trước, mình đã giới thiệu sơ lược về Memcached đồng thời hướng dẫn cách cài đặt cùng 1 vài thao tác cơ bản với memcached trên terminal. Ở bài này, mình sẽ viết một demo đơn giản để các bạn làm quen với Java memcached Client. Nào chúng ta cùng bắt đầu nhé.

Giới thiệu

Các bạn có bao giờ gặp tính năng giới hạn truy cập khi thao tác quá nhanh trên một ứng dụng, hoặc nhận thông báo bạn đã truy cập quá số lần cho phép? Để làm tính năng giới hạn truy cập này thì có nhiều cách, chúng ta có thể lưu số lần truy cập của user vào database hoặc thậm chí là 1 biến static… Và một trong số các cách đó là sử dụng cache, và ở đây là mình dùng memcached.

Có vài lý do để chúng ta chọn memcached cho tính năng này đó là truy cập trên memecached sẽ nhanh hơn so với sử dụng database đồng thời memcached hỗ trợ các tính năng như là tự động expired sau một khoảng thời gian (tự động mở lại cho user truy cập), tăng giá trị cho value…

Thêm một lý do khác để chọn memcached thay vì các loại cache local là vì đối với ứng dụng được deploy trên nhiều instance, sử dụng cache local chúng ta sẽ phải handle thêm các bước đồng bộ dữ liệu cache trên các intance. Làm mệt mà dễ có bug, hehe. Đối với memcached thì ta đã giải quyết xong phần đồng bộ dữ liệu cache giữa nhiều instance của ứng dụng.

Bắt đầu

Để kết nối memcached bằng Java chúng ta có thể sử dụng các libs spymemcached, xmemcached hoặc gwhalin memcached client… Ở demo này, mình sẽ sử dụng spymemcached.

Việc đầu tiên là tải về spymemcached. Và tất nhiên là đã có memcached. Đầu tiên, mình cần init connect tới memcached (tương tự như database vậy). Với spymemcached chúng ta có thể thao tác như sau:

  1. MemcachedClient memcachedClient = MemcachedClient(new InetSocketAddress(HOST, PORT));

Ở đây, mình thiết lập cho thời gian expire cache là 60s. Mình cần giới hạn user chỉ được phép truy cập tính năng này tối đa là 5 lần 1 phút. Do đó, mỗi lần user truy cập, mình sẽ kiểm tra thông tin username (thông tin duy nhất để phân biệt user, nên là uid) trong cache.

Nếu là lần đầu tiên thì sẽ cho phép truy cập, đồng thời ghi vào cache với thông tinh key – value là username – 1. Tương tự các lần tiếp theo mình sẽ cho phép truy cập và tăng số lần truy cập lên. Cuối cùng, nếu user đó truy cập quá số lần cho phép trong 60s thì sẽ bị chặn. Sau thời gian 60s, dữ liệu sẽ bị expire và user sẽ có truy cập như lúc đầu.

Code demo:

package memcached;
 
import java.io.IOException;
import java.net.InetSocketAddress;
import net.spy.memcached.MemcachedClient;
 
/**
 *
 * @author thachlp
 */
public class UserLimitAccess {
 
    private static final int LIMIT_PER_MINUTE = 5;
    private static final int TIME_EXPIRED = 60;
    private static final String HOST = "127.0.0.1";
    private static final int PORT = 11211;
 
    private static MemcachedClient memcachedClient;
 
    public static void initMemcached() {
        try {
            memcachedClient = new MemcachedClient(new InetSocketAddress(HOST, PORT));
            System.out.println("Connection to server sucessful.");
        } catch (IOException ex) {
            System.out.println("Can not connect to memcache server: " + ex.getMessage());
        }
    }
 
    public static boolean isLimitedAccess(String userName) {
        Object accessCount = memcachedClient.get(userName);
        // the fist time user login
        if (accessCount == null) {
            memcachedClient.add(userName, TIME_EXPIRED, "1");
            return true;
        }
 
        int numberAccess = Integer.parseInt((String)accessCount);
        // user access over the limit access
        if (numberAccess > LIMIT_PER_MINUTE) {
            return false;
        } else {
            memcachedClient.incr(userName, 1);
            return true;
        }
    }
 
    public static void main(String[] args) {
        initMemcached();
        // can access
        if (isLimitedAccess("thachle")) {
            System.out.println("Welcome to thachle blog");
        } else {
            System.out.println("You have accessed over limit per minute, please get back after 1 minute");
 
        }
        System.exit(0);
    }
 
}

Đây chỉ là phần code demo cách sử dụng memcached client để kết nối với memcaced. Các bạn có thể tham khảo. Mình đã test lần đầu= và thấy ok ^.^.

Kết

Vừa rồi là phần demo của mình về cách sử dụng memcached với Java. Quá đơn giản phải không. Tất nhiên trong các ứng dụng thực tế chúng ta cần thêm các config về pool… để tăng tốc độ cho memecached.

Mọi góp ý về cách trình bày, code hoặc bất cứ thứ gì có thể comment bên dưới, mình sẽ theo dõi nhé. Cảm ơn các bạn đã đọc và hẹn gặp lại các bạn ở các bài viết sau.