Thuật toán lính canh có thực sự tốt hơn tuần tự

#1

giả sử đề bài cho 1 mảng A, n phần tử, và 1 biến x, tìm vị trí của biến x trong mảng A

A[1,2,3,4,5,6,7,8,9,10…]
x

  1. nếu tìm kiếm tuần tự thì ta chỉ cần duyệt trực tiếp trên mảng A rồi tìm vị trí của x
  2. nếu tìm kiếm bằng lính canh ta phải tạo 1 mảng mới rồi đặt lính canh vào cuối mảng mới

về lí thuyết thì lính canh nhanh hơn 50% so với tuần tự, nhưng lính canh phải tạo 1 mảng mới rồi dùng vòng lặp để copy dữ liệu sang mảng mới, mình thấy vậy thì nó có tốt hơn tuần tự đâu nhỉ

trường hợp tuần tự xấu nhất khi x không có trong mảng: 2n+1+1
trường hợp lính canh xấu nhất khi x không có trong mảng: n+1+1
nhưng lính canh phải tạo mảng mới và thực hiện n phép gán >> 2n+1+1
nên tổng lại 2 cái như nhau mà lính canh còn tốn bộ nhớ hơn nữa

#2

Thêm 1 phần tử vào cuối thì cần gì phải copy lại đâu.

3 Likes
#3

sao ko anh, vd 1 mảng lúc khởi tạo thì chiều dài cố đinh, sau đó người ta lấp đầy mảng đó bằng các giá trị, thì thêm vào cuối kiểu gì mà ko copy sang mảng khác? em học java,C# thì thế hay bên c,c++ ảo diệu hơn :grinning:

#4

tìm từ 0 tới n-1 thì tốn có n so sánh làm sao lên tới 2n gì nhỉ :V

edit: à chắc đếm cả so sánh i < n gì à :V

vậy thì nếu mảng ban đầu cho phép thêm 1 phần tử vào cuối 1 cách hiệu quả O(1) thì lính canh tốt hơn. Ví dụ mảng động trong C++ có tối đa capacity phần tử, chứa size phần tử, nếu size == capacity thì sẽ move qua mảng mới có tối đa capacity = 2 * old capacity. Vậy nếu đọc vào ví dụ từ 5 tới 7 phần tử thì thật ra mảng có tối đa 8 phần tử, thêm 1 lính canh vào cuối thành 6-8 phần tử thì chỉ tốn O(1) vì mảng ban đầu chứa được tối đa 8 phần tử. Nếu đọc vào 8 phần tử thì khi thêm lính canh vào phải chuyển sang mảng mới có tối đa 16 phần tử để chứa 9 phần tử thì khi này mới mất O(n) :V

5 Likes
#5

nếu là 1 mảng bị lấp đầy phần tử thì dùng lính canh, tốc độ thua tuần tự?

#6

nếu tìm thấy phần tử trong mảng thì về lý thuyết là thua tuần tự (n+n/k > n/k+n/k), còn ko tìm thấy thì về lý thuyết là ngang ngửa tuần tự. Còn muốn chắc ăn thì viết code so tốc độ thôi :V

hình như ko thấy ai xài lính canh để tìm 1 phần tử trong mảng cả :V

4 Likes
#7

Lính canh phù hợp với mảng (effectively) không co giãn trong runtime, như bài mã đi tuần hay loang (đều là 2D).

3 Likes
#8

Đầu tiên thì lính canh là một kỹ thuật chứ không phải là thuật toán.

Hai là, kỹ thuật này áp dụng khi ta có quyền điều khiển data để có thể đặt lính canh như ý mình trên data đó.

Ba là, tác dụng chủ yếu của đặt lính canh là để giảm bớt việc phải xét biên của dữ liệu => với các vòng lặp phức tạp, việc tính toán nhiều thì thêm/bớt một vài thao tác xét biên có tác dụng không nhiều lắm (\lim_{n \to \infty} {n \over {n+k}} = 1). Nên việc phải duplicate data chỉ để thêm lính canh thì cần phải suy nghĩ thật kỹ (a.k.a cần benchmark).

Cuối cùng, lấy ví dụ như bài toán tìm kiếm như trên, nếu dùng tìm tuần tự:

auto find_in(int* a, int n, int v){
    for(int i=0; i<n; i++)
        if (a[i]==v) return i;
    return -1;
}

auto find(){
    int n, v;
    std::cin >> n >> v;
    auto a = std::make_unique<int[]>(n);
    for (int i=0; i<n; ++i) std::cin >> a[i];
    return find_in(a.get(), n, v);
}

Nếu dùng kỹ thuật lính canh:

auto find_until_found(int* a, int v){
    int i=0;
    while(a[i]!=v) ++i;
    return i;
}

auto find(){
    int n, v;
    std::cin >> n >> v;
    auto a = std::make_unique<int[]>(n+1);
    for (int i=0; i<n; ++i) std::cin >> a[i];
    a[n]=v; // Đặt lính canh
    auto i = find_until_found(a.get(), v); // Tìm bằng lính canh a[n] bên trên
    if (i==n) return -1;
    return i;
}

Và đây là so sánh độ hiệu quả 2 cách trên: https://gcc.godbolt.org/z/8dMnavTTv

5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?