0

部分文字列のサイズが大きくなるにつれて、コードのこのセクションの複雑さをどのように見つけることができますか?

if size > 160:
    sub = (hashlib.sha1(sub.encode('utf-8')).hexdigest())

ハッシュ関数が一定時間で実行されているかのようにプログラムが実行されていることに気付いたとき、私は興味を持ちました。私のプログラムでは、「サイズ」が 165 の場合、最悪の場合、上記のコードは 165x 実行されます。私が行ったばかりのテストでは、sha1 が長さと不安定な関係で実行されていることがわかりました。

Length  Time
0   0
1   0.015000105
2   0.016000032
3   0.046000004
4   0.046999931
5   0.062000036
6   0.078000069
7   0.078000069
8   0.07799983
9   0.108999968

テストコード:

import string
import random
import hashlib
import time

def randomly(size=6, chars=string.ascii_uppercase + string.digits):
    return ''.join(random.choice(chars) for _ in range(size))

for i in range(1, 10000001, 1000000):
    random_str = randomly(i)
    start = time.time()
    str_hash = hashlib.sha1(random_str.encode('utf-8')).hexdigest()
    print time.time() - start
4

2 に答える 2

2

SHA-1アルゴリズムは、「1」ビットと入力のサイズを追加した後、入力 (「メッセージ」) を 512 ビットの倍数にパディングします。ウィキペディアのアルゴリズムの説明から：

append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits
append 0 ≤ k < 512 bits '0'
append ml (message length), in a 64-bit big-endian integer.

そのため、実行時間は入力のステップ関数であり、しばらく一定のままで、その後ジャンプします。

ただし、ブロック サイズ (ステップ) の 64 バイトに対してメッセージ サイズが大きくなるにつれて、この影響は小さくなります。

メッセージ サイズがさまざまなメモリキャッシュ サイズに近づき、それを超えると、その他の注目すべき変化が発生します。通常、レベル 1 キャッシュ (L1) では 32 KB、L2 では 256 KB、L3 キャッシュでは 4、8、さらには 20 MB の順に増加します。最も速いものから最も遅いものまで。キャッシュされていないメモリ アクセスはさらに遅くなります。

mattkeo の場合、データがキャッシュ サイズを大幅に超えない限り、ハッシングによってキャッシュがウォームであることが検出されます (つまり、多くのデータがまだキャッシュに残っていることになります)。ウォーム キャッシュとキャッシュされていないメモリの違いは、ヒット率の低い生ぬるいまたはコールド キャッシュよりも顕著になる傾向があります。

于 2014-11-18T10:28:12.237 に答える