ฝัง
- เผยแพร่เมื่อ 17 มิ.ย. 2024
- In this video, we explore 6 different approaches to creating Circular Buffers, exploring solutions in C#, Python, Crystal, C++, Elm and Erlang. We explore queues, static and dynamic arrays, immutable data structures and a fun agent based implementation.
Circular Buffers are First In, First Out (FIFO) queues that are a fixed size. They're usually backed by an array, which gives it great spatial/data locality (good for performance!)
Kick back and enjoy 50mins of learning with Jeremy and Erik, then go solve the exercise in your favourite way on Exercism.
Solve the exercise at: exercism.org/exercises/circul...
Join #48in24 at: exercism.org/challenges/48in24
C# Reference: github.com/microsoft/referenc...
Featured Solutions:
- exercism.org/tracks/csharp/ex...
- exercism.org/tracks/python/ex...
- exercism.org/tracks/crystal/e...
- exercism.org/tracks/cpp/exerc...
- exercism.org/tracks/elm/exerc...
- exercism.org/tracks/erlang/ex...
Timestamps:
00:00:00 Introduction
00:07:27 C#: derive from a Queue
00:12:23 Python: dynamic array
00:18:32 Elm: immutable data structure
00:25:50 Crystal: use static array with read and write index
00:35:58 C++: use static array with read and size
00:38:12 Erlang: genserver (agents)
00:47:08 Conclusion - วิทยาศาสตร์และเทคโนโลยี
I'm inspired now to revisit some of my circular-buffer solutions to de-cheat-ify them.
Nice! What's the favourite one you've done?
Jeremy and Erik, this is a powerful platform you have right here. Thank You
Thanks so much! Really glad you're enjoying it! Appreciate you taking the time to comment :)
I hated, despised this exercise when I encountered it. I was just getting comfortable with programming and C# but I had never even thought of creating a generic collection and also never been asked to just built something that does xyz without some clear nudges towards a correct solution. I'd do an exercise or 2 a day but this took me several days to figure out. In the end it was probably good for me to have persevered, then realised at some point that I can make a variation of a looped linked list and appreciated the final product that works entirely with pointers, basically the Crystal solution shown here.
It's bittersweet to find out now that there was a collection in the library the whole time that would've done everything right out of the bag!
Exercism is a great platform, keep up the good work, lads!
Thanks so much for the support and sharing your story! I'm sorry you despised the exercise at first(!!) but glad it worked out well for you in the end. I always try to remember that pain is where the learning is!
Thanks for the video. I especially appreciated the Erlang discussion. I would never think about spinning up processes for a data structure, but I also do not know Erlang very well. Very cool.
Great to hear! Thanks for commenting :) Yeah - the Erlang solution was really surprising but very cool!
I agree, that Erlang and Elixir are extremely powerful with their concurrency. After all, it's the only really mature stack for telecom-grade massive, low-latency and robust concurrency out there.
Still one should be aware, that message sending between Erlang processes comes with a small but significant overhead for the message communication and (many forget that point) copying the data between the strictly isolated processes.
Therefore: If you don't need the buffer to be in itself concurrent, i.e. acting and being accessible as a separate server, it might be more appropriate to use a plain old functional abstraction (see my comment on my Elixir solution).
I always learn something from these videos. Great combination of in-depth deep dive, but a dive that's done in stages in a way I think just about any beginner can follow along. Great video Exercism!
Awesome! Thank you so much for the kind words and support - it's really encouraging for us! :)
Flashbacks to the growing ring buffer I had to write a while back. Same logic, but if the consumer falls behind and you have to more than you can fit, it has to grow automatically. So many tests to make sure existing data is split and copied to the right place for all possible cases. You quickly see why most just make it fixed size.
So a little like how the Queue works in C# natively? Nice :)
Mutable lists are very convenient since you can add new items, and they grow accordingly, but it's important to keep in mind that despite their flexibility, they are not as performant as arrays. I liked the discussion on this topic, it was a good reminder of these concepts!
Thanks! Yeah - was a good reminder to me too! When you're so abstracted from the underlying details, you forget these things!
Love these videos, understanding concepts before solving problems helps a lot in properly learning them.
That's great to hear. Thanks for taking the time to comment - really appreciated!
You got a new subscriber. Keep up the good work
Awww, thanks so much! Hope you enjoy the others in the series!
I like to offer some thoughts to Elixir in particular and FP in general, since many think, mutable data can not be effciently done in it. That is not my experience.
The challenge with a data structure like a buffer or a queue with immutable data structures is to get constant access O(1) on either side. That is harder than with a stack, which only uses one side and can easily be implement with a linked list. And that has constant access at the head as we know.
There is an easy way to implement a circular buffer with O(1) on write and amortized O(1) on read in a functional language: You just use a tuple with the capacity, the count, one in and one out list. The only tricky part is: You have to copy the reversed in list to the out list, if that is empty on read (Therefore you get only amortized O(1))
This is very easily accomplished in Elixir due do its phantastic pattern matching:
@type t() :: {capacity::non_neg_integer(), count::non_neg_integer(), inq::list(), outq::list()}
@spec new(capacity::non_neg_integer()) :: t()
def new(capacity), do: {capacity, 0, [], []}
@spec read(t()) :: {{:ok, any()} | {:error, atom}, t()}
def read({_, 0, _, _} = b), do: {{:error, :empty}, b}
def read({_, _, [_|_],[]} = b), do: b |> shift_to_out() |> read()
def read({capa, count, inq, [next_out | outq]}), do: {{:ok, next_out}, {capa, count-1, inq, outq}}
defp shift_to_out({capa, count, inq, []}), do: {capa, count, [], Enum.reverse(inq)}
My whole solution can be found on exercism.org/tracks/elixir/exercises/circular-buffer/solutions/Pul.
Of course, you can that than use as the data structure in a process like a GenServer or and Agent, but: One should not use a process instead of a functional abstraction, because even the quick Beam adds overhead for inter-process communication. So, don't start a new process, where you just need a data structure, e.g. because you are already running in a server process. Embedding the data structure in an Agent can also be seen in my solution.
> There is an easy way to implement a circular buffer with O(1) on write and amortized O(1) on read in a functional language: You just use a tuple with the capacity, the count, one in and one out list. The only tricky part is: You have to copy the reversed in list to the out list, if that is empty on read (Therefore you get only amortized O(1))
That is very nice solution. It does look like your solution still creates new lists (e.g. in: `[item | inq]` and `[next_out | outq]`). While I assume that the underlying implementation in Elixir will be efficient, it will incur some perf/memory costs over a once-created array. The array will inevitably also have better data locality properties, which will also be beneficial to performance. That's not to say that your solution isn't an excellent circular buffer implementation!
> Embedding the data structure in an Agent can also be seen in my solution.
I really like that! It has proper separation of concerns. Great implementation.
@@ErikSchierboom
Thank you for your anwer, Erik.
> While I assume that the underlying implementation in Elixir will be efficient, it will incur some perf/memory costs over a once-created array. The array will inevitably also have better data locality properties, which will also be beneficial to performance.
Inevitably? Really? Do you have proof for that hypothesis?
That immutable data structures have an efficient penalty is a myth, which gets too rarely challenged. Not only are linked lists (if correctly used) an extremely efficient data structure (and that is mainly thanks to their immutability). You oversee another big point: Due to their very different stateless design, FP-programs allocate much less in the heap than on the stack. Additionally you have to take into account Erlangs architecture, which uses very small, local and isolated memory allocations in their processes, which is an advantage in many aspects (e.g. Erlang systems don't need a stop-the-world global garbage collection and therefore and due to their preemptive concurrency architecture can grant consistently low latency, which is impossible in most mainstream stacks).
But even if one could really save some nanoseconds by using mutual datastructures, that comes with huge costs: This effect is in my experience by far outweighed by all the disadvantages of mutability (inconsistent states, race conditions, loads of mental overhead and accidental complexity, let alone). I never built complex systems as relaxed and bugfree as with Elixir/Erlang. One has to experience that to believe it.
And that encompasses another myth: That you allegedly need static typing to craft a safe system. That is bullshit. Erlangs late binding and pattern matching is not only a system theoretical necessity for really complex systems, but is combined with its supervision architecture all the safety you need. Which is proven since 3 decades. Or did you ever encounter a blue screen or real latency in phone calls?
So, I prefer a proper functional language with a great productivity like Elixir (not to mention the incredible power house, that is called Erlang BEAM) any day to imperative (or "OO" with the one exception of Smalltalk) programming, under which I suffered for decades.
Are you going to add Rasket/Scheme lang too?
We already have both languages. Racket has the circular buffer exercise :)
exercism.org/tracks/racket
@@exercism_org OK thanks. Great! Very often it is Not mentioned .
We'll feature Racket when we look at Matching Brackets and Eliud's Eggs, and Scheme for Scrabble Score and RNA Transcription :)