Bài 18.4: Tối ưu hóa với Set trong C++

Chào mừng quay trở lại với chuỗi bài viết về C++! Hôm nay, chúng ta sẽ cùng nhau tìm hiểu một cấu trúc dữ liệu cực kỳ mạnh mẽ và hữu ích trong Thư viện Chuẩn C++ (STL) - đó chính là set. Mặc dù tiêu đề có nhắc đến "tối ưu hóa", hãy hiểu rằng chúng ta sẽ khám phá cách set được thiết kế để tối ưu cho các tác vụ cụ thể, đặc biệt là khi làm việc với các tập hợp chứa các phần tử duy nhất và cần được sắp xếp.

Trong nhiều bài toán thực tế, chúng ta cần lưu trữ một tập hợp các dữ liệu sao cho:

Mỗi phần tử chỉ xuất hiện một lần (tính duy nhất).
Các phần tử được giữ trong một thứ tự nhất định (thường là tăng dần theo mặc định).
Các thao tác như thêm, xóa, và tìm kiếm một phần tử phải diễn ra nhanh chóng.

Nếu phải tự cài đặt một cấu trúc dữ liệu đáp ứng tất cả những yêu cầu này, đó sẽ là một công việc khá phức tạp và dễ mắc lỗi. May mắn thay, set sinh ra để giải quyết chính xác những vấn đề này một cách hiệu quả và tin cậy.

`set` là gì?

set là một container liên kết (associative container) trong STL, lưu trữ một tập hợp các phần tử duy nhất theo một thứ tự cụ thể. Thứ tự này thường là tăng dần theo giá trị của các phần tử, sử dụng toán tử < mặc định của kiểu dữ liệu hoặc một hàm so sánh tùy chỉnh do người dùng cung cấp.

Điểm mấu chốt làm nên hiệu quả của set chính là cấu trúc dữ liệu nền tảng mà nó sử dụng. Hầu hết các triển khai set hiện đại dựa trên cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search tree), phổ biến nhất là cây Đỏ-Đen (Red-Black Tree). Cấu trúc này đảm bảo rằng các thao tác tìm kiếm, chèn, và xóa luôn có độ phức tạp là O(log n), trong đó n là số lượng phần tử trong set.

Tại sao lại là O(log n)? Bởi vì trong một cây nhị phân tự cân bằng, chiều cao của cây luôn được giữ ở mức logarit so với số nút. Khi bạn tìm kiếm, chèn hay xóa một phần tử, bạn chỉ cần đi xuống theo một nhánh của cây, và số bước đi tỷ lệ với chiều cao của cây. Điều này nhanh hơn đáng kể so với O(n) khi bạn phải duyệt tuần tự qua một danh sách hay vector không được sắp xếp.

Các Thao Tác Quan Trọng và Độ Phức Tạp

Hiệu quả của set thể hiện rõ nhất qua độ phức tạp thời gian của các thao tác cơ bản:

insert(value): Thêm một phần tử mới vào set. Nếu phần tử đã tồn tại, thao tác sẽ không làm gì cả (vì set chỉ chứa phần tử duy nhất). Độ phức tạp: O(log n).
erase(value): Xóa phần tử có giá trị value khỏi set. Độ phức tạp: O(log n).
find(value): Tìm kiếm phần tử có giá trị value. Trả về một iterator trỏ đến phần tử đó nếu tìm thấy, hoặc set.end() nếu không tìm thấy. Độ phức tạp: O(log n).
count(value): Đếm số lần xuất hiện của value. Vì set chỉ chứa phần tử duy nhất, kết quả chỉ có thể là 0 hoặc 1. Độ phức tạp: O(log n).
Iteration (duyệt qua các phần tử): Duyệt từ đầu đến cuối set sẽ trả về các phần tử theo thứ tự đã được sắp xếp. Độ phức tạp: O(n) để duyệt toàn bộ set.

Đây chính là "tối ưu hóa" mà chúng ta đang nói đến: đối với các tác vụ thêm, xóa, tìm kiếm trên một tập hợp lớn các phần tử duy nhất cần được sắp xếp, set cung cấp hiệu suất O(log n) ổn định và đáng tin cậy.

Khi Nào Sử Dụng `set` (Các Tình Huống Tối Ưu)?

Với các đặc điểm và hiệu suất O(log n) cho các thao tác cốt lõi, set trở thành một lựa chọn tối ưu trong nhiều trường hợp:

Quản lý Tập Hợp Duy Nhất: Khi bạn cần lưu trữ một bộ sưu tập mà không được phép có các phần tử trùng lặp. set tự động xử lý việc này ngay khi bạn sử dụng insert.
Dữ Liệu Cần Được Sắp Xếp Tự Động: Nếu bạn liên tục thêm/xóa phần tử và cần dữ liệu luôn được giữ ở trạng thái sắp xếp, set làm điều này tự động và hiệu quả sau mỗi thao tác chèn/xóa (chi phí O(log n) đã bao gồm việc duy trì thứ tự).
Kiểm Tra Sự Tồn Tại Nhanh Chóng: Khi bạn cần thường xuyên kiểm tra xem một phần tử có tồn tại trong tập hợp hay không. Thao tác find hoặc count với O(log n) là rất hiệu quả cho việc này trên các tập hợp lớn.
Loại Bỏ Phần Tử Trùng Lặp Từ Nguồn Khác: Bạn có thể dễ dàng lấy các phần tử duy nhất từ một vector, list, hoặc mảng bằng cách đơn giản là chèn tất cả các phần tử đó vào một set. Set sẽ tự động loại bỏ các bản sao.

Hãy xem xét một vài ví dụ để hiểu rõ hơn cách sử dụng và lý do set phù hợp cho những tình huống này.

Ví Dụ Minh Họa

Ví Dụ 1: Tạo Set và Thêm Phần Tử (Duy Nhất & Sắp Xếp)

Ví dụ này cho thấy set tự động xử lý các phần tử trùng lặp và giữ cho các phần tử được sắp xếp.

#include <iostream>
#include <set>
#include <string>

int main() {
    // Khai bao mot set chua cac chuoi
    set<string> uniqueWords;

    // Them cac phan tu vao set
    uniqueWords.insert("apple");
    uniqueWords.insert("banana");
    uniqueWords.insert("apple"); // Them lai "apple" - se bi bo qua
    uniqueWords.insert("cherry");
    uniqueWords.insert("banana"); // Them lai "banana" - se bi bo qua

    cout << "Set sau khi them cac phan tu:" << endl;
    // Duyet qua set - cac phan tu se theo thu tu abc
    for (const string& word : uniqueWords) {
        cout << word << endl;
    }

    cout << "\nKich thuoc cua set: " << uniqueWords.size() << endl; // Kich thuoc chi la 3

    return 0;
}

Giải thích: Chúng ta tạo một set chứa kiểu string. Khi chèn các chuỗi, set tự động kiểm tra xem chuỗi đó đã tồn tại chưa. Nếu rồi, thao tác insert sẽ không thêm gì cả. Kết quả là set chỉ chứa các chuỗi duy nhất ("apple", "banana", "cherry") và chúng được lưu trữ theo thứ tự alphabet.

Ví Dụ 2: Kiểm Tra Sự Tồn Tại Phần Tử Nhanh Chóng (`find`)

Khi cần kiểm tra nhanh một giá trị có nằm trong tập hợp hay không, set với thao tác find (hoặc count) là rất hiệu quả (O(log n)).

#include <iostream>
#include <set>

int main() {
    set<int> lottoNumbers;
    lottoNumbers.insert(15);
    lottoNumbers.insert(4);
    lottoNumbers.insert(23);
    lottoNumbers.insert(8);
    lottoNumbers.insert(42);
    lottoNumbers.insert(1);

    int yourNumber = 23;
    int winningNumber = 7;

    // Su dung find de kiem tra
    if (lottoNumbers.find(yourNumber) != lottoNumbers.end()) {
        cout << yourNumber << " co trong bo so may man!" << endl;
    } else {
        cout << yourNumber << " khong co trong bo so may man." << endl;
    }

    if (lottoNumbers.find(winningNumber) != lottoNumbers.end()) {
        cout << winningNumber << " co trong bo so may man!" << endl;
    } else {
         cout << winningNumber << " khong co trong bo so may man." << endl;
    }

    // Su dung count (cung O(log n) va tra ve 0 hoac 1 cho set)
     if (lottoNumbers.count(yourNumber) > 0) {
        cout << "(Dung count) " << yourNumber << " co trong bo so may man!" << endl;
    }

    return 0;
}

Giải thích: Chúng ta sử dụng lottoNumbers.find(yourNumber). Nếu giá trị yourNumber tồn tại trong set, find sẽ trả về một iterator trỏ đến phần tử đó; ngược lại, nó trả về lottoNumbers.end(). Việc so sánh iterator trả về với lottoNumbers.end() là cách phổ biến để kiểm tra sự tồn tại. Thao tác này có độ phức tạp O(log n), rất nhanh ngay cả với set có hàng triệu phần tử. Sử dụng count cũng là một cách tương đương và có cùng độ phức tạp.

Ví Dụ 3: Xóa Phần Tử Nhanh Chóng (`erase`)

Khi cần xóa một phần tử cụ thể khỏi tập hợp duy nhất và được sắp xếp, set cũng cung cấp hiệu suất O(log n).

#include <iostream>
#include <set>
#include <vector>
#include <algorithm> // For sort - used for comparison later

int main() {
    set<double> experimentData;
    experimentData.insert(1.23);
    experimentData.insert(4.56);
    experimentData.insert(7.89);
    experimentData.insert(3.14);
    experimentData.insert(4.56); // Duplicates ignored

    cout << "Du lieu ban dau trong set:";
    for (double val : experimentData) {
        cout << " " << val;
    }
    cout << endl;

    // Xoa phan tu co gia tri 4.56
    size_t num_erased = experimentData.erase(4.56);
    cout << "So luong phan tu 4.56 da xoa: " << num_erased << endl; // Output: 1

    cout << "Du lieu trong set sau khi xoa 4.56:";
    for (double val : experimentData) {
        cout << " " << val;
    }
    cout << endl;

     // Thu xoa mot phan tu khong ton tai
    num_erased = experimentData.erase(99.99);
    cout << "So luong phan tu 99.99 da xoa: " << num_erased << endl; // Output: 0

    return 0;
}

Giải thích: experimentData.erase(4.56) tìm kiếm phần tử có giá trị 4.56 và xóa nó. Vì set chỉ chứa phần tử duy nhất, phương thức erase(value) sẽ xóa tối đa một phần tử và trả về số lượng phần tử đã bị xóa (0 hoặc 1). Thao tác này cũng có hiệu suất O(log n).

Ví Dụ 4: Lấy Các Phần Tử Duy Nhất Từ Một Container Khác

Đây là một trường hợp sử dụng rất phổ biến nơi set tỏ ra vô cùng hiệu quả. Thay vì phải sắp xếp vector rồi dùng unique, bạn chỉ cần chèn tất cả vào một set.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm> // Chi de in vector goc

int main() {
    vector<int> rawData = {10, 5, 20, 5, 10, 30, 10, 20, 40, 5};

    cout << "Du lieu goc trong vector:";
    for (int val : rawData) {
        cout << " " << val;
    }
    cout << endl;

    // Tao mot set tu du lieu cua vector
    // Set se tu dong xu ly tinh duy nhat va sap xep
    set<int> uniqueSortedData;
    for (int value : rawData) {
        uniqueSortedData.insert(value);
    }

    cout << "Cac phan tu duy nhat (da sap xep) tu set:";
    // Duyet qua set - cac phan tu da duy nhat va sap xep tang dan
    for (int value : uniqueSortedData) {
        cout << " " << value;
    }
    cout << endl; // Output: 5 10 20 30 40

    return 0;
}

Giải thích: Chúng ta có một vector chứa các số bị lặp lại và không theo thứ tự. Bằng cách đơn giản là lặp qua vector và chèn từng phần tử vào set, chúng ta nhận được một tập hợp mới chỉ chứa các giá trị duy nhất từ vector ban đầu và chúng được sắp xếp theo thứ tự tăng dần. Đây là một cách ngắn gọn và hiệu quả để lọc dữ liệu duy nhất. So với việc sao chép, sắp xếp vector, rồi dùng unique, cách dùng set thường đơn giản hơn về mặt code và hiệu quả cho tác vụ này.

Khi Nào `set` Có Thể Không Phải Là Lựa Chọn Tối Ưu Nhất?

Mặc dù set rất mạnh mẽ cho các trường hợp nó được thiết kế, không phải lúc nào nó cũng là lựa chọn tối ưu nhất. Hãy xem xét một số hạn chế:

Không Hỗ Trợ Truy Cập Ngẫu Nhiên: Bạn không thể truy cập phần tử thứ k trong set bằng toán tử [] như với vector hoặc deque. Việc truy cập đòi hỏi duyệt từ đầu (hoặc dùng advance trên iterator), mất thời gian tỷ lệ với vị trí của phần tử hoặc số bước tiến/lùi iterator.
Chi Phí Chèn/Xóa Cao Hơn So Với Vector ở Cuối: Việc chèn hoặc xóa ở cuối một vector (với push_back, pop_back - miễn là không cần cấp phát lại bộ nhớ) có thể là O(1) trung bình. Trong khi đó, mọi thao tác chèn/xóa trong set luôn là O(log n). Nếu bạn chỉ cần thêm/xóa ở cuối và không cần tính duy nhất hay sắp xếp, vector hoặc deque có thể nhanh hơn.
Không Chứa Phần Tử Trùng Lặp: Theo định nghĩa, set không lưu trữ các phần tử trùng lặp. Nếu bạn cần lưu trữ cả các bản sao của một giá trị, bạn cần sử dụng multiset.
Chi Phí Bộ Nhớ: Cấu trúc cây (như cây Đỏ-Đen) thường có chi phí bộ nhớ lớn hơn so với vector do cần lưu trữ thêm các con trỏ và thông tin cấu trúc cho mỗi nút.

Comments

There are no comments at the moment.