Pythonの二次元配列のin判定の高速化

サンプルコードの一部が脚注に飛ばされているので注意

--type2()はそれ以外の関数と違う結果を出します。--

Pythonで二次元配列に対してin判定を行うときは単純にforで回すよりもnumpy.whereを使ったほうが速いかもしれない

import random

import numpy

import time

#100回in判定

#Bool値が入ったリストを生成

def type1(l):

    testtime = time.time()

    BoolList = 

    for i in range(100):

        sig = False

        for n in l:

            if i in n:

                BoolList.append(True)

                sig = True

                break

        if sig != True:

            BoolList.append(False)

            

    print(time.time() - testtime)

def type2(l):

    testtime = time.time()

    BoolList = 

    for i in range(100):

        sig = True

        for n in l:

            a = numpy.array([i for n in range(len(n))])

            a = n - a

            if len*1[0]) < 1:

                BoolList.append(True)

                sig = False

                break

        if sig:

            BoolList.append(False)

    print(time.time() - testtime)

hoge = [random.randint(1, 100) for i in range(10)]

l = numpy.array([hoge for i in range(100)])

type1(l)

type2(l)

結果は、

type1 OUT> 0.027925491333007812

type2 OUT> 0.006983041763305664

結構速くなる。

BoolList = 

=>

BoolList =

---増設版---

import random

import numpy

import time

#100回in判定

#Bool値が入ったリストを生成

def type1(l):

    testtime = time.time()

    BoolList = 

    for i in range(100):

        sig = False

        for n in l:

            if i in n:

                BoolList.append(True)

                sig = True

                break

        if sig != True:

            BoolList.append(False)

            

    print(time.time() - testtime)

    return *2])

            a = i2 - a

            if len(numpy.where(a == 0)) > 0:

                BoolList.append(True)

                sig = False

                break

        if sig:

            BoolList.append(False)

    print(time.time() - testtime)

    return *3[0]) > 0:

            BoolList.append(True)

        else:

            BoolList.append(False)

    print(time.time() - testtime)

    return ((time.time() - testtime), BoolList)

def type4(l):

    testtime = time.time()

    Sumple = [i for i in range(100)]

    a = [numpy.where(l == i)[0] for i in Sumple]

    BoolList = [True if len(i) > 1 else False for i in a]

    print(time.time() - testtime)

    return ((time.time() - testtime), BoolList)

hoge = [random.randint(1, 100) for i in range(100)]

l = numpy.array([hoge for i in range(100)])

type1(l)

type2(l)

type3(l)

type4(l)

print(type1(l)[1] == type3(l)[1])

print(type1(l)[1] == type2(l)[1] == type3(l)[1] == type4(l)[1])

type1 OUT>0.01194310188293457

type2 OUT>0.0019948482513427734

type3 OUT>0.00498652458190918

type4 OUT>0.003988981246948242

OUT> True

OUT> False

この結果を見てもtype1が一番遅い。

ちなみに計算量は

type1: O(100n)

type2: O(100n)

type3: O(100)

type4: O(n)

って感じ。

※ただうまく動くかは保証しない。

*1:numpy.where(a == 0

*2:time.time() - testtime), BoolList)

def type2(l):

    testtime = time.time()

    BoolList = []

    for i in range(100):

        sig = True

        for i2 in l:

            a = numpy.array([i for m in range(len(i2

*3:time.time() - testtime), BoolList)

def type3(l):

    testtime = time.time()

    BoolList = []

    for i in range(100):

        a = l - i

        if len((numpy.where(a == 0