混淆在Python中调整数组大小 [英] confused about resizing array in Python
问题描述
我的困惑来自下面这段代码：
memo = {1：1,2：1}
def fib_memo（n）：
全球备忘录
如果不是备忘录中的n：
memo [n] = fib_memo（n-1）+ fib_memo（n-2）
返回备忘录[n]
我曾经认为这段代码的时间复杂度是O（n），因为它的价值是
使用memoization。
然而，我最近被告知在Python中，字典是一种特殊的
数组并且向它添加新元素或者为了调整它的大小，实际上它是内部通过创建另一个数组并将旧数组复制到
并添加一个新数组来内部补充。
因此，对于memo [n] = fib_memo（n-1）+ fib_memo（n-2），它所用的时间
根本不是恒定的。 n越大，这个声明就越需要时间。
这里的任何人都可以熟悉python的内部机制确认
这个？
My confusion comes from the following piece of code:
memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
I used to think that the time complexity for this code is O(n) due to its
use of memoization.
However, I was told recently that in Python, dictionary is a special kind of
array and to append new element to it or to resize it, it is in fact
internally inplemented by creating another array and copying the old one to
it and append a new one.
Therefore, for "memo[n] = fib_memo(n-1) + fib_memo(n-2)", the time it taks
is not at all constant. The larger the n grows, the more time this statement
takes.
Can anybody here familiar with the internal mechanism of python confirm
this?
推荐答案
Ruan schreef：
Ruan schreef:
我的困惑来自以下一段代码：
memo = {1：1,2：1}
def fib_memo（n）：
global备忘录
如果不是备忘录中的n：
memo [n] = fib_memo（n-1）+ fib_memo（n-2）
返回备忘录[n]
我曾经认为这段代码的时间复杂度是O（n），因为它使用了memoization
。
然而，最近有人告诉我，在Python中，字典是一种特殊的
数组并且为它添加新元素或者调整它的大小，它实际上是
内部通过创建另一个数组并将旧数组复制到
并添加一个新数组来补充。
My confusion comes from the following piece of code:
memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
I used to think that the time complexity for this code is O(n) due to its
use of memoization.
However, I was told recently that in Python, dictionary is a special kind of
array and to append new element to it or to resize it, it is in fact
internally inplemented by creating another array and copying the old one to
it and append a new one.
这是不正确的。 Python词典经过高度优化，我认为时间复杂度对于
插入和查找都是不变的（即O（1））。
-
如果我能够进一步看到，那只是因为我站在了巨人的肩膀上。 - Isaac Newton
Roel Schroeven
That''s not correct. Python dictionaries are highly optimized and I
believe the time complexity is amortized constant (i.e. O(1)) for both
insertions and lookups.
--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton
Roel Schroeven
那么Python的名单怎么样？
执行list.append时究竟做了什么？
对于列表，是否有另一个较大的列表初始化，而且内容来自
old列表是否与新的附加列表一起复制到它？
" Roel Schroeven" < rs **************** @ fastmail.fmwrote in message
news：8I ************** ******** @ phobos.telenet-ops.be ...
Then how about Python''s list?
What is done exactly when list.append is executed?
For list, is there another larger list initialized and the contents from the
old list is copied to it together with the new appended list?
"Roel Schroeven" <rs****************@fastmail.fmwrote in message
news:8I**********************@phobos.telenet-ops.be...
Ruan schreef：
Ruan schreef:
我的困惑来自下面这段代码：
memo = {1：1,2：1}
def fib_memo（n） ：
全球备忘录
如果不是备忘录中的n：
memo [n] = fib_memo（n-1）+ fib_memo（n-2 ）
返回备忘录[n]
我以前认为此代码的时间复杂度为O（n），因为
My confusion comes from the following piece of code:
memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
I used to think that the time complexity for this code is O(n) due to
其
its
使用memoization。
但是，我最近被告知在Python中，字典是特殊的
use of memoization.
However, I was told recently that in Python, dictionary is a special
种类
kind of
数组并向其追加新元素或调整大小，它实际上是通过创建另一个数组并将旧的数组复制为
array and to append new element to it or to resize it, it is in fact
internally inplemented by creating another array and copying the old one
到
to
it并追加一个新的。
it and append a new one.
这是不正确的。 Python词典经过高度优化，我认为时间复杂度对于
插入和查找都是不变的（即O（1））。
-
如果我能够进一步看到，那只是因为我站在了巨人的肩膀上。 - Isaac Newton
Roel Schroeven
That''s not correct. Python dictionaries are highly optimized and I
believe the time complexity is amortized constant (i.e. O(1)) for both
insertions and lookups.
--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton
Roel Schroeven
2月4日上午7:41， "阮" < rds1 ... @ sh163.netwrote：
On Feb 4, 7:41 am, "Ruan" <rds1...@sh163.netwrote:
那么Python的列表怎么样？
什么是在执行list.append时完全完成了吗？
对于列表，是否有另一个更大的列表被初始化，并且
旧列表中的内容被一起复制到它使用新的附加列表？
Then how about Python''s list?
What is done exactly when list.append is executed?
For list, is there another larger list initialized and the contents from the
old list is copied to it together with the new appended list?
Qi ren you tian :-)
Llike与词典相似，剩下一些空余空间每次扩展名单
时，所有摊销成本都是O（n）。
HTH，
John
Qi ren you tian :-)
Llike with dictionaries, some spare space is left each time the list
is expanded, so over-all the amortised cost is O(n).
HTH,
John
这篇关于混淆在Python中调整数组大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
