内存管理递归 Java

Question

内存管理递归 Java

6

我正在使用一个大的ArrayList进入Java递归。在一个递归步骤中，我将该列表分成两个大小各半的列表，并对这两个列表应用相同的方法进行递归。然而，由于在分裂之后不再需要这个大列表，我想要将它从内存中删除。在这里搜索了一段时间后，我得到了以下解决方案：

public some_object recursiveMethod(ArrayList large_List) {
    //Compute the two sublists
    ArrayList lower_half = lowerHalf(large_List);
    ArrayList upper_half = upperHalf(large_List);

   //Delete large list from memory
   large_List = null;

   //Recursively call on smaller lists
   return procedure(recursiveMethod(lower_half),recursiveMethod(upper_half));
}

这会起作用吗，也就是说，GC会删除大的列表吗？

- Skrodde

如果您的 large_list 还有其他引用，那么这可能不够。 - Gábor Bakos

4个回答

1

为什么要放弃旧的数组并创建两个较小的数组？也许可以保留数组，只是进行“虚拟”分割？lowerHalf将返回一个对象，记录数组中的起始和结束索引作为您的新虚拟数组。这样，您就可以在不打乱内容的情况下划分数组...

public some_object recursiveMethod(ArrayList large_List, int start, int end) {
    //Compute the two sublists
    StartEndIndexObj lower_half = lowerHalf(large_List);
    StartEndIndexObj upper_half = upperHalf(large_List);

   //Recursively call on smaller lists
   return procedure(recursiveMethod(large_List, lower_half.start, lower_half.end),
                    recursiveMethod(large_List, upper_half.start, upper_half.end));
    }

另外，还可以查看Sam的答案，其中包含使用List.subList的版本。

- dertoni

顺便问一下...我有时候会用“手动”的方式去做事情，因为在Pascal和C语言时代我们没有其他的解决方案，而不是使用库函数。我变老了... - dertoni

遗憾的是，“lowerHalf”和“upperHalf”比这更复杂。相应的值在“large_List”上是任意分散的。按照您的方法，我确实需要重新排列（在最坏的情况下）large_List中的所有元素。 - Skrodde

也许你可以使用不同的数据结构，比如平衡树？这样你可以“重复使用”内容对象，并且还可以直接访问“中间”...在构建树的同时，甚至可以保留一个大小计数... - dertoni

自平衡二叉搜索树的维基百科条目：http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree - dertoni

1

看起来像是分而治之。在这种情况下，最好避免使用本地（硬）引用（参数和临时变量），以及保持一个大列表和轻量级子列表视图，使用List.subList()（包装器，引用大型后备列表）或一对索引来避免垃圾收集开销。

如果这些子列表必须独立于原始列表进行修改，则可以在进入递归处理之前复制该大列表一次，这应该仍然比多个独立子列表副本更高效。

public some_object recursiveMethod(List large_List) {
    //Create views of the two sublists
    List lower_half = large_List.subList(0,large_List.size()/2);
    List upper_half = large_List.subList(large_List.size()/2,large_List.size());

   //Recursively call on list views
   return procedure(recursiveMethod(lower_half),recursiveMethod(upper_half));
}

public some_object recursiveMethod2(ArrayList large_List, int begin, int end) {
    //Create views of the two sublists
    int size = end - begin;
    int lowerBegin = begin;
    int lowerEnd = begin + size/2; //exclusive
    int upperBegin = lowerEnd;
    int upperEnd = begin + size; //exclusive

   //Recursively call on list views
   return procedure(recursiveMethod2(large_List,lowerBegin,lowerEnd),recursiveMethod2(large_List,upperBegin,upperEnd));
}

- Sam

很遗憾，我不能使用List结构，而需要使用ArrayList结构，因为我需要快速在两个子列表中找到中位数。从ArrayList中我可以做到这一点，但是从List中却不行。 - Skrodde

@Skrodde：你可以将large_List与起始和结束索引对一起传递。为了清晰起见，您可以添加recursiveMethod()的整个实现。- 请参见编辑 - Sam

经过一段时间的思考，你的方法似乎最适合我。非常感谢！ - Skrodde

0

垃圾回收器将删除所有无引用的对象。然而，并不是所有的JVM都支持这个功能。我不确定你是否有带GC的JVM。

- Mansouritta

但是large_List在之前的递归中被upper_half或Lower_half引用，因此在之前的递归方法完成之前无法回收它。 - Sylwester

有没有没有垃圾回收器的JVM？ - Eypros

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pablo Francisco Pérez Hidalgo · Accepted Answer

由于lower_half和upper_class仍然引用调用者中的列表，直到调用者完成后才取消对它们的引用，因此它不起作用。

例如，以procedure的第一个实际参数为例：recursiveMethod(lower_half)。 lower_half 引用被复制到被调用的recursiveMethod large_List实际参数中。所以你有同样的列表：

在调用者中作为lower_half引用。
在当前调用范围内作为large_list

在当前调用中，你将引用large_list设置为null，但没有将调用者的lower_half设置为null。因此，该列表仍然被某个地方引用，因此无法被GC收集。

内存管理 递归 Java

内存管理递归 Java