# 4.2. 要素の削除
# 4.2.1. 比較対象
あるリストから条件をつけて要素を削除したい場合、 大きく２つにわけられるかなと思います。 １つ目は、新しくリストを作ってしまうこと。 ２つ目は、元あるリストから要素を削除すること。
# creating a new list.
def for_statement_append(lst):
new_lst = []
for e in lst:
if e % 2 == 0:
new_lst.append(e)
return new_lst
def list_comprehension(lst):
new_lst = [e for e in lst if e % 2 == 0]
return new_lst
# deleting an element from an original list.
def while_statement(lst):
tmp = []
while lst:
e = lst.pop()
if e % 2 == 0:
tmp.append(e)
while tmp:
lst.append(tmp.pop())
return lst
def for_statement_del(lst):
def reversed_enumerate(seq):
return zip(reversed(range(len(seq))), reversed(seq))
for i, e in reversed_enumerate(lst):
if e % 2 == 1:
del lst[i]
return lst
# 4.2.2. 測定結果
$ python3 4_2_list_deletion.py
# Case 0
# ([random.randint(0, 10**i - 1) for _ in range(10**0)], )
for_statement_append : 0.0004 [msec]
list_comprehension : 0.0005 [msec]
while_statement : 0.0009 [msec]
for_statement_del : 0.0016 [msec]
# Case 1
# ([random.randint(0, 10**i - 1) for _ in range(10**1)], )
for_statement_append : 0.0014 [msec]
list_comprehension : 0.0012 [msec]
while_statement : 0.0040 [msec]
for_statement_del : 0.0028 [msec]
# Case 2
# ([random.randint(0, 10**i - 1) for _ in range(10**2)], )
for_statement_append : 0.0119 [msec]
list_comprehension : 0.0082 [msec]
while_statement : 0.0330 [msec]
for_statement_del : 0.0144 [msec]
# Case 3
# ([random.randint(0, 10**i - 1) for _ in range(10**3)], )
for_statement_append : 0.1073 [msec]
list_comprehension : 0.0791 [msec]
while_statement : 0.3066 [msec]
for_statement_del : 0.1675 [msec]
# Case 4
# ([random.randint(0, 10**i - 1) for _ in range(10**4)], )
for_statement_append : 1.0735 [msec]
list_comprehension : 0.8335 [msec]
while_statement : 2.8832 [msec]
for_statement_del : 4.5954 [msec]
# Case 5
# ([random.randint(0, 10**i - 1) for _ in range(10**5)], )
for_statement_append : 12.0328 [msec]
list_comprehension : 10.0785 [msec]
while_statement : 33.7151 [msec]
for_statement_del : 379.7889 [msec]
$
# 4.2.3. 補足
まず、リスト内包表記が最も速かった。 また、元からあるリストから要素を削除するよりも、新しく作ってしまった方が速かった。 そして、要素数が多くなると del を使った削除は悲劇的に遅くなっている。
# 4.2.3.1. なんでリスト内包表記が速いのか？
for 文で書くと属性参照が生じてしまいますlst.append。
Python ではこの属性参照が殊の外重いのです。
そのため通常の 2 のfor 文よりも属性参照が無い 1 のリスト内包表記の方が速くなります。
# 4.2.3.2. なんで while 文は遅かったのか？
また 3 の書き方は 1, 2 に比べて、 たくさんの属性参照や関数呼び出しを行なっています。 そのため遅くなっています。
# 4.2.3.3. なんで for 文と del 文の組み合わせが遅いのか？
一般にプログラミングをしていて「配列」というとロッカーのように付け替えたりできないデータ構造を指している気がします。 反対に「リスト」というと自由に付け替えのできる電車のようなデータ構造を指している気がします。
これによって何が起こるかというと、例えば今回の for 文は index を指定して del しています。 恐らくその度に、配列の要素を１つずつずらす処理が走っているのだと思われます。 del 文は要素数が多くなると悲劇的に遅くなります。
Python の「リスト」は純粋な「リスト」ではなく「配列」に近いものです。 これはデメリットばかりではなく、リストの要素を探したいときは先頭から順番に探すのではなく、 ここ！だと見つけることができます。参照速度は O(1) で参照できます。 これだけだと何言ってるんだ？みたいな感じですが、別の機会でご紹介させてください。
また、末尾に付け足す append, 末尾から取り出す pop が、insert, remove とは別に専用に用意されているのは、 おそらくそのためです。
# 4.2.3.4. 先頭から削除したいときは
deque (opens new window) 型を使います。deque 型の速度については、以下の記事にまとまっています。