2017-09-19 17 views
0

この関数を使用すると、時系列のエントロピーを推定できます。これは、Lempel-Ziv圧縮アルゴリズムに基づいています。 L_iを最短位置から始まるサブストリングのlongness 1 LN(N)Pythonを使用したLempel-Zivアルゴリズムに基づくEntropy Estimator

-

E =(1/N SUM_i L_iを)^:長さnの時系列に対して、エントロピーはとして推定値でありますiは以前に位置1からi-1に現れていない。推定エントロピーは、nが無限大に近づく時系列の実数エントロピーに収束する。

MATLAB関数での実装がすでにあります: https://cn.mathworks.com/matlabcentral/fileexchange/51042-entropy-estimator-based-on-the-lempel-ziv-algorithm?s_tid=prof_contriblnk

私が実現したいPythonであり、私はこのようにそれをやった:

def contains(small, big): 
    for i in range(len(big)-len(small)+1): 
     if big[i:i+len(small)] == small: 
      return True 
    return False 

def actual_entropy(l): 
    n = len(l) 
    sequence = [l[0]] 
    sum_gamma = 0 

    for i in range(1, n): 
     for j in range(i+1, n+1): 
      s = l[i:j] 
      if contains(s, sequence) != True: 
       sum_gamma += len(s) 
       sequence.append(l[i]) 
       break 

    ae = 1/(sum_gamma/n) * math.log(n)    
    return ae 

しかし、私はそれが時に遅すぎる計算しましたデータサイズが大きくなっています。 (データhereを見つけることができる)私はこのようなリストの何千も計算する必要があり、そのような長い時間がたまらない

0-1000: 1.7068431377410889 s 
1000-2000: 18.561192989349365 s 
2000-3000: 84.82257103919983 s 
3000-4000: 243.5819959640503 s 
... 

:消費入力と時間は次のようであるように、例えば、私は23832個の要素のリストを使用しました。この機能を最適化してより速く動作させるにはどうすればよいですか?

+1

リストで作業するのではなく、numpyで作業してみることができます。これによって処理が高速化される可能性があります。 – Kev1n91

+0

リストの代わりにnumpy配列を使用することをお勧めしますか? –

+1

データ構造には注意が必要です(配列上の多くのアペンディックス; numpyはここで助けになりません)。プロファイラを使用して遅いものをチェックしてください。 2つの候補は、 '' 'contains'''と' 'sequence.append'''です。前者はおそらくstartとして古い位置を再利用して最適化することができますが、アルゴリズムをチェックする必要があります。 – sascha

答えて

1

私はちょっと遊んで、StackOverflowの別のthreadからいくつかの異なるアプローチを試みました。そして、これは私が思いついたコードです:

numpy配列を文字列にキャストすることは、文字列を使って直接作業するよりも速くなります。あなたが提供するデータと私のマシン上で私のコードの非常に粗製のベンチマークである:あなたが外側のループを並列化する場合

N: my code - your code 
1000: 0.039s - 1.039s 
2000: 0.266s - 18.490s 
3000: 0.979s - 74.761s 
4000: 2.891s - 285.488s 

あなたは多分これがさらに高速化することができます。