bytearray
A bytearray is a mutable sequence of
integers in $0..255$, stored as one contiguous C buffer — bytes with the immutability removed. It
recurs across the problems below because the largest data structure in a Project Euler solution is
usually a flag array: one slot per integer up to some bound, holding one bit of information. A
list will do that job, and will spend eight bytes and a pointer dereference per slot doing it.
The idea
Three properties do all the work.
One byte per element, contiguous. A million-element bytearray is 1,000,058 bytes; a
[0] * 1_000_000 list is 8,000,064 — and that is only the pointer array, before the integer objects
it points at. For a sieve over $10^8$ the difference decides whether the program runs at all.
Indexing yields int, slicing yields bytearray. sieve[i] is a plain integer, so a flag test
is if sieve[i]: with no unboxing ceremony. Slices stay in the byte world, which is what makes the
next property useful.
Strided slice assignment runs in C. This is the property that changes algorithms rather than memory footprints, and problem 10's Sieve of Eratosthenes is the canonical case:
sieve = bytearray(b"\x01") * (max_num + 1)
sieve[0] = sieve[1] = 0
for i in range(2, int(max_num ** 0.5) + 1):
if sieve[i]:
sieve[i * i:: i] = bytearray(len(range(i * i, max_num + 1, i)))
The inner loop of the sieve — the crossing-out — never executes in Python. bytearray(k) is a
zero-filled block of k bytes, and assigning it to the extended
slice i*i::i is a single strided memset at C speed. Only the
outer loop over $\sqrt{n}$ candidates is interpreted.
Compare problem 10's other sieve, the Sieve of Sundaram,
which marks the same kind of bytearray one element at a time from a Python loop:
marked = bytearray(n + 1)
for i in range(1, n + 1):
j = i
while i + j + 2 * i * j <= n:
marked[i + j + 2 * i * j] = 1
j += 1
Same container, same asymptotics, and at $n = 2 \times 10^6$ it takes 0.361 s against the
slice-assigned Eratosthenes' 0.058 s. The bytearray is not what made the first one fast; the
slice assignment was. Problem 77 marks a Sundaram sieve the same way, and gets away with it because
its bound is small.
The other C-speed method worth knowing is .count(). Problem 926 needs, for each of the
$O(\sqrt{n})$ bands of large primes sharing an exponent in $n!$, how many primes fall in that band —
and gets it with sieve[lo + 1:hi + 1].count(1), one buffer scan per band instead of a Python loop
over the range.
The same strided slice works for any set of moduli, not just all primes. Problem 272 counts cube roots of unity modulo $n$, and the structure of the problem splits every qualifying $n$ into a product of "good" primes ($p \equiv 1 \pmod 3$, plus a factor $9$) and a cofactor that must avoid all of them. Its cofactor table is a sieve that strikes out only the multiples of $3$ and of each good prime:
free = bytearray([1]) * (bound + 1)
for p in [3, *good_primes]:
free[p::p] = bytes(len(range(p, bound + 1, p)))
The survivors are not primes — they are the integers coprime to a chosen set — and the flags are
then folded into a prefix sum of the surviving values, so a query
"sum of admissible cofactors up to $x$" is one lookup. The primes themselves come from
primesieve; the bytearray does the part no prime library does. And the reduction keeps it small:
the table only has to reach $L$ divided by the smallest five-factor product, about $2 \times 10^5$
for $L = 10^{11}$.
The other two jobs
A bit-addressed DP table. When the state of a dynamic program is a bitmask, the table is indexed
by an integer $0..2^D-1$ and each entry is a single boolean. Problem 961 encodes a game position as
the integer whose binary digits mark which decimal digits are nonzero, and solves the whole impartial
game bottom-up into win = bytearray(1 << digits), reading win[reduced] for the position one move
on. The bit-array proper would be eight times denser again, but you
would pay for the packing in Python-level shifting; a bytearray is the point on that curve where
the interpreter stays out of the way.
A mutable string of digits. str is immutable, so mutating one digit costs a rebuild; a list of
int needs a "".join to become a number again. A bytearray holding ASCII codes is both at once —
mutable in place, and directly parseable, because int() accepts a bytes-like object:
digits = bytearray(b"0" * length)
digits[0] = 48 + value # 48 is ord("0")
number = int(digits) # int() parses the buffer as a numeral
Problem 254 uses exactly this to walk from one number to the next of the same
digit sum without ever building an intermediate string: the successor is
found by editing a suffix in place, and the result is read back as an integer with int(digits).
How to reason about it
- Values are $0..255$, and nothing else. Storing 256 raises
ValueError— usefully, since it fails at the write rather than silently truncating. The moment a slot needs a count rather than a flag, this is the wrong container: reach for alist,array, or NumPy. - Extended slice assignment must match lengths exactly.
len(range(i * i, n + 1, i))looks laborious next to a hand-computed count, but it is the correct spelling and a wrong one raises rather than corrupting the sieve — a free off-by-one check on the hottest line in the program. (Plain contiguous slices can resize; only strided ones are rigid.) - It is unhashable. A
bytearraycannot be adictkey or asetmember. When a mutable buffer needs to become a memo key — a board state, a canonical arrangement — freeze it withbytes(ba), which copies but hashes. - Build it inside
solve(), sized to the input. A module-level sieve with a fixed bound is computed once at import and is therefore free on every benchmark run after the first, which makes the reported time a fiction. Every sieve in this repository is constructed per call (size work to the input). - Know when to stop.
bytearrayis the best pure-Python array of flags, not the fastest thing available. On problem 10 at $2 \times 10^6$, the slice-assigned sieve takes0.058 s; theprimesievelibrary, a wheel-factorised C sieve, takes0.0028 s. Twenty times faster for one import — but also a dependency, and one that only solves the prime problem.bytearrayis what you use when the array is not a sieve of primes — and the two combine cleanly: problem 272 takes its primes fromprimesieveand builds only its custom "coprime to these" table as abytearray. - It is the one Python idiom that ports to C unchanged. A
bytearrayis acalloc'dchar *, and the strided slice assignment is thefor (j = i*i; j <= n; j += i) sieve[j] = 0you would have written anyway. That is why the sieve is the one place where the Python and C siblings in this repository read alike (parity across languages) — and why the Python version of a sieve-shaped problem is usually within a small factor of the C one, while a dict-shaped one is not.