Existe-t-il un moyen plus rapide de convertir un grand nombre arbitraire en une grande suite d'octets?

Question

Je possède ce code Python pour ce faire:

from struct import pack as _pack 

def packl(lnum, pad = 1): 
    if lnum < 0: 
     raise RangeError("Cannot use packl to convert a negative integer " 
         "to a string.") 
    count = 0 
    l = [] 
    while lnum > 0: 
     l.append(lnum & 0xffffffffffffffffL) 
     count += 1 
     lnum >>= 64 
    if count <= 0: 
     return '\0' * pad 
    elif pad >= 8: 
     lens = 8 * count % pad 
     pad = ((lens != 0) and (pad - lens)) or 0 
     l.append('>' + 'x' * pad + 'Q' * count) 
     l.reverse() 
     return _pack(*l) 
    else: 
     l.append('>' + 'Q' * count) 
     l.reverse() 
     s = _pack(*l).lstrip('\0') 
     lens = len(s) 
     if (lens % pad) != 0: 
      return '\0' * (pad - lens % pad) + s 
     else: 
      return s 

Cela prend environ 174 USEC pour convertir 2**9700 - 1 à une chaîne d'octets sur ma machine. Si je suis prêt à utiliser la méthode spécifique Python 2.7 et Python 3.x bit_length, je peux raccourcir cela à 159 usecs en pré-allouant le tableau l pour avoir exactement la bonne taille au début et en utilisant la syntaxe l[something] = au lieu de l.append .

Y a-t-il quelque chose que je puisse faire pour accélérer le processus? Cela sera utilisé pour convertir de grands nombres premiers utilisés en cryptographie ainsi que certains nombres plus petits (mais pas beaucoup).

Modifier

C'est actuellement l'option la plus rapide en Python < 3.2, il faut environ la moitié du temps ou l'autre direction que la réponse acceptée:

def packl(lnum, padmultiple=1): 
    """Packs the lnum (which must be convertable to a long) into a 
     byte string 0 padded to a multiple of padmultiple bytes in size. 0 
     means no padding whatsoever, so that packing 0 result in an empty 
     string. The resulting byte string is the big-endian two's 
     complement representation of the passed in long.""" 

    if lnum == 0: 
     return b'\0' * padmultiple 
    elif lnum < 0: 
     raise ValueError("Can only convert non-negative numbers.") 
    s = hex(lnum)[2:] 
    s = s.rstrip('L') 
    if len(s) & 1: 
     s = '0' + s 
    s = binascii.unhexlify(s) 
    if (padmultiple != 1) and (padmultiple != 0): 
     filled_so_far = len(s) % padmultiple 
     if filled_so_far != 0: 
      s = b'\0' * (padmultiple - filled_so_far) + s 
    return s 

def unpackl(bytestr): 
    """Treats a byte string as a sequence of base 256 digits 
    representing an unsigned integer in big-endian format and converts 
    that representation into a Python integer.""" 

    return int(binascii.hexlify(bytestr), 16) if len(bytestr) > 0 else 0 

En Python 3.2 la classe int a to_bytes et from_bytes des fonctions qui peuvent accomplir cela beaucoup plus rapidement que la méthode donnée ci-dessus.

Answer 1

Pour être complet et pour les futurs lecteurs de cette question:

à partir de Python 3.2, il existe des fonctions int.from_bytes() et int.to_bytes() qui effectuent la conversion entre bytes et int objets dans un choix de commandes d'octets.

Answer 2

Je suppose que vous devriez vraiment utiliser numpy, ce qui, je suis sûr, a quelque chose ou un autre construit pour cela. Il peut également être plus rapide de pirater avec le module array. Mais je vais y aller de toute façon.

IMX, la création d'un générateur et l'utilisation d'une compréhension de liste et/ou d'une sommation intégrée est plus rapide qu'une boucle qui s'ajoute à une liste, car l'ajout peut être effectué en interne. Oh, et "lstrip" sur une grande chaîne doit être coûteux.

De plus, certains points de style: les cas spéciaux ne sont pas assez spéciaux; et vous semblez ne pas avoir reçu le mémo sur la nouvelle construction x if y else z. :) Bien que nous n'en ayons pas besoin de toute façon. ;)

from struct import pack as _pack 


Q_size = 64 
Q_bitmask = (1L << Q_size) - 1L 


def quads_gen(a_long): 
    while a_long: 
     yield a_long & Q_bitmask 
     a_long >>= Q_size 


def pack_long_big_endian(a_long, pad = 1): 
    if lnum < 0: 
     raise RangeError("Cannot use packl to convert a negative integer " 
         "to a string.") 
    qs = list(reversed(quads_gen(a_long))) 
    # Pack the first one separately so we can lstrip nicely. 
    first = _pack('>Q', qs[0]).lstrip('\x00') 
    rest = _pack('>%sQ' % len(qs) - 1, *qs[1:]) 
    count = len(first) + len(rest) 
    # A little math trick that depends on Python's behaviour of modulus 
    # for negative numbers - but it's well-defined and documented 
    return '\x00' * (-count % pad) + first + rest 

Answer 3

Voici une solution d'appeler l'API Python/C via ctypes. Actuellement, il utilise NumPy, mais si NumPy n'est pas une option, il peut être fait purement avec ctypes.

import numpy 
import ctypes 
PyLong_AsByteArray = ctypes.pythonapi._PyLong_AsByteArray 
PyLong_AsByteArray.argtypes = [ctypes.py_object, 
           numpy.ctypeslib.ndpointer(numpy.uint8), 
           ctypes.c_size_t, 
           ctypes.c_int, 
           ctypes.c_int] 

def packl_ctypes_numpy(lnum): 
    a = numpy.zeros(lnum.bit_length()//8 + 1, dtype=numpy.uint8) 
    PyLong_AsByteArray(lnum, a, a.size, 0, 1) 
    return a 

Sur mon ordinateur, c'est 15 fois plus rapide que votre approche.

Edit: est ici le même code en utilisant ctypes seulement et retourner une chaîne au lieu d'un tableau numpy:

import ctypes 
PyLong_AsByteArray = ctypes.pythonapi._PyLong_AsByteArray 
PyLong_AsByteArray.argtypes = [ctypes.py_object, 
           ctypes.c_char_p, 
           ctypes.c_size_t, 
           ctypes.c_int, 
           ctypes.c_int] 

def packl_ctypes(lnum): 
    a = ctypes.create_string_buffer(lnum.bit_length()//8 + 1) 
    PyLong_AsByteArray(lnum, a, len(a), 0, 1) 
    return a.raw 

Ceci est encore deux fois plus rapide, pour un total d'un facteur d'accélération de 30 sur ma machine.

Answer 4

Je voulais juste poster une suite à la réponse de Sven (qui fonctionne très bien).Le opposé opération - allant d'octets arbitrairement long objet à Python objet entier nécessite les éléments suivants (car il n'y a pas de fonction de l'API C PyLong_FromByteArray() que je peux trouver):

import binascii 

def unpack_bytes(stringbytes): 
    #binascii.hexlify will be obsolete in python3 soon 
    #They will add a .tohex() method to bytes class 
    #Issue 3532 bugs.python.org 
    return int(binascii.hexlify(stringbytes), 16)