# 4.2. 要素の削除

for 文の方が速い

# 4.2.1. 比較対象

あるリストから条件をつけて要素を削除したい場合、 大きく2つにわけられるかなと思います。 1つ目は、新しくリストを作ってしまうこと。 2つ目は、元あるリストから要素を削除すること。

# 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 しています。 恐らくその度に、配列の要素を1つずつずらす処理が走っているのだと思われます。 del 文は要素数が多くなると悲劇的に遅くなります。

Python の「リスト」は純粋な「リスト」ではなく「配列」に近いものです。 これはデメリットばかりではなく、リストの要素を探したいときは先頭から順番に探すのではなく、 ここ!だと見つけることができます。参照速度は O(1) で参照できます。 これだけだと何言ってるんだ?みたいな感じですが、別の機会でご紹介させてください。

また、末尾に付け足す append, 末尾から取り出す pop が、insert, remove とは別に専用に用意されているのは、 おそらくそのためです。

# 4.2.3.4. 先頭から削除したいときは

deque 型を使います。deque 型の速度については、以下の記事にまとまっています。

Last Updated: 11/11/2019, 11:17:29 PM