Zero surprises. It's the same as in any other language.
And thank god for that. Theoretical computer science is still good ;)
I was a bit surprised that deque
is implemented as a linked list and not, for example, a ring buffer. It would mean that index reads would be constant time (though insert and delete at an index would be linear time), the opposite of using a linked list.
But a ring buffer is a FIFO data structure that can be implemented using linked lists. What ring buffer implementation did you have in mind?
Standard ring buffers or circular buffers are implemented as continuous vectors, with a read and write pointer.
Rust's VecDeque
is a ring buffer: https://doc.rust-lang.org/std/collections/struct.VecDeque.html
Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.
No that's a subtly different thing. The storage is a contiguous vector, but because it is a ring buffer there must be one pair of adjacent elements that are not contiguous in memory. That's what that comment is saying.
But because it is only one discontinuity it doesn't affect algorithmic complexity, so it is still O(1) to access elements, unlike a linked list which is O(N).
If you google "circular buffer" there will be loads of diagrams that make it really obvious how it works.
I am used to seeing ring buffers implemented using an array. They are FIFO if you write to the maximum offset and read from the minimum offset but they are double ended if you have a method to read from the maximum offset and write to the minimum offset.
Python
Welcome to the Python community on the programming.dev Lemmy instance!
📅 Events
Past
November 2023
- PyCon Ireland 2023, 11-12th
- PyData Tel Aviv 2023 14th
October 2023
- PyConES Canarias 2023, 6-8th
- DjangoCon US 2023, 16-20th (!django 💬)
July 2023
- PyDelhi Meetup, 2nd
- PyCon Israel, 4-5th
- DFW Pythoneers, 6th
- Django Girls Abraka, 6-7th
- SciPy 2023 10-16th, Austin
- IndyPy, 11th
- Leipzig Python User Group, 11th
- Austin Python, 12th
- EuroPython 2023, 17-23rd
- Austin Python: Evening of Coding, 18th
- PyHEP.dev 2023 - "Python in HEP" Developer's Workshop, 25th
August 2023
- PyLadies Dublin, 15th
- EuroSciPy 2023, 14-18th
September 2023
- PyData Amsterdam, 14-16th
- PyCon UK, 22nd - 25th
🐍 Python project:
- Python
- Documentation
- News & Blog
- Python Planet blog aggregator
💓 Python Community:
- #python IRC for general questions
- #python-dev IRC for CPython developers
- PySlackers Slack channel
- Python Discord server
- Python Weekly newsletters
- Mailing lists
- Forum
✨ Python Ecosystem:
🌌 Fediverse
Communities
- #python on Mastodon
- c/django on programming.dev
- c/pythorhead on lemmy.dbzer0.com
Projects
- Pythörhead: a Python library for interacting with Lemmy
- Plemmy: a Python package for accessing the Lemmy API
- pylemmy pylemmy enables simple access to Lemmy's API with Python
- mastodon.py, a Python wrapper for the Mastodon API