Repository files navigation

ArrayDeque is a fast, array-backed deque implementation for Python written in C. It provides high-performance double-ended queue operations similar to Python’s built-incollections.deque, with a straightforward and efficient design.

• Fast Operations: Quick appends and pops at both ends.
• Random Access: Efficient in-place item assignment and index-based access.
• Full API Support: Implements iteration, slicing (via__getitem__ and__setitem__), and common deque methods.
• C Extension: A complete CPython C-extension for optimal speed.
• Benchmark Included: Compare performance with Python’s built-incollections.deque.

There are two ways to install ArrayDeque.

Pre-built wheels are available on PyPI. Simply run:

pip install arraydeque

Clone the repository and install in editable mode to compile the C-extension:

git clone https://github.com/yourusername/arraydeque.gitcd arraydequepip install -e.

Once installed, use ArrayDeque just like the standard deque:

fromarraydequeimportArrayDeque# Create an ArrayDeque instancedq=ArrayDeque()# Append items on the rightdq.append(10)dq.append(20)# Append items on the leftdq.appendleft(5)# Access by indexprint(dq[0])# Output: 5# Pop itemsprint(dq.pop())# Output: 20print(dq.popleft())# Output: 5

ArrayDeque supports the standard deque API including methods likeextend,extendleft (which reverses the input order),clear, and iteration.

A benchmark script (benchmark.py) is provided to compare the performance of ArrayDeque withcollections.deque.

The benchmark tests various operations such as append, appendleft, pop, popleft, random access, and a mixed workload. Each operation is run 5 times, with the median time reported.

After running the benchmark with:

python benchmark.py

a plot (plot.png) is generated that visually compares the two implementations using a fivethirtyeight-style bar chart.

Tests are implemented using Python’s built-inunittest framework. Run the test suite with:

python test_arraydeque.py

Alternatively, if you’re usingtox, simply run:

tox

This project uses GitHub Actions for continuous integration. It includes three workflows:

• Release Workflow (.github/workflows/release.yml): Builds wheels for Ubuntu, macOS, and Windows, then publishes to PyPI.
• Test Workflow (.github/workflows/test.yml): Runs the test suite across multiple Python versions.
• tox Configuration (tox.ini): Defines test, lint, and formatting environments (usingruff).

To set up a development environment:

1. Clone the repository:

   git clone https://github.com/yourusername/arraydeque.gitcd arraydeque

2. Create a virtual environment:

   On Unix/macOS:

   python -m venv envsource env/bin/activate

   On Windows:

   python -m venv envenv\Scripts\activate

3. Install development dependencies:

   pip install tox

4. Format and lint the code:

   tox -e formattox -e lint

This project is distributed under the Apache License 2.0.