0

随着我的子字符串的大小增加，我怎样才能找到这部分代码的复杂性？

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

当我注意到我的程序运行时好像哈希函数在恒定时间内执行时，我变得很好奇。对于我的程序，如果“大小”为 165，最坏的情况是上述代码将执行 165 倍。我刚刚完成的一项测试显示 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

3

我不同意 DarthGizka。以下是同一篇维基百科文章的更多描述：

Pre-processing:
append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits. 
append 0 ≤ k < 512 bits '0', thus the resulting message length (in bits)
   is congruent to 448 (mod 512)
append ml, in a 64-bit big-endian integer. So now the message length is a multiple of 512 bits.

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    Extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

        ......

填充的工作只是一个预处理。更多的工作是在for each chunk. 由于 mattkaeo 的数据大小大于 1000000 个字符（第一个字符除外），因此 for 循环应该消耗最多的时间，而填充的消耗可以忽略不计。

我相信，mattkaeo 的结果不是很线性，因为他只运行每个样本一次，所以系统噪音（例如，操作系统和其他进程共享 CPU 能力）很重要。我运行每个样本 200 次：

import timeit
for i in range(1, 10000001, 1000000):
    random_str = randomly(i)
    print timeit.timeit('hashlib.sha1(random_str).hexdigest()',
                        setup='import hashlib; random_str="%s".encode("utf-8")' % random_str,
                        number=200)

结果更加线性：

0.000172138214111
0.303541898727
0.620085954666
0.932041883469
1.29230999947
1.57217502594
1.93531990051
2.24045419693
2.56945014
2.95437908173
于 2014-11-18T11:26:25.990 回答
2

在附加一个“1”位和输入大小之后，SHA-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 字节的块大小（步长）变大，这种影响会减弱。

当消息大小接近并超过各种内存缓存大小时，会发生其他显着变化：一级缓存（L1）通常为 32 KB，L2 为 256 KB，L3 缓存为 4、8 甚至 20 MB，依次为从最快到最慢。未缓存的内存访问甚至更慢。

在 mattkeo 的情况下，只要数据没有明显超过缓存大小，散列就会发现缓存是温暖的（也就是说，很多数据仍然在缓存中）。热缓存和非缓存内存之间的差异往往比命中率低的不冷不热或冷缓存更明显。

于 2014-11-18T10:28:12.237 回答