4

私はいくつかのパフォーマンス集約型のコードを書いており、それをさらに改善する方法について、cythonistas からフィードバックを得たいと思っていました。私が書いた関数の目的を説明するのは少し難しいですが、それらが何をするかはそれほど恐ろしいことではありません。最初の (大まかに) 数のリストの 2 つの辞書を取得し、それらを結合して 1 つの数のリストの辞書を取得します。一度しか実行されないので、最適化にはあまり関心がありません。2 番目は最初のものを呼び出し、次にその結果を使用して、基本的に numpy 配列に格納されたインデックスと配列のリスト内の数値を交差させ、(pybloomfiltermmap) ブルーム フィルターでクエリ (新しい数値) を形成します。

重いステップはネストされたループが原因であると判断し、使用するループの数を減らし、一度だけ発生する必要があるすべてのものをループから移動し、私の知る限りすべてを入力しました。それでも、2 番目の関数の i の各反復には約 10 秒かかりますが、これは長すぎます。HTMLコンパイル出力でまだ黄色として表示される主なものは、リストとnumpy配列のインデックス付きアクセスが原因であるため、リストをすべてnumpy配列に置き換えようとしましたが、改善できませんでした. フィードバックをお寄せいただければ幸いです。

#cython: boundscheck=False
#cython: wraparound=False

import numpy as np
cimport numpy as np

def merge_dicts_of_lists(dict c1, dict c2):
    cdef dict res
    cdef int n, length1, length2, length3
    cdef unsigned int i, j, j_line, jj, k, kk, new_line

    res =  {n: [] for n in range(256)}
    length1 = len(c1)

    for i in range(length1):
        length2 = len(c1[i])
        for j in range(length2):
            j_line = c1[i][j]
            jj = (j_line) % 256
            length3 = len(c2[jj]) 
            for k in range(length3):
                kk = c2[jj][k]
                new_line = (j_line << 10) + kk
    res[i].append(new_line)
    return res


def get_4kmer_set(np.ndarray c1, dict c2, dict c3, bf):
    cdef unsigned int num = 0
    cdef unsigned long long query = 0
    cdef unsigned int i, j, i_row, i_col, j_line
    cdef unsigned int length1, length2
    cdef dict merge 
    cdef list m_i 

    merge = merge_dicts_of_lists(c2, c3)
    length1 = len(c1[:,0])
    for i in range(length1):
        print "i is %d" % i
        i_row = c1[i,0]
        i_col = c1[i,1]
        m_i = merge[i_col]
        length2 = len(m_i)
        for j in range(length2):
            j_line = m_i[j]
            query = (i_row << 24) + (i_col << 20) + j_line
            if query in bf:
                num += 1
    print "%d yes answers from bf" % num
4

1 に答える 1

3

後世のために、トピック外の回答を追加していますが、それでも誰かに役立つことを願っています. 上に投稿したコードは、Ctyhon html コンパイル出力からわかるように、すでに短い C 行にコンパイルされているため、そのまま使用することに決めたものと大差ありません。

最も内側の操作はブルーム フィルター クエリだったので、2 つの方法でそのステップを高速化することが最も効果的であることがわかりました。1 つは、pybloomfiltermmap で使用されるハッシュ関数を、murmurhash3 の利用可能な C++ 実装に変更することでした。私は、pybloomfilter が sha を使用していることを発見しました。これは、暗号化ハッシュ関数として予想されるように、比較的低速でした。2 番目のブーストは、この論文 ( http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/rsa.pdf ) にあるトリックを適用することによってもたらされました。基本的に、BF の k 個の異なるハッシュの代わりに 2 つのハッシュ値の線形結合を使用することで、多くの計算を節約できると言われています。これら 2 つのトリックを組み合わせると、クエリ時間が 1 桁 (約 5 倍) 向上しました。

于 2013-08-09T20:41:50.127 に答える