Python, len e dimensione degli interi

Question

Quindi, cPython (2.4) ha un comportamento interessante quando la lunghezza di qualcosa si avvicina a 1 < < 32 (la dimensione di un int).

r = xrange(1<<30) 
assert len(r) == 1<<30 

va bene, ma:

r = xrange(1<<32) 
assert len(r) == 1<<32 
ValueError: xrange object size cannot be reported`__len__() should return 0 <= outcome 

Alex wowrange ha questo comportamento così. wowrange(1<<32).l va bene, ma len(wowrange(1<<32)) non funziona correttamente. Immagino che ci sia qualche azione in virgola mobile (che viene letta come negativa) in corso qui.

1. Che cosa sta succedendo esattamente qui? (questo è abbastanza ben risolto di seguito!)
2. Come posso aggirarlo? Longs?

(La mia domanda specifica è random.sample(xrange(1<<32),ABUNCH)) se la gente vuole affrontare direttamente a questa domanda!)

Answer 1

cPython presuppone che gli elenchi siano in memoria. Questo si estende agli oggetti che si comportano come liste, come xrange. In sostanza, la funzione len prevede che il metodo __len__ restituisca qualcosa che è convertibile in size_t, che non si verificherà se il numero di elementi logici è troppo grande, anche se tali elementi non esistono effettivamente nella memoria.

Answer 2

1<<32, quando trattata come un intero con segno, è negativo.

Answer 3

Troverete che

xrange(1 << 31 - 1) 

è l'ultima che si comporta come si desidera. Questo perché la massima firmato (32-bit) intero è 2^31 - 1.

1 << 32 non è un positivo segno a 32-bit integer (int tipo di dati di Python), quindi è per questo che stai ricevendo questo errore.

In Python 2.6, non riesco nemmeno a fare xrange(1 << 32) o xrange(1 << 31) senza ottenere un errore, molto meno len sul risultato.

Edit Se si vuole un po 'più in dettaglio ...

1 << 31 rappresenta il numero 0x80000000, che nella rappresentazione in complemento a 2 è il numero negativo rappresentabili più basso (-1 * 2^31) per un 32-bit int. Quindi sì, a causa della rappresentazione bit-a-bit dei numeri con cui stai lavorando, in realtà sta diventando negativo.

Per il numero di complemento a 32-bit 2, 0x7FFFFFFF è il numero intero rappresentabile più alto (2^31 - 1) prima di "overflow" in numeri negativi.

Further reading, se sei interessato.

Si noti che quando si visualizza qualcosa come 2147483648L nel prompt, la "L" alla fine significa che ora viene rappresentato come un "long integer" (64 bit, di solito, non posso fare promesse su come Python lo gestisce perché non ho letto su di esso).