This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

Sliding window algorithm

The sliding window algorithm can transform the nested cycle problem into a single cycle problem and reduce the time complexity.

For example, given the following array:

[5, 7, 1, 4, 3, 6, 2, 9, 2]Copy the code

What is the largest sum of five consecutive elements?

[5, 7, 1, 4, 3] is the first group of five consecutive elements and the sum is 20. [7, 1, 4, 3, 6] is the second group of five consecutive elements and the sum is 21…… In this way, the maximum sum of the five consecutive elements is 24, which is composed of [4, 3, 6, 2, 9].

Simple and crude two-layer for loop algorithm implementation:

const getMaxSumOfFiveContiguousElements = (arr) => {
  let maxSum = -Infinity;
  let currSum;

  for (let i = 0; i <= arr.length - 5; i++) {
    currSum = 0;

    for (let j = i; j < i + 5; j++) {
      currSum += arr[j];
    }

    maxSum = Math.max(maxSum, currSum);
  }

  return maxSum;
};
Copy the code

The time complexity is O(n*k), and the traversal is as shown in the figure:

With the sliding window algorithm, we can reduce the time complexity toO(n);

We put 5 consecutive elements into a window, after each sum calculation, subtract the first number in the window, and then add the first number outside the window to form a new window, the length of the window remains the same, and so on, until the window traverses all the elements, the traversal is finished;

The algorithm is as follows:

const getLargestSumOfFiveConsecutiveElements = (arr) => {
  let currSum = getSum(arr, 0, 4);
  let largestSum = currSum;

  for (let i = 1; i <= arr.length - 5; i++) {
    currSum -= arr[i - 1]; // subtract element to the left of curr window
    currSum += arr[i + 4]; // add last element in curr window
    largestSum = Math.max(largestSum, currSum);
  }

  return largestSum;
};

const getSum = (arr, start, end) => {
  let sum = 0;

  for (let i = start; i <= end; i++) {
    sum += arr[i];
  }

  return sum;
};
Copy the code

Traversal diagram:

Through + 1-1 traversal, double cycle into single cycle, reduce the time complexity, which is the technical points of sliding window;

Of course, there are many deformation of sliding window, such as length is not fixed, sliding distance is not 1……

The above mentioned slide window algorithm part, next to learn the PRINCIPLE of TCP slide window:

TCP sliding window principle

At first, to ensure that each packet is received between sender and receiver. And in order, the sending process is:

However, this is too slow, so we upgrade to multiple parallel sends to increase throughput:

Later, in order to achieve “out-of-order” sending, the sender sends packet 3 when it gets packet 1, rather than waiting for packet 2 to send packet 3.

Thus, the sliding window was introduced;

The window is divided into two parts: sent (not Ack) and to be sent (not Ack). When the sent packet is confirmed by Ack, the window will move, and the unsent packet will be transferred to the to be sent, and the move will continue until all the packets are sent. For packet loss, the sliding window has a timeout retransmission mechanism.

The biggest advantage of sliding window is that the receiver can inform the window size according to its own situation, so as to control the reception of the sender and control the flow.

This article is a small citation, and more on sliding window deformation algorithms or applications will follow

I am Anthony Nuggets, the public account of the same name, output exposure input, technical insights into life, see you next time ~~