5

基本的に、定義された単純なハッシュ関数を何度も呼び出して、重複がいつ検出されるかをテストする関数があります。私はそれを使ってたくさんのシミュレーションを行う必要があるので、できるだけ速くしたいと思っています. これを行うためにcythonを使用しようとしています。cython コードは現在、0 から m^2 の範囲の値を持つ整数の通常の python リストで呼び出されます。

import math, random
cdef int a,b,c,d,m,pos,value, cyclelimit, nohashcalls   
def h3(int a,int b,int c,int d, int m,int x):
    return (a*x**2 + b*x+c) %m    
def floyd(inputx):
    dupefound, nohashcalls = (0,0)
    m = len(inputx)
    loops = int(m*math.log(m))
    for loopno in xrange(loops):
        if (dupefound == 1):
            break
        a = random.randrange(m)
        b = random.randrange(m)
        c = random.randrange(m)
        d = random.randrange(m)
        pos = random.randrange(m)
        value = inputx[pos]
        listofpos = [0] * m
        listofpos[pos] = 1
        setofvalues = set([value])
        cyclelimit = int(math.sqrt(m))
        for j in xrange(cyclelimit):
            pos = h3(a,b, c,d, m, inputx[pos])
            nohashcalls += 1    
            if (inputx[pos] in setofvalues):
                if (listofpos[pos]==1):
                    dupefound = 0
                else:
                    dupefound = 1
                    print "Duplicate found at position", pos, " and value", inputx[pos]
                break
            listofpos[pos] = 1
            setofvalues.add(inputx[pos])
    return dupefound, nohashcalls 

inputx と listofpos を変換して C 型の配列を使用し、C の速度で配列にアクセスするにはどうすればよいですか? 他に使用できるスピードアップはありますか? setofvalues を高速化できますか?

比較対象があるように、m = 5000 で floyd() を 50 回呼び出すと、現在、私のコンピューターでは約 30 秒かかります。

更新: floyd の呼び出し方法を示すサンプル コード スニペット。

m = 5000
inputx = random.sample(xrange(m**2), m)
(dupefound, nohashcalls) = edcython.floyd(inputx)
4

2 に答える 2

10

まず、関数に変数を入力する必要があるようです。その良い例がここにあります。

2 つ目はcython -a、"annotate" の場合、cython コンパイラによって生成されたコードの非常に優れた内訳と、それがどの程度汚れているか (読み取り: python api が重い) を色分けして示します。この出力は、何かを最適化しようとするときに非常に重要です。

第 3 に、 Numpyの操作に関する今や有名なページでは、Numpy 配列データへの高速な C スタイルのアクセスを取得する方法が説明されています。残念ながら、それは冗長で面倒です。ただし、最近の Cython ではTyped Memory Viewsが提供されており、これは使いやすく素晴らしいものです。他のことをしようとする前に、そのページ全体を読んでください。

10分かそこらの後、私はこれを思いつきました:

# cython: infer_types=True

# Use the C math library to avoid Python overhead.
from libc cimport math
# For boundscheck below.
import cython
# We're lazy so we'll let Numpy handle our array memory management.
import numpy as np
# You would normally also import the Numpy pxd to get faster access to the Numpy
# API, but it requires some fancier compilation options so I'll leave it out for
# this demo.
# cimport numpy as np

import random

# This is a small function that doesn't need to be exposed to Python at all. Use
# `cdef` instead of `def` and inline it.
cdef inline int h3(int a,int b,int c,int d, int m,int x):
    return (a*x**2 + b*x+c) % m

# If we want to live fast and dangerously, we tell cython not to check our array
# indices for IndexErrors. This means we CAN overrun our array and crash the
# program or screw up our stack. Use with caution. Profiling suggests that we
# aren't gaining anything in this case so I leave it on for safety.
# @cython.boundscheck(False)
# `cpdef` so that calling this function from another Cython (or C) function can
# skip the Python function call overhead, while still allowing us to use it from
# Python.
cpdef floyd(int[:] inputx):
    # Type the variables in the scope of the function.
    cdef int a,b,c,d, value, cyclelimit
    cdef unsigned int dupefound = 0
    cdef unsigned int nohashcalls = 0
    cdef unsigned int loopno, pos, j

    # `m` has type int because inputx is already a Cython memory view and
    # `infer-types` is on.
    m = inputx.shape[0]

    cdef unsigned int loops = int(m*math.log(m))

    # Again using the memory view, but letting Numpy allocate an array of zeros.
    cdef int[:] listofpos = np.zeros(m, dtype=np.int32)

    # Keep this random sampling out of the loop
    cdef int[:, :] randoms = np.random.randint(0, m, (loops, 5)).astype(np.int32)

    for loopno in range(loops):
        if (dupefound == 1):
            break

        # From our precomputed array
        a = randoms[loopno, 0]
        b = randoms[loopno, 1]
        c = randoms[loopno, 2]
        d = randoms[loopno, 3]
        pos = randoms[loopno, 4]

        value = inputx[pos]

        # Unforunately, Memory View does not support "vectorized" operations
        # like standard Numpy arrays. Otherwise we'd use listofpos *= 0 here.
        for j in range(m):
            listofpos[j] = 0

        listofpos[pos] = 1
        setofvalues = set((value,))
        cyclelimit = int(math.sqrt(m))
        for j in range(cyclelimit):
            pos = h3(a, b, c, d, m, inputx[pos])
            nohashcalls += 1
            if (inputx[pos] in setofvalues):
                if (listofpos[pos]==1):
                    dupefound = 0
                else:
                    dupefound = 1
                    print "Duplicate found at position", pos, " and value", inputx[pos]
                break
            listofpos[pos] = 1
            setofvalues.add(inputx[pos])
    return dupefound, nohashcalls

docs.cython.orgで説明されていないトリックはここにはありません。ここで私は自分でそれらを学びましたが、すべてが一緒になっていることを確認するのに役立ちます.

元のコードに対する最も重要な変更はコメントにありますが、それらはすべて、Python API を使用しないコードを生成する方法について Cython にヒントを与えることになります。

余談ですinfer_typesが、デフォルトで がオンになっていない理由は本当にわかりません。これにより、コンパイラーは可能な限り Python の型ではなく C の型を暗黙的に使用できるようになり、作業が軽減されます。

これを実行するcython -aと、Python を呼び出す行は、random.sample への呼び出しと、Python set() のビルドまたは追加だけであることがわかります。

私のマシンでは、元のコードは 2.1 秒で実行されます。私のバージョンは 0.6 秒で実行されます。

次のステップは、そのループから random.sample を取得することですが、それはあなたに任せます。

回答を編集して、ランドサンプルを事前計算する方法を示しました。これにより、時間が0.4 秒に短縮されます。

于 2012-12-19T23:06:47.133 に答える
0

この特定のハッシュ アルゴリズムを使用する必要がありますか? 辞書に組み込みのハッシュアルゴリズムを使用しないのはなぜですか? 例えば:

from collections import Counter
cnt = Counter(inputx)
dupes = [k for k, v in cnt.iteritems() if v > 1]
于 2012-12-19T20:50:41.703 に答える