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: 8/8/2019, 8:53:30 PM