时间戳

首页 > 解决方案 > 在同一个循环的迭代之间，局部变量是重用还是重新分配？

java - 在同一个循环的迭代之间，局部变量是重用还是重新分配？

问题描述

我一直明白，在循环中定义一个局部变量并不会减慢它的速度，因为它们在同一个循环的迭代之间被重用。

我惊讶地发现，当我将局部变量的定义移到循环之外时，它会显着减少内存（39.4Mb 对 40Mb）。

在同一个循环的迭代之间，局部变量是重用还是重新分配？

我也看到了为循环中的局部变量分配空间

重复零问题（leetcode）：给定一个固定长度的整数数组 arr，复制每个出现的零，将剩余元素向右移动。

请注意，超出原始数组长度的元素不会被写入。

对输入数组进行上述修改，不要从函数返回任何内容。

import java.util.Arrays;

/**
 * algorithm: the zeroes divide the array into sub-arrays or subsets.
 * we move or shift the elements exactly once, to their final resting place R.I.P. ;)
 * The last subset will be shifted n0s places, the one before it, n0s -1 places and so on...
 * O(n)
 * @author likejudo
 *
 */
public class DuplicateZeroes {
    static void arrayCopy(int[] arr, int begin, int end, int n) {
        for (int i = end + 1; i >= begin ; i--) {
            int destination = i + n;
            if (destination < arr.length) {
                arr[destination] = arr[i];
            }
        }
    }

    public static void duplicateZeros(int[] arr) {
        int n0s = 0; // number of zeroes
        int last0At = -1; // last zero at index
        int boundary = 0; // rightmost boundary

        // find total n0s, last0At
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                n0s++;
                last0At = i;
            }
        }
//      System.out.format("n0s=%d last0At=%d \n", n0s, last0At);

        // if no zeroes or all zeroes, we are done
        if(n0s == 0 || n0s == arr.length) {
            return;
        }
        
        boundary = arr.length - n0s;

        while (n0s > 0) {
        //  System.out.format("before arrayCopy(%s, %d, %d, %d) ", Arrays.toString(arr), last0At, boundary, n0s);
            // move subset of all elements from last0At till boundary-1, by n0s spaces.
            arrayCopy(arr, last0At, boundary, n0s);
            // set start of subset to 0
            arr[last0At] = 0;
//          System.out.format("after arrayCopy : %s assigned arr[last0At=%d]=0\n", Arrays.toString(arr),last0At);
            // update boundary
            boundary = last0At - 1;
            // next subset to the left will have one less zero
            n0s--;
            last0At--;

            // find the next last zer0 At index
            while (last0At > 0 && arr[last0At] != 0)
                last0At--;
            // if no more...
            if (last0At <0 || arr[last0At] != 0) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        // input: [1, 0, 2, 3, 0, 4, 5, 0]
        // output: [1, 0, 0, 2, 3, 0, 0, 4]

        int[] arr = {0,0,0,0,0,0,0};
        System.out.println("input:  " + Arrays.toString(arr));

        duplicateZeros(arr);
        System.out.println("output: " + Arrays.toString(arr));

    }

}

在方法arrayCopy中，当我将局部变量移到destination循环外时，

前

    static void arrayCopy(int[] arr, int begin, int end, int n) {
        for (int i = end + 1; i >= begin ; i--) {
            int destination = i + n; // >>>>>>>>>>>>>>>>>>>>>>>
            if (destination < arr.length) {
                arr[destination] = arr[i];
            }
        }
    }

后

内存使用得到改善！（39.4 Mb 与 40 Mb）

static void arrayCopy(int[] arr, int begin, int end, int n) {
    int destination = 0; // >>>>>>>>>>>>>>>>>
    for (int i = end + 1; i >= begin ; i--) {
        destination = i + n;
        if (destination < arr.length) {
            arr[destination] = arr[i];
        }
    }
}

标签： javaperformance

解决方案

关于你的问题

我一直明白，在循环中定义一个局部变量并不会减慢它的速度，因为它们在同一个循环的迭代之间被重用。

在循环内声明局部变量不会减慢速度吗？

  • 是的你是对的。声明本地变量不会增加时间复杂度，或者如果它确实改变了运行时间，那么它太微不足道了，无法考虑。

  • LeetCode 的运行时和内存测量非常不准确，尤其是运行时。例如，我刚刚重新提交了以下解决方案，它说 39.6 MB，几天前说 43.3 MB 完全相同的解决方案没有字节更改：

enter image description here

  • Their test cases are usually limited because it is costly I guess, thus their benchmarking is not valuable.
public final class Solution {
    public static final void duplicateZeros(int[] arr) {
        int countZero = 0;

        for (int index = 0; index < arr.length; index++)
            if (arr[index] == 0) {
                countZero++;
            }

        int length = arr.length + countZero;

        for (int indexA = arr.length - 1, indexB = length - 1; indexA < indexB; indexA--, indexB--)
            if (arr[indexA] != 0) {
                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }

            } else {
                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }

                indexB--;

                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }
            }
    }
}
  • Overall it'd be best to focus on asymptotically efficient algorithms mostly, because benchmarking has lots of "how-tos" and we'd want to have really good resources (CPU, memory, etc.) with isolated test systems.

References

  • For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis1, 2.

推荐阅读