5

Pythonリストをタプルに変換する（およびその逆）の時間の複雑さは何ですか：

tuple([1,2,3,4,5,6,42])
list((10,9,8,7,6,5,4,3,1))

O(N) または O(1)、つまり、リストはコピーされますか、それとも書き込み可能から読み取り専用に内部的に切り替えられた何かですか?

どうもありがとう！

4

2 に答える 2

11

これは O(N) 操作であり、tuple(list) は単にオブジェクトをリストからタプルにコピーします。SO、内部オブジェクトを変更することはできますが (変更可能な場合)、タプルに新しい項目を追加することはできません。

リストのコピーには時間がかかりO(N)ます。

>>> tup = ([1, 2, 3],4,5 ,6)
>>> [id(x) for x in tup]
[167320364, 161878716, 161878704, 161878692]
>>> lis = list(tup)

内部オブジェクトは引き続き同じオブジェクトを参照します

>>> [id(x) for x in lis]
[167320364, 161878716, 161878704, 161878692]

しかし、外側のコンテナは別のオブジェクトになりました。したがって、外側のオブジェクトを変更しても、他のオブジェクトには影響しません。

>>> 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

変更可能な内部オブジェクトを変更すると、両方のコンテナーに影響します。

>>> tup[0].append(100)
>>> tup[0], lis[0]
([1, 2, 3, 100], [1, 2, 3, 100])

タイミングを比較すると、リストのコピーとタプルの作成にかかる時間はほぼ同じですが、新しいプロパティを持つ新しいオブジェクトの作成にはオーバーヘッドがあるため、タプルの作成には少しコストがかかります。

>>> 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
于 2013-09-10T19:39:01.097 に答える