Benchmark:

```
100000 initial elements
33374 L-queries
33299 R-queries
33327 replace-queries
8.4 ± 0.1 ms baseline
16.3 ± 0.1 ms solve_deque_optimized
20.1 ± 0.1 ms solve_deque
20.7 ± 0.2 ms solve_deque_sentinel
33.8 ± 0.4 ms solve_stacks2
34.5 ± 0.5 ms solve_stacks
97.5 ± 2.7 ms solve_linked_list
Python: 3.11.4 (main, Sep 9 2023, 15:09:21) [GCC 13.2.1 20230801]
```

(`baseline`

is just for curiosity, it just iterates and identifies the queries like I do in all my solvers. So for example my optimized deque solver takes ~7.9 ms to actually process the queries.)

##
Code

Attempt This Online!

```
from random import choices, randint, randrange
from time import perf_counter as time
from statistics import mean, stdev
from collections import deque
import sys
def baseline(A, queries):
for q in queries:
match q:
case 1, L:
pass
case 2, R:
pass
case 3, X, Y:
pass
def solve_list(A, queries):
a = A[:]
i = 0
for q in queries:
match q:
case 1, L:
i -= L
case 2, R:
i += R
case 3, X, Y:
a[i+1:i+2] = X, Y
return a
def solve_stacks(A, queries):
left = []
right = A[::-1]
for q in queries:
match q:
case 1, L:
for _ in range(L):
right.append(left.pop())
case 2, R:
for _ in range(R):
left.append(right.pop())
case 3, X, Y:
right[-2:-1] = Y, X
return left + right[::-1]
def solve_stacks2(A, queries):
left = []
right = A[::-1]
for q in queries:
match q:
case 1, L:
right += left[:~L:-1]
del left[-L:]
case 2, R:
left += right[:~R:-1]
del right[-R:]
case 3, X, Y:
right[-2:-1] = Y, X
return left + right[::-1]
def solve_deque(A, queries):
d = deque(A)
i = 0
for q in queries:
match q:
case 1, L:
d.rotate(L)
i -= L
case 2, R:
d.rotate(-R)
i += R
case 3, X, Y:
d[1] = X
d.insert(2, Y)
d.rotate(i)
return list(d)
def solve_deque_sentinel(A, queries):
d = deque(A)
d.append(None)
for q in queries:
match q:
case 1, L:
d.rotate(L)
case 2, R:
d.rotate(-R)
case 3, X, Y:
d[1] = X
d.insert(2, Y)
d.rotate(~d.index(None))
d.pop()
return list(d)
def solve_deque_optimized(A, queries):
d = deque(A)
rotate = d.rotate
prepend = d.appendleft
d.rotate(-1)
i = 1
for q in queries:
match q:
case 1, L:
i -= L
rotate(L)
case 2, R:
i += R
rotate(-R)
case 3, X, Y:
d[0] = Y
prepend(X)
rotate(i)
return list(d)
def solve_linked_list(A, queries):
head = curr = [None] * 3
for a in A:
curr[2] = curr = [curr, a, None]
curr[2] = [None] * 3
curr = head[2][2]
for q in queries:
match q:
case 1, L:
for _ in range(L):
curr = curr[0]
case 2, R:
for _ in range(R):
curr = curr[2]
case 3, x, y:
curr[1] = x
curr[2][0] = curr[2] = [curr, y, curr[2]]
out = []
curr = head[2]
while curr[2]:
out.append(curr[1])
curr = curr[2]
return out
funcs = [
# solve_list, # too slow
solve_stacks,
solve_stacks2,
solve_deque,
solve_deque_sentinel,
solve_deque_optimized,
solve_linked_list,
]
# Generate large test case
n = 10**5
A = choices(range(100), k=n)
i = 0
queries = []
while len(queries) < 10**5:
instr = randint(1, 3)
if instr == 1:
if i > 1:
L = randint(2, min(i, 4))
queries.append((1, L))
i -= L
elif instr == 2:
if i < n-2:
R = randint(2, min(n-1 - i, 4))
queries.append((2, R))
i += R
else:
if i < n-1:
queries.append((3, randrange(100), randrange(100)))
n += 1
count = next(zip(*queries)).count
print(len(A), 'initial elements')
print(count(1), 'L-queries')
print(count(2), 'R-queries')
print(count(3), 'replace-queries')
print()
# Correctness
expect = None
for f in funcs:
result = f(A, queries)
if expect is None:
expect = result
else:
assert result == expect
# Speed
funcs.append(baseline)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):5.1f} ± {stdev(ts):3.1f} ms '
for _ in range(25):
for f in funcs:
t0 = time()
f(A, queries)
times[f].append(time() - t0)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
print('\nPython:', sys.version)
```