いいものをつくろう

CTOの日記

アルゴリズム

python loopでフィルターする処理、loop一回しと二回まわしとの比較

投稿日:

ループを二回こすとは無視できる、むしろ関数フィルターより速い

 

items = [{}...{}]

がありまして、特定の条件でフィルターしたいとします。

条件が2つあります。

この場合は

filterred_items = [ item for item in items if condition1]

filterred_items_2 = [ item for item in filterred_items if condition2]

と二回よびだすパターンと

 

一回で2つの条件をやってしまうこのパターン

filterred_items = [ item

for item in items

if condition1

if condition2 ]

のどっちがはやいんでしょうか?

という検証です。

で今回、少し特殊かもしれませんが、条件自体もitemの状態により有効な場合と

無効な場合の2値ありえる処理をかんがえます。

百聞は一見にしかず

#-*- coding: utf-8 -*-
import time
from collections import defaultdict

def timeit(method):
    def timed(*args, **kw):
        global calc
        calc = defaultdict(int)
        print ('===========')
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()
        print ('%r  %2.8f ms' % (method.__name__, (te - ts) * 1000))
        print("calc %s times" % sum(calc.values()))
        return result
    return timed

# items = [
#     {'item': 1, 'ts': 1569488756, 'value':500},
#     {'item': 2, 'ts': 1569488750, 'value':2}
# ]
import random

@timeit
def loop_twice(items):
    key1 = "ts"
    val1 = 8688499900
    if key1 and val1:
        ts = time.time()
        items = [i for i in items if abs(i.get(key1, 0) - ts) < val1]

    key2 = 'item'
    key3 = 'value'
    val3 = 3
    ng_items = {
        item[key2] for item in items
        if item.get(key2)
        if item.get(key3) and val3
        if item.get(key3) < val3
    }
    print(len(ng_items))
    return


@timeit
def loop_once(items):
    key1 = "ts"
    val1 = 8688499900
    if key1 and val1:
        ts = time.time()
        def ts_filter(doc):
            return abs(doc.get(key1, 0) - ts) < val1
    else:
        def ts_filter(doc):
            return True
    key2 = 'item'
    key3 = 'value'
    val3 = 3
    if key3 and val3:
        def rr_filter(doc):
            return doc.get(key3, -sys.maxsize) < val3
    else:
        def rr_filter(doc):
            return True

    ng_items = {
        item[key2] for item in items
        if item.get(key2)
        if ts_filter(item)
        if rr_filter(item)
    }
    print(len(ng_items))
    return

for i in range(5):
    N = 40 * 10**i
    items = [ dict(zip(('item', 'ts', 'value'), (x, y, z)))
              for x, y, z in zip(
            range(1, N+1),
            range(1569488750, 1569488750 + (100*N), 100),
            [ random.uniform(0, 10) for _ in range(N)]
        )
    ]
    print('N:%s' % N)
    loop_twice(items)
    #loop_once(items)

結果ですが

loop_twiseのほうが速い結果となりました。

loop_twiceの結果はこちら

N:40
===========
6
'loop_twice'  0.03480911 ms
calc 0 times
N:400
===========
112
'loop_twice'  0.23603439 ms
calc 0 times
N:4000
===========
1174
'loop_twice'  2.00223923 ms
calc 0 times
N:40000
===========
11973
'loop_twice'  20.94793320 ms
calc 0 times
N:400000
===========
120030
'loop_twice'  209.94615555 ms
calc 0 times

で、loop_onceの結果はこちら

N:40
===========
9
'loop_once'  0.04100800 ms
calc 0 times
N:400
===========
125
'loop_once'  0.26583672 ms
calc 0 times
N:4000
===========
1214
'loop_once'  2.27904320 ms
calc 0 times
N:40000
===========
12116
'loop_once'  24.24407005 ms
calc 0 times
N:400000
===========
120233
'loop_once'  234.66014862 ms
calc 0 times

なんでしょう。だいたい20%遅いです、ループ一つにして関数filterでフィルターする処理のほうが。以外でした。残念でした、だってloop_onceのほうが綺麗なのに。。。

一応def関数ではなくlambda関数でもためしましたが全く同じ結果となりました。

import sys
@timeit
def loop_once_lambda(items):
    key1 = "ts"
    val1 = 8688499900
    if key1 and val1:
        ts = time.time()
        ts_filter = lambda doc: abs(doc.get(key1, 0) - ts) < val1
    else:
        ts_filter = lambda doc: True
    key2 = 'item'
    key3 = 'value'
    val3 = 3
    if key3 and val3:
        rr_filter = lambda doc: doc.get(key3, -sys.maxsize) < val3
    else:
        rr_filter = lambda doc: True

    ng_items = {
        item[key2] for item in items
        if item.get(key2)
        if ts_filter(item)
        if rr_filter(item)
    }
    print(len(ng_items))
    return

 

この仮設を検証するために

defって関数で条件つきでパターンわけしてかえせるの?

もしらべましたので興味あるかたはこちら(python 関数を条件付きで返す方法)で。

 

ということで結果

ループを二回こすとは無視できる、むしろ関数フィルターより速い

とい結論に至りました。

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.