Please use more memory, it is OK!
Computer scientists and engineers: use more memory. It is fine.
As a matter of fact, if you want to collaborate to ensure that Moore's Law (and the equivalent memory variant) remains true, then you actually have a duty to keep pushing memory (and CPU/GPU) to the next level! Memory these days is cheap - go on, and cache whatever you want.
Search uses an absurd amount of caching and pre-computed data in memory. It is necessary. When you want to give the information back to the user in a blink of an eye, you have no choice but to do all the very heavy-lifting processing in the background, and "pre-cook" in memory a lot of what you want to serve the user. This is no cheating. It is technology.
In-memory caching makes everyone's life easier - and faster. Here is a problem that exemplifies this concept: https://leetcode.com/problems/range-sum-query-2d-immutable/
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
As a matter of fact, if you want to collaborate to ensure that Moore's Law (and the equivalent memory variant) remains true, then you actually have a duty to keep pushing memory (and CPU/GPU) to the next level! Memory these days is cheap - go on, and cache whatever you want.
Search uses an absurd amount of caching and pre-computed data in memory. It is necessary. When you want to give the information back to the user in a blink of an eye, you have no choice but to do all the very heavy-lifting processing in the background, and "pre-cook" in memory a lot of what you want to serve the user. This is no cheating. It is technology.
In-memory caching makes everyone's life easier - and faster. Here is a problem that exemplifies this concept: https://leetcode.com/problems/range-sum-query-2d-immutable/
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
- Start by having a separate matrix
- This matrix will contain the cumulative sum of all the elements from (0,0) to (i,j)
- You can compute (2) in linear time
- Now, when positions (x1,y1) and (x2,y2) are given, you can compute the result by looking up this auxiliary matrix
- Basically by inspection in the below picture, you will notice that to find the area in red:
- Sum(red) = Sum(red full) - Sum(orange) - Sum(green) + Sum(blue)
And there you have it. How fast does it work? Fast. Code is below, cheers, ACC.
public class NumMatrix
{
int[][] sumMatrix = null;
public NumMatrix(int[][] matrix)
{
this.sumMatrix = (int[][])matrix.Clone();
for (int r = 0; r < matrix.GetLength(0); r++)
{
for (int c = 0; c < matrix[0].GetLength(0); c++)
{
sumMatrix[r][c] = matrix[r][c];
if (r - 1 >= 0) sumMatrix[r][c] += sumMatrix[r - 1][c];
if (c - 1 >= 0) sumMatrix[r][c] += sumMatrix[r][c - 1];
if (r - 1 >= 0 && c - 1 >= 0) sumMatrix[r][c] -= sumMatrix[r - 1][c - 1];
}
}
}
public int SumRegion(int row1, int col1, int row2, int col2)
{
int sum = 0;
sum = sumMatrix[row2][col2];
if (row1 - 1 >= 0) sum -= sumMatrix[row1 - 1][col2];
if (col1 - 1 >= 0) sum -= sumMatrix[row2][col1 - 1];
if (row1 - 1 >= 0 && col1 - 1 >= 0) sum += sumMatrix[row1 - 1][col1 - 1];
return sum;
}
}
Comments
Post a Comment