Thuật toán lùa bò vào chuồng(Đếm phân phối)

Làm cách nào từ một coder chân chính  trở thành một người chăn bò 😃😃

Chắc hẳn trong lập trình chúng ta không khó để gặp gỡ các bài toán đếm.Tuy nhiên việc thực hiện các bài toán đếm thường được diễn ra trên dữ liệu lớn, nếu các bạn không biết cách tổ chức dữ liệu và thực hiện  thuật toán hiệu quả thường sẽ dẫn đến kết quả sai lầm. Vì vậy trong bài viết hôm nay chúng ta sẽ cùng tìm hiểu qua một trong những cách tiếp cận bài toán đếm đó là thuật toán lùa bò vào chuồng hay còn gọi là đếm phân phối.

1. Đặt vấn đề:

Ban đầu bạn có một mảng số gồm N phần tử ( N <10^5) mỗi giá trị trong mảng đều bé hơn hoặc bằng 100. Bạn được giao nhiệm vụ đếm xem trong mảng số đó có bao nhiêu phần tử riêng biệt.

    VD: N=10

    arr []  =   1 6 9 1  7 9 9 9 2 3

=> 6 phần tử riêng biệt.

2.Thuật toán lùa bò vào chuồng: 

•  Tư tưởng của thuật toán: giả sử bạn là một người nông dân sở hữu một nông trại bò và bạn cần phải đếm chính xác số lượng những chú bò trong trang trại để dễ quản lý. Vi những chú bò rất tinh nghịch nên bạn cần phải lùa những chú bò này vào chuồng của mình để dễ dàng cho việc đếm, bò kobe sẽ được lùa vào chuồng bò kobe, bò sữa sẽ được lùa vào chuồng bò sữa... sau khi hoàn tất việc còn lại bạn chỉ cần đếm số lương của mỗi chuồng. Bạn sẽ biết được chính xác mỗi loại có bao nhiêu con và tổng số lượng bò.
• Trên cơ sở đó ta có thể áp dụng thuật toán để giải quyết vấn đề trên.

    int n=10, max_val=-1, ans=0;

    int arr[]={1,6,9,1,7,9,9,9,2,3};

    for(int i=0; i<n; i++) {

        if(arr[i]>max_val)

            max_val =arr[i];

    }

    int cnt[max_val+1]={0};

    for(int i=0; i<n; i++) {

        cnt[arr[i]]++;

    }

    for(int i=0; i<max_val+1; i++) {

        if(cnt[i]!=0)

            ans++;

    }

    cout<<"So loai bo khac nhau la: "<<ans<<'\n';

• Hãy tưởng tượng mỗi giá trị trong mảng là một loại bò. Bò loại 1, bò loại 7, bò loại 9... bây giờ chúng ta sẽ xây dựng chuồng bò là một mảng cnt với kích thước của mảng sẽ bằng giá trị lớn nhất trong mảng array +1.
• Mỗi index trong mảng cnt sẽ  đại diện cho chuồng của mỗi loại nên ta phải cấp phát mảng bằng chú bò có giá trị lớn nhất và cộng thêm 1 vì index của mảng bắt đầu từ 0. Ban đầu chuồn trống nên ta gán các phần tử đều bằng không.
• Bây giờ ta chỉ việc lùa các chú bò vào chuồng bằng cách duyệt các phần tử của mảng arr  và tăng kích thước của chuồng đó lên một. Sau cùng để kiểm tra số lượng loại bò ta chỉ cần duyệt qua chuồng bò cnt và tăng đáp án lên 1 nếu chuồng đó không trống.
• Điểm mạnh: Thuật toán được cài đặt một cách dễ dàng và dễ quản lý. Qua đó bạn cũng có thể trả lời các truy vấn như số lượng của các số riêng biệt. VD: số lượng số 1 là
• cout<<cnt[1];
• Điểm yếu: Ta có thể thấy nếu giá trị trong mảng arr quá lớn  thì ta không thể tạo mảng cnt để lưu trữ bên cạnh đó độ phức tạp thuật toán trên là O(n+k) với n là độ dài phần tử arr và k là giá trị lớn nhất trong mảng arr. nếu k nhỏ ta có thể suy độ phức tạp là O(n) và có thể giải bài toán trong 1s Nhưng nếu k đạt tới giá trị n^2 thì độ phức tạp có thể đạt là O(n^2) nên ta cần phải cân nhắc khi bài toán giới hạn là 2s.
• Để cái tiến cách cài đặt trên ta có thể sử dụng thêm một số các cấu trúc dữ liệu như map( Bảng đồ băm) bây giờ với O(n^2) với k đạt tới n^2 ta có thể thu thành O(nlogn).

    int n=10, max_val=-1, ans=0;

    int arr[]={1,6,9,1,7,9,9,9,2,3};

    for(int i=0; i<n; i++) {

        if(arr[i]>max_val)

            max_val =arr[i];

    }

    map<int,int> cnt;

    for(int i=0; i<n; i++) {

        cnt[arr[i]]++;

    }

    for(auto x: cnt) {

        if(x.second!=0)

            ans++;

    }

    cout<<"So loai bo khac nhau la: "<<ans<<'\n';

3.Một số ứng dụng phổ biến:

• Counting sort:

void countSort(int arr[], int n)

{

    int output[n];

    int count[n + 1], i;

    memset(count, 0, sizeof(count));

 

    for (i = 0; arr[i]; ++i)

        ++count[arr[i]];

    for (i = 1; i <= n; ++i)

        count[i] += count[i - 1];

 

    for (i = 0; arr[i]; ++i) {

        output[count[arr[i]] - 1] = arr[i];

        --count[arr[i]];

    }

    for (i = 0; arr[i]; ++i)

        arr[i] = output[i]; }

}

• Radix sort:

void countSort(int arr[], int n, int exp)

{

    int output[n];

    int i, count[10] = { 0 };

 

    for (i = 0; i < n; i++)

        count[(arr[i] / exp) % 10]++;

 

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

 

    for (i = n - 1; i >= 0; i--) {

        output[count[(arr[i] / exp) % 10] - 1] = arr[i];

        count[(arr[i] / exp) % 10]--;

    }

 

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

 

void radixsort(int arr[], int n)

{

    int m =arr[0];    

    for (int i = 0; i<n; i++)

        m = max(m, arr[i]);

    for (int exp = 1; m / exp > 0; exp *= 10)

        countSort(arr, n, exp);

}