Imballaggio intero efficiente di dimensioni arbitrarie in Python

Question

La funzione struct.pack() consente di convertire interi di stringhe fino a 64 bit in byte. Qual è il modo più efficiente per comprimere un intero ancora più grande? Preferirei non aggiungere una dipendenza a moduli non standard come PyCrypto (che fornisce num_to_bytes()).

Answer 1

Come suggerito da S.Lott in un commento, è sufficiente convertire il numero in una stringa e comprimere tale stringa. Ad esempio,

x = 2 ** 12345 
struct.pack("40s", str(x)) 

Answer 2

Assumendo il manifesto vuole confezionare un intero grande come una stringa binaria, cioè non utilizzare un byte di archiviazione per cifra del numero. Un modo di fare questo sembra essere:

import marshal 

a = 47L 
print marshal.dumps(a) 

Questo stampa:

'l\x01\x00\x00\x00/\x00' 

Non posso dire che ho capito come interpretare questi bit, in questo momento ...

Answer 3

I intendi vuoi dire che vuoi solo usare tanti byte quanti ne hai bisogno per rappresentare il numero? per esempio. se il numero è:

• 255 o meno devi usare solo 1 byte
• 65535 o meno 2 byte
• 16777215 o inferiore a 3 byte
• etc etc

Sul Di solito il PDA di Psion ha uno schema di compressione in cui si legge il primo byte, si rileva se ha il bit più alto impostato e quindi legge un altro byte se lo ha. In questo modo continui a leggere i byte finché non leggi il numero "completo". Questo sistema funziona piuttosto bene se la maggior parte dei numeri con cui si ha a che fare sono abbastanza piccoli, poiché normalmente utilizzerai solo uno o due byte per numero.

L'alternativa è di avere uno (o più) byte che rappresentano il numero di byte totali utilizzati, ma a quel punto è fondamentalmente una stringa in Python comunque. vale a dire una stringa di 256 cifre base.

Answer 4

vuoi dire qualcosa come questo:

def num_to_bytes(num): 
    bytes = [] 
    num = abs(num) # Because I am unsure about negatives... 
    while num > 0: 
     bytes.append(chr(num % 256)) 
     num >>= 8 
    return ''.join(reversed(bytes)) 

def bytes_to_num(bytes): 
    num = 0 
    for byte in bytes: 
     num <<= 8 
     num += ord(byte) 
    return num 

for n in (1, 16, 256, 257, 1234567890987654321): 
    print n, 
    print num_to_bytes(n).encode('hex'), 
    print bytes_to_num(num_to_bytes(n)) 

che restituisce:

1 01 1 
16 10 16 
256 0100 256 
257 0101 257 
1234567890987654321 112210f4b16c1cb1 1234567890987654321 

io non sono solo sicuro di cosa fare al riguardo negativi ... io non sono così familiare con un po 'di rumore.

EDIT: Un'altra soluzione (che gestisce circa il 30% più veloce con i miei test):

def num_to_bytes(num): 
    num = hex(num)[2:].rstrip('L') 
    if len(num) % 2: 
     return ('0%s' % num).decode('hex') 
    return num.decode('hex') 

def bytes_to_num(bytes): 
    return int(bytes.encode('hex'), 16) 

Answer 5

Questo è un po 'hacky, ma si potrebbe passare attraverso la rappresentazione di stringa esadecimale, e lì per binari con il codec hex:

>>> a = 2**60 
>>> a 
1152921504606846976L 
>>> hex(a) 
'0x1000000000000000L' 
>>> hex(a).rstrip("L")[2:].decode('hex') 
'\x10\x00\x00\x00\x00\x00\x00\x00'  # 8bytes, as expected. 

>>> int(_.encode('hex'), 16) 
1152921504606846976L 

si rompe un po 'perché il codec esagonale richiede un numero pari di cifre, quindi avrai bisogno di pad per questo, e avrete bisogno di impostare un flag per gestire i numeri negativi.Ecco un generico pacchetto/decompressione:

def pack(num): 
    if num <0: 
     num = (abs(num) << 1) | 1 # Hack - encode sign as lowest bit. 
    else: 
     num = num << 1 
    hexval = hex(num).rstrip("L")[2:] 
    if len(hexval)%2 ==1: hexval = '0' + hexval 
    return hexval.decode('hex') 

def unpack(s): 
    val = int(s.encode('hex'), 16) 
    sign = -1 if (val & 1) else 1 
    return sign * (val>>1) 


for i in [10,4534,23467, 93485093485, 2**50, 2**60-1, -1, -20, -2**60]: 
    assert unpack(pack(i)) == i 

Con tutto il giocherellare per etc imbottitura richiesta, io non sono sicuro che è molto meglio di una soluzione arrotolato a mano però.