6. リストかイテレータか

リストの方が速い。

リスト、イテレータ、ジェネレータイテレータの3つを比較しました。 素直に1度全ての要素をリストに叩き込んでから、 for 文を回した方が速そうでした。

今回の比較で対象にするのは、二分探索木です。 二分探索木をこのコードの説明は、 こちらでご説明させていただきました。

6.1. 測定対象

測定対象は以下の通りです。

# 1. 1度全て要素を取り出してから for 文を回すもの
def list_iterator(
    binary_search_node: BinarySearchNode
) -> Iterator[BinarySearchNode]:
    return iter(binary_search_node.list())

# 2. 専用のイテレータ Path を用意し、
#    1つずつ順番に for 文で回すもの
def iterator(
    binary_search_node: BinarySearchNode
) -> Iterator[BinarySearchNode]:
    return Path(binary_search_node)

# 3. ジェネレータを使って再帰的に for 文で回すもの
def generator(
    binary_search_node: BinarySearchNode
) -> Iterator[BinarySearchNode]:
    bsn = binary_search_node
    if bsn.left:
        yield from bsn.left
    yield bsn.value
    if bsn.right:
        yield from bsn.right

6.2. 実行結果

実行結果は次の通りです。

$ python 6_1_binary_search_tree.py 

# Case 0
# ([random.randint(0, 10**0 - 1) for i in range(10**0)], )
list_iterator                            :   0.0014 [msec]
iterator                                 :   0.0061 [msec]
generator                                :   0.0011 [msec]

# Case 1
# ([random.randint(0, 10**1 - 1) for i in range(10**1)], )
list_iterator                            :   0.0066 [msec]
iterator                                 :   0.0215 [msec]
generator                                :   0.0071 [msec]

# Case 2
# ([random.randint(0, 10**2 - 1) for i in range(10**2)], )
list_iterator                            :   0.0602 [msec]
iterator                                 :   0.1865 [msec]
generator                                :   0.0806 [msec]

# Case 3
# ([random.randint(0, 10**3 - 1) for i in range(10**3)], )
list_iterator                            :   0.6468 [msec]
iterator                                 :   1.7297 [msec]
generator                                :   1.0678 [msec]

# Case 4
# ([random.randint(0, 10**4 - 1) for i in range(10**4)], )
list_iterator                            :   6.7514 [msec]
iterator                                 :  18.2437 [msec]
generator                                :  12.6572 [msec]

# Case 5
# ([random.randint(0, 10**5 - 1) for i in range(10**5)], )
list_iterator                            : 106.6255 [msec]
iterator                                 : 202.9075 [msec]
generator                                : 232.6605 [msec]

$

6.3. 補足

もう少しよく見てみると n を大きくするにつれて list_iterator, generator に比較して iterator の速度が改善しています。 これは list_iterator, generator が、再帰を使っているからだと思われます。

Last Updated: 5/24/2019, 2:47:11 AM