alvises

alvises

After benchmarking queues they seem much faster than Lists on
appending.

  • [1,...1000] ++ [1001] O(n)
  • :queue.in(1,q) should be O(1) right?

last element

  • List.last([1,..,1000]) again O(n)
  • :queue.get_r(q) again O(1)

and they should be similar on prepending

  • List [0 | [1,..,1000]]
  • :queue.in_r(0,q)

Now, seeing queues implementation it seems reasonable. A queue generated from a list of numbers from 1 to 1000 is implemented as a tuple of two lists.

{ [1000, 999, 998,.., 501], [1, 2, 3, 4, .., 500] }

So the list is split in two and the last half part of the list is reversed. Since prepending an item in a list is fast O(1) then appending 1001 is fast because 1001 is prepended to the first list in the tuple. Same thing for getting the last element, with lists is O(n) and while with :queue is O(1).

My question is, what are the downsides of using queues over lists? Maybe enumerating the numbers from 500 to 1000 since that list is reversed?
Some rebalancing when enqueueing new elements?

First 3 of 3 Posts Switch mode

al2o3cr

al2o3cr

Your intuition is correct - the documentation for :queue has a list of slow operations:

All operations [have] an amortized O(1) running time, except
filter/2, join/2, len/1, member/2, split/2 that have O(n).

See also the paper referenced in those docs, “Purely Functional Data Structures” by Chris Okasaki for detailed analysis.

10
Post #1
alvises

alvises OP

Thanks a lot for the pdf! Super interesting!!

Isn’t len O(n) also on lists?

len/1 couldn’t it be made O(1) wrapping the queue around a struct, which has a :count field that is incremented/decremented at each operation?

— All posts loaded —

Where Next? Top

Trending in Questions Top

stjefim
Hello! Suppose you are building workflow (order / task / payment) processing system with the following requirements: Each workflow con...
New
jonnycharles
I’m in search of an Elixir library that offers PDF generation capabilities similar to Ruby’s Prawn. While there have been discussions abo...
New
spammy
I’m looking to build a personal workflow to quickly deploy web applications written in elixir/phoenix, for local consumption (ie not on t...
New
dli
Before I dive in myself, did anyone successfully sprinkle Hologram into their existing LiveView app? Looking for hints regarding: Addi...
New
bottlenecked
Hi all, I wanted to ask how the community is dealing with post-release steps. Today we have Ecto migrations, which make sure that the db...
New
roeland
Kia ora, We have been using elixir-google-api to connect to Google Drive. However, with the updates to Tesla due to CVEs this is now bro...
New
rahultumpala
Hello, I have an Elixir backend that implements a custom protocol over TCP. I want to load test the backend and assess the performance o...
New

Other Trending Topics Top

JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Damirados
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge & Solve. They are GUI (Emerge) and State management (S...
New
netoum
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
ausimian
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
juhalehtonen
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New

We're in Beta

About us Mission Statement