Hướng dẫn về thuật toán cửa sổ trượt và cách triển khai nó trong Go

Thực hiện các thao tác trên chuỗi số và ký tự là một khía cạnh quan trọng của lập trình. Thuật toán cửa sổ trượt là một trong những thuật toán tiêu chuẩn để thực hiện việc đó.

Thuật toán này sở hữu tính chất đặc biệt và dễ thích ứng, có khả năng áp dụng trên nhiều lĩnh vực khác nhau như xử lý chuỗi, điều hướng mảng và nâng cao hiệu quả. Tiện ích của nó vượt ra ngoài các thao tác đơn thuần hoặc các hoạt động truyền tải; đúng hơn, nó phục vụ như một nguồn tài nguyên quý giá để tối ưu hóa hiệu suất hệ thống trong nhiều bối cảnh khác nhau.

Thuật toán cửa sổ trượt hoạt động theo cách nào và người ta có thể thực thi nó bằng ngôn ngữ lập trình Go như thế nào?

Tìm hiểu thuật toán cửa sổ trượt

Là một nhà phát triển phần mềm có kinh nghiệm, điều cần thiết là phải làm quen với các thuật toán nổi bật khác nhau để giải quyết các thách thức lập trình một cách hiệu quả. Trong số các thuật toán này, kỹ thuật cửa sổ trượt nổi bật nhờ khả năng xử lý và kiểm tra hiệu quả các tập hợp con dữ liệu bằng cách quản lý động một cửa sổ trên một loạt thông tin.

Thuật toán này có thể áp dụng cho một loạt các thách thức tính toán liên quan đến cấu trúc dữ liệu dựa trên mảng, dựa trên chuỗi và tuần tự.

Khái niệm cơ bản của cách tiếp cận cửa sổ trượt bao gồm việc thiết lập một cửa sổ có kích thước được xác định trước hoặc có thể điều chỉnh được, sau đó được xử lý thông qua dữ liệu đầu vào. Bằng cách đó, phương pháp này cho phép kiểm tra các tập hợp con khác nhau của đầu vào mà không cần lặp lại các phép tính không cần thiết, từ đó tối ưu hóa hiệu quả.

Hình minh họa được cung cấp hiển thị mô tả đồ họa về hoạt động của nó:

Các tham số của cửa sổ có thể được điều chỉnh dựa trên các yêu cầu cụ thể do vấn đề hiện tại đặt ra.

Triển khai thuật toán cửa sổ trượt trong Go

Một cách tiếp cận để hiểu được thuật toán cửa sổ trượt là sử dụng thử thách lập trình chung, chẳng hạn như xác định tổng tối đa của tập hợp con liền kề của các phần tử trong một mảng xác định, trong đó độ dài của mảng con được xác định trước.

Mục tiêu của ví dụ minh họa này là xác định một tập hợp con liền kề có độ dài “k” trong một mảng đầu vào, sao cho tổng các phần tử của nó đạt giá trị cao nhất có thể. Thuật toán được cung cấp lấy đầu vào là cả mảng đã cho và số nguyên không âm chỉ định độ dài chuỗi con mong muốn.

Hãy xem xét một mảng số được chỉ định là “nums”. Như được mô tả trong đoạn mã tiếp theo, chúng ta có cách sắp xếp các giá trị sau:

 nums := []int{1, 5, 4, 8, 7, 1, 9}

Hãy xem xét một mảng chính có kích thước n x m, trong đó n đại diện cho số hàng và m biểu thị số cột. Chúng ta hãy xem xét thêm một tập hợp con của mảng này, được gọi là mảng con, trải dài trên k hàng và có giá trị là 3 cho thứ nguyên cột của nó (tức là k cột).

 k := 3

Người ta có thể định nghĩa một hàm tìm cách xác định tổng lớn nhất có thể thu được bằng cách kết hợp các mảng con, trong đó mỗi mảng con có độ dài k:

 func maximumSubarraySum(nums []int, k int) int {
    // body
}

Mặc dù việc lưu trữ bản sao của các phần tử đích trong một cửa sổ như một giải pháp thay thế là khả thi nhưng phương pháp này thể hiện hiệu suất dưới mức tối ưu.

Thay vào đó, người ta chỉ cần phác họa các tham số của cửa sổ cho mục đích giám sát. Thật vậy, trong kịch bản này, cửa sổ ban đầu sẽ có chỉ số bắt đầu là 0 và chỉ số kết thúc là k-1. Trong quá trình dịch chuyển cửa sổ, các thông số ranh giới này sẽ được cập nhật tương ứng.

Để giải quyết vấn đề này, cần phải tính tổng độ dài đoạn ban đầu ‘k’. Để đạt được mục đích đó, bạn nên kết hợp các dòng sau trong hàm của mình:

 var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0

for i := 0; i < k; i\+\+ {
    windowSum \+= nums[i]
}

maxSum = windowSum

Đoạn mã nói trên thiết lập các biến cần thiết cho thuật toán, tính tổng của cửa sổ ban đầu trong mảng và đặt tổng tối đa thành tổng thu được từ cửa sổ chính. Sau đó, nó khởi tạo biến maxSum với giá trị được xác định cho sự tích lũy của cửa sổ đang mở.

Giai đoạn tiếp theo liên quan đến việc duyệt qua mảng nums , bắt đầu từ chỉ mục k và di chuyển dần dần “cửa sổ” về phía trước theo một loạt các bước. Ở mỗi giai đoạn của quá trình này, “cửa sổ” được dịch chuyển tăng dần cho đến khi đến cuối mảng.

Để cập nhật biến windowSum, chúng tôi sẽ thêm phần tử hiện tại vào đó đồng thời trừ đi phần tử có trong windowSum ở đầu lần lặp hiện tại, được biểu thị bằng chỉ mục windowStart. Điều này cho phép chúng tôi duy trì tổng hoạt động khi các phần tử mới được thêm vào mảng.

Thuật toán cập nhật tổng giá trị tối đa trong một cửa sổ được chỉ định dựa trên việc liệu tổng mới được tính có vượt quá mức tối đa hiện tại đã được lưu trữ trước đó hay không.

Mã được cung cấp bao gồm kỹ thuật cửa sổ trượt, có thể được kết hợp trong hàm maxSubarraySum như một tính năng bổ sung.

 for windowEnd = k; windowEnd < len(nums); windowEnd\+\+ {
    windowSum = windowSum \+ nums[windowEnd] - nums[windowStart]

    if windowSum > maxSum {
        maxSum = windowSum
    }

    // slide window forward
    windowStart\+\+
}

Sau khi kết thúc vòng lặp, tổng giá trị cao nhất sẽ được lưu trữ trong maxSum , giá trị này có thể được trả về dưới dạng đầu ra của hàm.

 return maxSum

Chức năng hoàn chỉnh của bạn sẽ trông như thế này:

 func maximumSubarraySum(nums []int, k int) int {
    var windowStart, windowEnd, maxSum, windowSum int
    windowStart = 0

    for i := 0; i < k; i\+\+ {
        windowSum \+= nums[i]
    }

    maxSum = windowSum

    for windowEnd = k; windowEnd < len(nums); windowEnd\+\+ {
        windowSum = windowSum \+ nums[windowEnd] - nums[windowStart]

        if windowSum > maxSum {
            maxSum = windowSum
        }

        // slide window forward
        windowStart\+\+
     }

    return maxSum
}

Để đánh giá hiệu suất thuật toán của chúng tôi, chúng tôi có thể tạo một hàm chính sử dụng các giá trị số được thiết lập trước đó cho nums và k. Điều này sẽ cho phép chúng tôi đánh giá mức độ hiệu quả của thuật toán trong các tình huống khác nhau bằng cách nhập các bộ số và giá trị khác nhau cho số lượng số nguyên riêng biệt được yêu cầu.

 func main() {
    nums := []int{1, 5, 4, 8, 7, 1, 9}
    k := 3
    fmt.Println(maximumSubarraySum(nums, k))
}

Trong trường hợp này, kết quả sẽ lên tới 19, tương ứng với tổng của mảng con bao gồm các phần tử 4, 8 và 7, tức là giá trị lớn nhất trong số tất cả các chuỗi con như vậy trong mảng đã cho.

Người ta có thể sử dụng một cách tiếp cận có thể so sánh được để giải quyết các mô hình lặp lại trong các bối cảnh và lĩnh vực ngôn ngữ khác nhau, chẳng hạn như quản lý các phần tử lặp trong phạm vi được chỉ định bằng cách sử dụng một

Thuật toán tối ưu mang lại hiệu quả cho ứng dụng

Tính hiệu quả của thuật toán này minh họa tầm quan trọng của việc thực hiện các chiến lược tối ưu trong việc giải quyết các thách thức. Bằng cách sử dụng kỹ thuật cửa sổ trượt, nó đạt được năng suất tối đa đồng thời giảm thiểu các hoạt động quá mức.

Sự hiểu biết thành thạo về thuật toán cửa sổ trượt, cũng như việc thực thi nó trong ngữ cảnh của ngôn ngữ lập trình Go, chuẩn bị đầy đủ cho việc giải quyết những thách thức thực tế phát sinh trong quá trình phát triển các ứng dụng phần mềm.