[Python] xor: cosi' lento?
Daniele Varrazzo
piro a develer.com
Ven 17 Ott 2008 00:24:03 CEST
On Wed, 15 Oct 2008 16:15:06 +0200, Marco Mariani
<marco.mariani a prometeia.it> wrote:
> michele a nectarine.it wrote:
>
>> Ovviamente non sono a conoscenza di un altro modo per effettuare lo
>> xor tra byte di dati, ma mi sembra che il tempo richiesto per le
>> operazioni sia effettivamente troppo alto (perfino java è più veloce).
>>
>> Secondo voi come potrei risolvere?
>>
>
> Qualcosa tipo...
>
> Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
> [GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
> Type "help", "copyright", "credits" or "license" for more information.
> >>>
> >>> import Numeric
> >>>
> >>> a = Numeric.array("abcdefghi", typecode=Numeric.UnsignedInt8)
> >>> b = Numeric.array("jklmnolpq", typecode=Numeric.UnsignedInt8)
> >>>
> >>> print a ^ b
> [11 9 15 9 11 9 11 24 24]
> >>>
Quasi, ma non proprio. Mi ci sono divertito un po'. Sono partito dallo
script postato dall'OP nel messaggio di stasera, con un blocco main che
ripete 20 volte il calcolo:
if __name__ == '__main__':
data = open('test.img','rb').read()
x = EncoderDecoder()
for i in range(20):
assert(sha.new(x.create_random_block(data)).hexdigest() ==
'673b64b3cc85161fe5233dec6e091f444f3ce6ba')
Tempo originale (su un centrino 1.7GHz): 0m12.484s
Poi ho eliminato un po' di chiamate inutili nell'inner loop: è inutile
passare in continuazione da stringhe a interi e viceversa: meglio usare gli
interi il più possibile:
--- test1.py 2008-10-16 22:58:24.000000000 +0100
+++ test2.py 2008-10-16 22:50:21.000000000 +0100
@@ -9,14 +9,14 @@
if len(piece) % blocksize != 0:
raise Exception('size error')
self.N = len(piece)/blocksize
- random_block = ['\0']*blocksize
+ random_block = [ 0 ]*blocksize
bitlist = [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1,
0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1]
- for i in range(len(bitlist)):
+ for i in xrange(len(bitlist)):
if bitlist[i] == 1:
- block = piece[i*blocksize:i*blocksize+blocksize]
- for j in range(blocksize):
- random_block[j] = chr(ord(random_block[j]) ^
ord(block[j]))
- return ''.join(random_block)
+ block = map(ord,
piece[i*blocksize:i*blocksize+blocksize])
+ for j in xrange(blocksize):
+ random_block[j] ^= block[j]
+ return ''.join(map(chr, random_block))
Con queste modifiche il tempo scenda a 6.912s. La cosa pesante resta
l'inner loop in Python però. Con numpy si può spostare in C: quello che
suggerisci è grossomodo:
--- test2.py 2008-10-16 22:50:21.000000000 +0100
+++ test3.py 2008-10-16 22:50:15.000000000 +0100
@@ -3,19 +3,19 @@
import os
import sha
import sys
+import numpy
class EncoderDecoder(object):
def create_random_block(self,piece,blocksize=16384):
if len(piece) % blocksize != 0:
raise Exception('size error')
+ piece = numpy.array(map(ord, piece), dtype='uint8')
self.N = len(piece)/blocksize
- random_block = [ 0 ]*blocksize
+ random_block = numpy.zeros(blocksize, dtype='uint8')
bitlist = [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1,
0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1]
for i in xrange(len(bitlist)):
if bitlist[i] == 1:
- block = map(ord,
piece[i*blocksize:i*blocksize+blocksize])
- for j in xrange(blocksize):
- random_block[j] ^= block[j]
+ random_block ^= piece[i*blocksize:(i+1)*blocksize]
return ''.join(map(chr, random_block))
Ma, sorprendentemente, non è stato veloce come mi aspettavo: 5.875s
Forse il problema è che uint8 non è un tipo di dati alla moda dai tempi
del C=64? Lo xor non cambia se lo effettuo 4 byte alla volta, e usando gli
uint32 posso sfruttare meglio l'architettura della macchina. Quindi:
--- test3.py 2008-10-16 22:50:15.000000000 +0100
+++ test4.py 2008-10-16 23:19:51.000000000 +0100
@@ -9,14 +9,16 @@
def create_random_block(self,piece,blocksize=16384):
if len(piece) % blocksize != 0:
raise Exception('size error')
- piece = numpy.array(map(ord, piece), dtype='uint8')
+ dtype = numpy.uint32 # uint64 may be better on 64 bit
computers
+ piece = numpy.fromstring(piece, dtype=dtype)
self.N = len(piece)/blocksize
- random_block = numpy.zeros(blocksize, dtype='uint8')
+ blocksize //= dtype().nbytes
+ random_block = numpy.zeros(blocksize, dtype=dtype)
bitlist = [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1,
0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1]
for i in xrange(len(bitlist)):
if bitlist[i] == 1:
random_block ^= piece[i*blocksize:(i+1)*blocksize]
- return ''.join(map(chr, random_block))
+ return random_block.tostring()
Ora va meglio: 0.271s, una 50ina di volte più veloce dell'originale.
--
Daniele Varrazzo - Develer S.r.l.
http://www.develer.com
Maggiori informazioni sulla lista
Python