python中将列表转换为元组的时间复杂度，反之亦然
问题描述
将python列表转换为元组的时间复杂度是多少(反之亦然):
what is the time complexity of converting a python list to tuple (and vice versa):
tuple([1,2,3,4,5,6,42])
list((10,9,8,7,6,5,4,3,1))
O(N) 或 O(1)，即列表是否被复制或内部某处从可写切换为只读?
O(N) or O(1), i.e. does the list get copied or is something somewhere internally switched from writable to read-only?
非常感谢！
解决方案
这是一个 O(N) 操作，tuple(list) 只是简单地将对象从列表中复制到元组中.所以，您仍然可以修改内部对象(如果它们是可变的)，但您不能向元组添加新项目.
It is an O(N) operation, tuple(list) simply copies the objects from the list to the tuple. SO, you can still modify the internal objects(if they are mutable) but you can't add new items to the tuple.
复制列表需要 O(N) 时间.
>>> tup = ([1, 2, 3],4,5 ,6)
>>> [id(x) for x in tup]
[167320364, 161878716, 161878704, 161878692]
>>> lis = list(tup)
内部对象仍然引用相同的对象
Internal object still refer to the same objects
>>> [id(x) for x in lis]
[167320364, 161878716, 161878704, 161878692]
但是外部容器现在是不同的对象.因此，修改外部对象不会影响其他对象.
But outer containers are now different objects. So, modifying the outer objects won't affect others.
>>> tup is lis
False
>>> lis.append(10)
>>> lis, tup
([[1, 2, 3], 4, 5, 6, 10], ([1, 2, 3], 4, 5, 6)) #10 not added in tup
修改一个可变的内部对象会影响两个容器:
Modifying a mutable internal object will affect both containers:
>>> tup[0].append(100)
>>> tup[0], lis[0]
([1, 2, 3, 100], [1, 2, 3, 100])
时间比较表明列表复制和元组创建花费的时间几乎相同，但由于创建具有新属性的新对象有开销，因此创建元组稍微昂贵.
Timing comparison suggest list copying and tuple creation take almost equal time, but as creating a new object with new properties has it's overhead so tuple creation is slightly expensive.
>>> lis = range(100)
>>> %timeit lis[:]
1000000 loops, best of 3: 1.22 us per loop
>>> %timeit tuple(lis)
1000000 loops, best of 3: 1.7 us per loop
>>> lis = range(10**5)
>>> %timeit lis[:]
100 loops, best of 3: 2.66 ms per loop
>>> %timeit tuple(lis)
100 loops, best of 3: 2.77 ms per loop
相关文章