Tìm kiếm nhị phân | Binary search

Chào mừng các bạn đã đến với thachleblog, bài viết hôm nay mình sẽ trình bày về một thuật toán tìm kiếm đơn giản nhưng lại cực kỳ hiệu quả, được ứng dụng rất nhiều trong thực tế đó là tìm kiếm nhị phân hay còn gọi là binary search. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Nói về bài toán tìm kiếm, chúng ta gặp rất nhiều trong thực tế đó là khi chúng ta tìm tên mình danh sách đăng ký vận động viên marathon, tìm tên mình trong danh sách nhân viên xuất sắc của năm được dán ở đâu đó. Thời đại này cần tìm kiếm thì nhấn nút thôi chứ lấy ví dụ về tìm kiếm bằng mắt khó quá, hehe.

Cách đơn giản nhất là chúng ta sẽ dò tuần tự (đối với các danh sách ngắn), cho đến khi tìm đúng đến tên mình. Hoặc cũng có cách nhanh hơn là vì các danh sách thường sắp xếp theo tên, do đó, mình chỉ việc dò tên mình trong phạm vi bản chữ cái tên mình. Ví dụ, tên mình bắt đầu bằng chữ cái T, do đó mình chỉ việc tìm tên trong phạm vi chữ T. Tùy vào vị trí mình chọn mà mình sẽ dò tên mình theo hướng tiến hoặc lùi.

Trong lập trình, để tìm kiếm một phần tử trong mảng, danh sách. Cách tìm kiếm đơn giản nhất là tìm kiếm tuần tự, hay còn gọi là tìm kiếm lân cận (linear search). Ý tưởng rất đơn giản, ta chỉ việc kiểm tra lần lượt các phần tử từ đầu đến cuối để tìm phần tử thỏa điều kiện.

Ví dụ: Cho mảng gồm 16 số nguyên tố tăng dần: 2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47

Để tìm vị trí số 13 trong mảng, ta cứ việc kiểm tra lần lượt phần tử đầu tiên là 2, cho đến hết mảng và trả về vị trí của số 13.

Trường hợp tổng quát, nếu may mắn, số ở vị trí đầu tiên là số cần tìm thì ta chỉ cần 1 lần kiểm tra. Tuy nhiên, nếu số cần tìm ở vị trí cuối cùng hoặc không có trong mảng, ta sẽ phải thực hiện kiểm tra đến 16 lần.

Vì là mảng các số nguyên tăng dần nên trong trường hợp này ta có thể dùng thuật toán tìm nhị phân . Cách thực hiện rất đơn giản, đầu tiên ta kiểm tra số chính giữa mảng có phải là số cần tìm hay không, nếu không ta có thể loại bỏ 1/2 số phần tử và tiếp tục tìm kiếm trong 1/2 còn lại. Cứ mỗi lần chọn phần tử để so sánh, ta sẽ loại bỏ được 1/2 số phần tử không phù hợp. Ở ví dụ trên, việc tìm kiếm nhị phân sẽ được thực hiện như sau:

– Đầu tiên chọn phần tử để kiểm tra ở giữa mảng là 19, vì số cần tìm là 13 nhỏ hơn 19 nên ta loại bỏ được 1/2 phần tử từ 19 – 47 và chỉ cần tìm trong phạm vi từ 2 – 17.

– Lần tiếp theo tương tự ta chọn số 7, vì 7 nhỏ hơn 13 nên ta cũng loại bỏ được 1/2 số phần tử và tiếp tục tìm trong phạm vi từ 11 – 17.

– Lần cuối cùng ta chọn 13 để so sánh, lần này ta trả về kết quả cần tìm.

Trong cách tìm kiếm nhị phân, rõ ràng, số lần chúng ta kiểm tra sẽ ít hơn rất nhiều so với tìm kiếm tuần tự, trong trường hợp trên, trường hợp xấu nhất ta cũng mất tối đa là 5 lần để kiểm tra.

Đặc biệt, vì mỗi lần chọn số cần tìm là lại loại bỏ được 1/2 phần tử, nên khi số lượng phần tử cần tìm tăng lên gấp đôi, ta chỉ mất thêm 1 lần để kiểm tra. Số lần cần kiếm tra trong thuật toán tìm kiếm nhị phân sẽ là logarit cơ số 2 của n. Để xem mức độ hiệu quả của thuật toán tìm kiếm nhị phân, ta có thể xem bảng logn:

Thử tưởng tượng, nếu bạn cần tìm user theo id, trong danh sách (list) user được sắp xếp id tăng dần lên đến xấp xỉ 1000 phần tử, chúng ta chỉ mất tối đa 11 lần so sánh để tìm ra kết quả. Một sự cải thiện đáng kinh ngạc so với 1000 lần kiếm tra (trường hợp xấu nhất) theo thuật toán tìm kiếm tuần tự!

Giải thuật

Giải thuật của tìm kiếm nhị phân rất đơn giản, như phần ví dụ ở trên, mình chỉ cần thực hiện bằng các bước.

1. Chọn min là 0 và max = n -1 (n là số phần tử của mảng)

2. Nếu max nhỏ hơn min, số cần tìm không tồn tại, trả về -1

3. Chọn mid là số chính giữa mảng

4. Nếu mid là số cần tìm (target), ta trả về giá trị cần tìm

5.  Nếu mid < target, ta set lại min = mid + 1

6. Nếu mid > target, ta set lại max = mid – 1;

7. Lập tại bước 2

Code

Có nhiều cách để implement tìm kiếm nhị phân, nhưng thường thì mình dùng vòng lặp while

package binarysearch;
 
/**
 *
 * @author thachlp
 */
public class BinarySearch {
 
    private static int binarySearch(int arr[], int target) {
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
 
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
 
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47};
        System.out.println("Found 13 at index: " + binarySearch(arr, 13));
    }
 
}

Đoạn code trên là ví dụ minh họa với các phần tử là số nguyên, nhưng chúng ta cũng có thể vận dụng cho các trường hợp các giá trị của phần tử là chữ cái, số… miễn là chúng được sắp xếp tăng dần. (Chúng ta cũng có thể tối ưu danh sách trước khi tìm kiếm bằng cách sort object, xem thêm tại đây)

Kết

Qua bài viết của mình, hy vọng các bạn đã cảm thấy được sự hiệu quả của thuật toán tìm kiếm nhị phân, qua đó có thể tự tin vận dụng vào dự án của mình đạt hiệu quả cao nhất. Các bài sau, mình sẽ tiếp tục giới thiệu đến các giải thuật khác. Cảm ơn các bạn đã đọc và hẹn gặp lại.

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.