Python の組み込みコンテナと collections.deque
python(C)Python には list, tuple, dict, set が組み込まれており、collections モジュールで deque が実装されている。
$ python3 --version
Python 3.10.7
list
連結リストではなく可変長配列で実装されている。
C++ STLのContainersとAlgorithms - sambaiz-net
a = ['d', 'ae', 'ff', 'b', 'c']
print(a[2:-1]) # => ['ff', 'b']
a.append('x')
print(a.pop()) # => 'x'
print(a) # => ['d', 'ae', 'ff', 'b', 'c']
print('ae' in a) # => True
print(sorted(a, key=len, reverse=True)) # => ['ae', 'ff', 'd', 'b', 'c']
v, w, x, y, z = a
print(x) # => ff
print(*a) # => d ae ff b c
tuple
list と似たようなことができるが、immutable で hashable なオブジェクト。
a = ('d', 'ae', 'ff', 'b', 'c')
# a.append('x') => AttributeError: 'tuple' object has no attribute 'append'
print(a + a) # => ('d', 'ae', 'ff', 'b', 'c', 'd', 'ae', 'ff', 'b', 'c')
# print({[100]: 100}) => TypeError: unhashable type: 'list'
print({tuple([100]): 100}) # => {(100,): 100}
dict
hash table で実装されており格納順を保持しない、と思いきや実は Python 3.6 からの実装では保持するようになっており、 Python 3.7 で言語仕様にも入った。 元々 sparse array に直接データの配列を格納していたものが、データは別の配列に順番に格納し、sparse array にはその index のみを持つことでメモリの使用率が 20% 以上減り、CPUのキャッシュメモリの効率も高まっているそうだ。
a = {'foo': 100, 'bar': 200}
print([k+str(v) for k, v in a.items()]) # => ['foo100', 'bar200']
print('foo' in a) # => True
print(sorted(a)) # => ['bar', 'foo']
del a['foo'] # => {'bar': 'a'}
set
hash table で実装されている。
a = {'d', 'ae'} | {'ff', 'b', 'c'}
print(len(a)) # => 5
print('c' in a) # => True
a.add('x')
a.remove('y') # => KeyError: 'y'
a.discard('y')
collections.deque
両端から O(1) でデータを追加できるキュー。
from collections import deque
d = deque()
d.append('x')
d.appendleft('y')
d.append('z')
print(d) # => deque(['y', 'x', 'z'])
d.pop() # => 'z'
d.popleft() # => 'y