Java nesting for loop optimization solution
Nested for loops in Java can cause performance issues when working with large data sets. By optimizing these cycles, the execution efficiency of the program can be significantly improved.
Here are several common optimization methods, accompanied by detailed code examples and comments.
1. Reduce the number of cycles
Reduce unnecessary loop iterations by exiting the loop early with appropriate conditions.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (someCondition(i, j)) {
// operate break; // Exit the inner loop early }
}
}2. Merge loop
Merge independent loops into one loop, reducing the number of layers of loops.
// Original codefor (int i = 0; i < n; i++) {
// Operation A}
for (int i = 0; i < n; i++) {
// Operation B}
// After optimizationfor (int i = 0; i < n; i++) {
// Operation A // Operation B}3. Use more efficient data structures
Reduce time complexity by using appropriate data structures. For example, use HashMap instead of nested loops for lookup operations.
// Original codefor (int i = 0; i < (); i++) {
for (int j = 0; j < (); j++) {
if ((i).equals((j))) {
// operate }
}
}
// After optimizationMap<Type, Boolean> map = new HashMap<>();
for (Type item : list2) {
(item, true); // Put the element of list2 into the Map}
for (Type item : list1) {
if ((item)) {
// operate }
}4. Parallel processing
Use multithreading or parallel streams to process loops in parallel, and use multi-core processors to improve performance.
// Parallel streaming using Java 8().forEach(item -> {
// operate});5. Preprocessing and caching
Preprocess and cache some values that are repeatedly calculated in the loop, reducing unnecessary calculations.
int cachedValue = computeExpensiveValue(); // Preprocessing calculationfor (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int result = someFunction(cachedValue, i, j); // Use cached values }
}6. Optimization through algorithms
Use more efficient algorithms instead of nested loops. For example, dynamic programming, division and conquer methods, etc. are used to reduce time complexity.
// Original codefor (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// operate }
}
// After optimization, assume that some operation can be optimized using dynamic programmingint[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = computeValue(i, j, dp); // Use dynamic programming to cache results }
}7. Minimize object creation
Try to avoid frequent objects creation in loops, because object creation and garbage collection will affect performance. Objects can be created using an object pool or pre-created.
// Original codefor (int i = 0; i < n; i++) {
List<Integer> tempList = new ArrayList<>();
// operate}
// After optimization, use object poolList<List<Integer>> objectPool = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> tempList;
if (i < ()) {
tempList = (i); // Get the object from the pool } else {
tempList = new ArrayList<>();
(tempList); // Add new object to the pool }
(); // Clear the object // operate}8. Local variable optimization
Caches global variables or attributes frequently used in the loop into local variables to reduce search time.
// Original codefor (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
(i, j);
}
}
// After optimizationSomeClass localObject = someObject; // Cache to local variablesfor (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
(i, j); // Use local variables }
}Dynamic programming optimization example: longest incremental subsequence
Suppose we have a two-dimensional array with the value of each position representing a height.
We want to find the longest incremental path from any position, each step can be moved to a position adjacent to the upper, lower, left and right, and the value of the position moved to must be strictly greater than the current value.
public class LongestIncreasingPath {
public static void main(String[] args) {
int[][] matrix = {
{9, 9, 4},
{6, 6, 8},
{2, 1, 1}
};
int result = longestIncreasingPath(matrix);
("Longest Increasing Path: " + result); // 4 should be output }
public static int longestIncreasingPath(int[][] matrix) {
if (matrix == null || == 0 || matrix[0].length == 0) {
return 0;
}
int rows = ;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols]; // Used to save the longest incremental path length for each location int maxLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxLength = (maxLength, dfs(matrix, dp, i, j));
}
}
return maxLength;
}
private static int dfs(int[][] matrix, int[][] dp, int i, int j) {
if (dp[i][j] != 0) {
return dp[i][j]; // If it has been calculated, return the result directly }
int rows = ;
int cols = matrix[0].length;
int max = 1; // The shortest path length is at least 1 (itself)
// Define four directions: up, down, left, right int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] direction : directions) {
int x = i + direction[0];
int y = j + direction[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > matrix[i][j]) {
max = (max, 1 + dfs(matrix, dp, x, y));
}
}
dp[i][j] = max; // Cache results return max;
}
}With this example, you can see how dynamic programming is used to optimize the original nested loop code, and avoid repeated calculations, greatly improving efficiency.
The actual effect of the above optimization method depends on the specific application scenario and data characteristics, so performance testing and analysis are recommended before application.
Summarize
These are personal experiences, I hope you can give you a reference, and I hope you can support me more.