Очень быстрая прокатка га sh в Python? - PullRequest
Новая
       14

Очень быстрая прокатка га sh в Python?

2 голосов
/ 04 февраля 2020

Я пишу игрушечный rsync подобный инструмент в Python. Как и многие аналогичные инструменты, сначала он будет использовать очень быстрое ха sh в качестве бросающегося га sh, а затем SHA256, как только совпадение будет найдено (но у последнего нет топи * 1055). * здесь: SHA256, MDA5, и т. д. c. слишком медленны, как скользящий ха sh).

В настоящее время я тестирую различные быстрые методы ха sh: 

import os, random, time

block_size = 1024  # 1 KB blocks
total_size = 10*1024*1024  # 10 MB random bytes
s = os.urandom(total_size)

t0 = time.time()
for i in range(len(s)-block_size):
    h = hash(s[i:i+block_size])
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

Я получаю: 0,8 МБ / с ... поэтому встроенная функция Python hash(...) здесь слишком медленная.

Какое решение позволит быстрее га sh не менее 10 МБ / с на стандартной машине?

  • Я пробовал с 

    import zlib
...
    h = zlib.adler32(s[i:i+block_size])

    , но это не намного лучше (1.1 МБ / с)

  • Я пытался с sum(s[i:i+block_size]) % modulo, и это слишком медленно

  • Интересный факт: даже без каких-либо га sh fonction, само l oop работает медленно! 

    t0 = time.time()
for i in range(len(s)-block_size):
    s[i:i+block_size]

    Я получаю: только 3,0 МБ / с! Так что простой факт того, что у oop есть доступ к подвижному блоку на s, уже медленный.

Вместо того, чтобы заново изобретать колесо и писать свой собственный ха sh / или используйте пользовательские алгоритмы Рабина-Карпа, что бы вы предложили, сначала ускорить это l oop, а затем как ха sh?

Редактировать: (Частично ) решение для "Интересного факта" медленного l oop выше: 

import os, random, time, zlib
from numba import jit

@jit()
def main(s):
    for i in range(len(s)-block_size):
        block = s[i:i+block_size]

total_size = 10*1024*1024  # 10 MB random bytes
block_size = 1024  # 1 KB blocks
s = os.urandom(total_size)
t0 = time.time()
main(s)
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

С Numba, есть значительное улучшение: 40,0 МБ / с, но здесь все еще не сделано sh. По крайней мере, мы не заблокированы на скорости 3 МБ / с.

1 Ответ

0 голосов
/ 04 февраля 2020

что бы вы предложили, сначала ускорить этот l oop, а затем как ха sh?

Увеличить размер блока. Чем меньше размер вашего блока, тем больше python вы будете выполнять на байт, и тем медленнее будет.

edit: ваш диапазон имеет шаг по умолчанию 1, и вы не умножаете i на block_size, поэтому вместо итерации 10 * 1024 непересекающихся блоков по 1 Кб, вы перебираете 10 миллионов - 1024 в основном перекрывающихся блока

...