this post was submitted on 25 Oct 2024
35 points (100.0% liked)

Python

6368 readers
15 users here now

Welcome to the Python community on the programming.dev Lemmy instance!

πŸ“… Events

PastNovember 2023

October 2023

July 2023

August 2023

September 2023

🐍 Python project:
πŸ’“ Python Community:
✨ Python Ecosystem:
🌌 Fediverse
Communities
Projects
Feeds

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
35
Python Big O: the time complexities of different data structures in Python (www.pythonmorsels.com)
submitted 3 weeks ago by [email protected] to c/[email protected]
8 comments fedilink hide all child comments
 

via https://mastodon.social/@treyhunner/113367936771761302

top 8 comments
sorted by: hot top controversial new old
[–] [email protected] 6 points 3 weeks ago (2 children)

Zero surprises. It's the same as in any other language.

[–] [email protected] 6 points 3 weeks ago

And thank god for that. Theoretical computer science is still good ;)

[–] [email protected] 3 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

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.

[–] [email protected] 1 points 3 weeks ago (2 children)

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?

[–] [email protected] 2 points 3 weeks ago (1 children)

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

[–] [email protected] 0 points 3 weeks ago (1 children)

Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.

[–] [email protected] 2 points 3 weeks ago

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.

[–] [email protected] 1 points 2 weeks ago

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.