Aynı karakterin birden çok kez yanması

Question

Bir programlama zorluğu yapıyorum ve zorluklardan biriyle deliriyorum. Zorlukta, bir dizenin MD5'ini hesaplamam gerekiyor. dize aşağıdaki biçimde verilir:

n[c]: n bir sayıdır ve c bir karakteridir. Örneğin: Ben şu dizeyi verildi dek b3[a2[c]] =>baccaccacc

Her şey yolunda gitti:

1[2[3[4[5[6[7[8[9[10[11[12[13[a]]]]]]]]]]]]]

Bu dizeleri 6227020800 a 's ile bir dize dönüşür. Bu dize 6GB'tan fazla, bu yüzden pratik zamanda hesaplamak neredeyse imkansız. Yani, benim sorum:

Burada kullanabileceğim MD5'in özellikleri var mı?

Bunu kısa sürede yapmak için bir form olması gerektiğini biliyorum ve bunun, tüm dizenin birden çok kez tekrarlanan aynı karakterle ilgili olması gerektiğinden şüpheleniyorum.

Answer 1

Büyük olasılıkla sonucu tek bir değer olarak üretmek için bir (yinelemeli) işlev oluşturmuş olabilirsiniz. Bunun yerine, sonucu bir bayt akışı olarak üretmek için bir jeneratör kullanmalısınız. Bunları daha sonra byte byte by MD5 hash rutininize besleyebilirsiniz. Akışın boyutu bu şekilde önemli değildir, kullanılan bellekte değil, hesaplama süresi üzerinde bir etkisi olacaktır.

İşte tek geçişli ayrıştırıcı kullanarak bir örnek:

import re, sys, md5 

def p(s, pos, callBack): 
    while pos < len(s): 
    m = re.match(r'(d+)[', s[pos:]) 
    if m: # repetition? 
     number = m.group(1) 
     for i in range(int(number)): 
     endPos = p(s, pos+len(number)+1, callBack) 
     pos = endPos 
    elif s[pos] == ']': 
     return pos + 1 
    else: 
     callBack(s[pos]) 
     pos += 1 
    return pos + 1 

digest = md5.new() 
def feed(s): 
    digest.update(s) 
    sys.stdout.write(s) 
    sys.stdout.flush() 

end = p(sys.argv[1], 0, feed) 
print 
print "MD5:", digest.hexdigest() 
print "finished parsing input at pos", end 

Answer 2

tüm hash fonksiyonları öncelikle tüm dizeyi açmamalı nedenle, bit akımlar ile çalışmak üzere tasarlanmış ve emin karma sonra - yapmalısınız Dize verilerinin parçalarını üreten ve MD5 bağlamına besleyen jeneratör yazın. Ve MD5 64 bayt (veya char) arabelleği kullanır, bu nedenle 64 baytlık veri kümelerini içeriğe beslemek iyi bir fikir olur.

Answer 3

karma iyi özelliklerinden yararlanan al:

import hashlib 
cruncher = hashlib.md5() 
chunk = 'a' * 100 
for i in xrange(100000): 
    cruncher.update(chunk) 
print cruncher.hexdigest() 

tur sayısını (x = 10000) ve yığın (y = 100) bu nedenle, x * y = 13 uzunluğunu Tweak !. Buradaki nokta, algoritmayı dizininizin parçalarını (her biri x karakter uzunluğunda), birbiri ardına, y katıyla beslemenizdir.