Python- HOF中非局部变量的空间复杂性
我想知道我是否要在HOF中引用非局部变量，这会花多少钱？例如：
def f():
lst = [1, 2, ... , 100]
def g():
print(lst) # or anything that references lst
g()
f()
我在想，如果递归深度达到100个级别，g如何知道在哪里可以找到lst？ Python如何在引擎盖下工作？如果是存储指向lst的指针，那么应该有额外的内存费用吗？希望我的问题有意义。谢谢！
I was wondering if I were to reference a nonlocal variable in a HOF, how much extra memory would it cost me? For example:
def f():
lst = [1, 2, ... , 100]
def g():
print(lst) # or anything that references lst
g()
f()
I was thinking that if the recursion depth reaches something like 100 levels, how does g know where to find lst? How does Python work under the hood? If it is storing a pointer to lst, there should be extra memory cost right? Hope my question makes sense. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
g的范围包括从封闭范围中读取对变量的访问（它需要nonlocal或global也能够重新分配） 。递归的存在对这里的范围没有影响。不，它只是遵循封闭范围中对
lst的引用，而不是将lst的内容复制到其本地框架中。在最糟糕的情况下，参考变量是每个帧的内存足迹的恒定因素增加，这是从空间复杂性的角度无关的。调用此功能的空间复杂性看起来可能为
o（len（lst） + space_cost_of_g_frame * call_to_g）。但是space_cost_of_g_frame是恒定的，所以它已删除，目前尚不清楚什么call_to_g_g是（现在，是0，是O（1）如果是无限或任何硬编码值）。最后，lst是一个硬编码的长度，也是o（1）。因此，此功能的总体空间成本为O（1），如您所写。要获取复杂性涉及的
n，您需要某种参数。由于复杂性分析仅与增长有关，因此，如果所有呼叫的成本都相同，无论输入如何，o（1）无论呼叫多么昂贵。这是依赖于实现的，但可能很小，除非您实际遇到一个真正的问题，否则不用担心，在这种情况下，不断的因素详细介绍了复杂性分析忽略的开始很重要（用例/应用程序/应用程序目标，机器/环境的特征，确切的功能代码，而不是伪代码等）。
g's scope includes read access to variables from the enclosing scope (it'd neednonlocalorglobalto be able to reassign as well). The presence of recursion has no impact on scoping here.No, it's just following a reference to
lstin the enclosing scope rather than copyinglst's contents to its local frame. At worst, the reference variable is a constant factor increase in the memory footprint of each frame which is irrelevant from a space complexity perspective.The space complexity of calling this function looks like it might be
O(len(lst) + space_cost_of_g_frame * calls_to_g). But thespace_cost_of_g_frameis constant, so it's dropped, and it's unclear whatcalls_to_gis (right now, it's 0, which is O(1), but that'd also apply if it was infinite or any hardcoded value). Finally,lstis a hardcoded length, also O(1). So the overall space cost of this function is O(1) as you've written it.To get
ninvolved in the complexity, you need a parameter of some sort. Since complexity analysis is only concerned with growth, if all the calls have the same cost regardless of the input, it's O(1) no matter how expensive that call might be.That's implementation-dependent, but probably miniscule and nothing to worry about unless you actually run into a real problem, in which case, constant factor details that complexity analysis ignores start to matter greatly (use case/application goals, characteristics of the machine/environment, the exact function code rather than pseudocode, etc).