垃圾收集运行时成本的大O分析 [英] Big O analysis of garbage collection runtime cost

问题描述

在用垃圾回收语言推理运行时成本时，用'n'(列表中元素的数量)而言，诸如 myList = null; 之类的语句的成本是多少?出于争论的考虑，请将该列表视为参考类型的单链接列表，而无需最终确定.

When reasoning about runtime cost in a garbage collected language, what is the cost of a statement such as myList = null; in terms of 'n' (the number of elements in the list)? For sake of argument, consider the list to be a singly linked list of reference types with no finalisation required.

更笼统地说，我正在寻找有关如何使用GC语言分析运行时成本的任何信息.

More generally, I'm looking for any information on how runtime cost can be analysed in a language with GC.

推荐答案

我自己的想法是，根据收集器的实现，成本很可能是O(1)或O(n).在标记和清除收集器中，根本无法到达无法访问的对象，因此我可以想象清除它们没有任何成本.(实际上，保持对象的生存状态可能会产生一定的成本，大概是通过使用世代来进行摊销.)相反，在一个简单的引用计数收集器中，我可以轻松地想象到花费O(n)进行清理...

My own thought is that the cost is likely to be either O(1) or O(n) depending on the collector implementation. In a mark and sweep collector the unreachable objects simply won't be reached, so I could imagine there being no cost associated with clearing them. (Infact there is an ongoing cost simply keeping objects alive, presumably amortised by using generations.) Conversely in a simple reference counting collector I could easily imagine it costing O(n) to do the cleanup...

在设计算法时，如何推理这一点对我来说并不明显.

It's not obvious to me how to reason about this when designing algorithms..

这篇关于垃圾收集运行时成本的大O分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！