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?

Showing Posts 1 to 3

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

katta
I having some trouble figuring out if I have set myself too strict of standards for my production server. Currently I can handle 75% of r...
New
peck
Hi everyone. My team and I have been working on a fairly modest app based around video streaming and chat, but we’ve landed a customer t...
New
achenet
Hello, I’m trying to build a basic Phoenix web-app, and I’d like to use Tailwind. However, when I launch mix phx.server, I get an error...
New
bradley
I really like the adapter patterns that ecto, nebulex, waffle, etc. use and would love find something similar for a key management servic...
New
unaware8150
Hello folks! So at work, we are seeing some situations where we have to define some “fixed” strings that are used across the codebase in...
New
Alvinkariuki
How Can I Optimise Compile Time Dependencies I have been building an elixir application for about 2 years now. Many modules and files ha...
New

Other Trending Topics Top

budgie
A little off-topic, but I feel like people here have a good head on their shoulders. I used to be quite good at making software. Was luc...
New
KristerV
Hey. Is there anyone here who creates agents in their apps? Not talking about using agents, but creating them. I’m finding it pretty diff...
New
mudasobwa
I fully migrated to my own harness from Anthropic/Gemini and I think it’s time to share it. Welcome DSH, the DeepSeek Harness, fully writ...
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
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
budgie
I love Elixir. It’s one of 2 programming languages I’ve ever fallen in love with. But I don’t use it anymore. Serverless was the promis...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews