Home-theater-designers
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 đó.
Video MUO trong ngày CUỘN ĐỂ TIẾP TỤC VỚI NỘI DUNG
Đó là một giải pháp tinh tế và linh hoạt đã được ứng dụng vào nhiều lĩnh vực. Từ thao tác chuỗi đến truyền tải mảng và tối ưu hóa hiệu suất, thuật toán này có thể đóng một vai trò nào đó.
Vậy thuật toán cửa sổ trượt hoạt động như thế nào và bạn có thể triển khai nó trong Go như thế nào?
Tìm hiểu thuật toán cửa sổ trượt
Có nhiều thuật toán hàng đầu những điều hữu ích cần biết với tư cách là một lập trình viên và cửa sổ trượt là một trong số đó. Thuật toán này xoay quanh một khái niệm đơn giản về việc duy trì một cửa sổ động trên một chuỗi dữ liệu để xử lý và phân tích các tập hợp con của dữ liệu đó một cách hiệu quả.
Bạn có thể áp dụng thuật toán khi giải các bài toán tính toán liên quan đến mảng, chuỗi hoặc chuỗi dữ liệu.
Ý tưởng cốt lõi đằng sau thuật toán cửa sổ trượt là xác định một cửa sổ có kích thước cố định hoặc thay đổi và di chuyển nó qua dữ liệu đầu vào. Điều này cho phép bạn khám phá các tập hợp con khác nhau của đầu vào mà không cần tính toán dư thừa có thể cản trở hiệu suất.
Đây là một minh họa trực quan về cách nó hoạt động:
Ranh giới của cửa sổ có thể điều chỉnh theo yêu cầu cụ thể của bài toán.
Triển khai thuật toán cửa sổ trượt trong Go
Bạn có thể sử dụng một bài toán mã hóa phổ biến để tìm hiểu cách hoạt động của thuật toán cửa sổ trượt: tìm tổng lớn nhất của một mảng con có độ dài cho trước.
Mục đích của bài toán mẫu này là tìm mảng con có kích thước k tổng các phần tử của nó có giá trị lớn nhất. Hàm giải có hai tham số: mảng đầu vào và một số nguyên dương biểu thị k .
Đặt mảng mẫu là con số , như đoạn mã dưới đây hiển thị:
nums := []int{1, 5, 4, 8, 7, 1, 9}
Và đặt độ dài mảng con là k , với giá trị là 3:
k := 3
Sau đó, bạn có thể khai báo một hàm để tìm tổng tối đa của các mảng con có độ dài k:
điều gì xảy ra nếu bạn nói 112 với siri
func maximumSubarraySum(nums []int, k int) int {
// body
}
Có thể bạn đang nghĩ cửa sổ phải là một mảng lưu trữ các bản sao của phần tử đích. Mặc dù đó là một tùy chọn nhưng nó hoạt động kém.
Thay vào đó, bạn chỉ cần xác định ranh giới của cửa sổ để theo dõi. Ví dụ: trong trường hợp này, cửa sổ đầu tiên sẽ có chỉ mục bắt đầu là 0 và chỉ số cuối của k-1 . Trong quá trình trượt cửa sổ, bạn sẽ cập nhật các ranh giới này.
Bước đầu tiên để giải quyết vấn đề này là lấy tổng của mảng con đầu tiên có kích thước k. Thêm mã sau vào chức năng của bạn:
máy tính bảng Android của tôi sẽ không bật
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
Đoạn mã trên khai báo các biến cần thiết cho thuật toán và tìm tổng của cửa sổ đầu tiên trong mảng. Sau đó nó khởi tạo số tiền tối đa với tổng của cửa sổ đầu tiên.
Bước tiếp theo là trượt cửa sổ bằng cách lặp qua con số mảng từ chỉ mục k đến cuối cùng. Trong mỗi bước trượt cửa sổ:
- Cập nhật cửa sổTổng hợp bằng cách thêm phần tử hiện tại và trừ phần tử tại cửa sổBắt đầu .
- Cập nhật số tiền tối đa nếu giá trị mới của cửa sổTổng hợp lớn hơn nó.
Đoạn mã sau thực hiện cửa sổ trượt. Thêm nó vào tối đaSubarraySum chức năng.
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
Khi vòng lặp hoàn tất, bạn sẽ có số tiền lớn nhất trong số tiền tối đa , mà bạn có thể trả về dưới dạng kết quả 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
}
Bạn có thể định nghĩa một hàm chính để kiểm tra thuật toán bằng cách sử dụng các giá trị của con số Và k từ sớm hơn:
func main() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
Đầu ra trong trường hợp này sẽ là 19 , là tổng của mảng con [4, 8, 7], lớn nhất.
Bây giờ bạn có thể áp dụng kỹ thuật tương tự cho các vấn đề tương tự, ngay cả trong các ngôn ngữ khác, như xử lý các phần tử lặp lại trong một cửa sổ bằng cách sử dụng một Bản đồ băm Java , Ví dụ.
Thuật toán tối ưu mang lại hiệu quả cho các ứng dụng
Thuật toán này là minh chứng cho sức mạnh của các giải pháp hiệu quả khi giải quyết vấn đề. Cửa sổ trượt tối đa hóa hiệu suất và loại bỏ các tính toán không cần thiết.
Sự hiểu biết vững chắc về thuật toán cửa sổ trượt và cách triển khai nó trong Go sẽ trang bị cho bạn khả năng giải quyết các tình huống trong thế giới thực khi xây dựng ứng dụng.