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

stjefim
Hello! Suppose you are building workflow (order / task / payment) processing system with the following requirements: Each workflow con...
New
itzmidinesh
Hi all, I’m working on a Phoenix project where I need to make external HTTP requests and I’m trying to choose between Req and HTTPoison....
New
pragdave
How do I tell Hologram not to escape HTML when substituting into templates? {Textile.render(@product.long_description)} escapes the HTM...
New
leoschweizer
Hi, we run different LLM models across a cluster, with each node loading a configurable subset. Model-specific queues let nodes consume ...
New
rlipscombe
I’d like to create a file with 600 permissions (rw-------), but there’s a race condition if I create it and then change the permissions. ...
New
saleyn
Is there a way to import record definitions in the iex shell for pretty printing (similar to the rr command in the erl shell)? This woul...
New
rlipscombe
When I use Mix.install with a git dependency, using git@github.com:... how do I change the SSH identity used? I’ve got two Github accoun...
New

Other Trending Topics Top

dominicletz
Hey there, I haven’t seen a list of useful Elixir specific skills for the popular AI tools yet so I’m starting one here with my first. ...
New
raa-ziq
Hi everyone :waving_hand: I wanted to share something I’ve been building — NowBlind, a random chat app designed to help people discover ...
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
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
OndrejValenta
(I just needed to vent somewhere and LinkedIn is full of hope, or hype, I’m not sure which exactly) AI dream has many faces, but general...
New
kip
Localize is the next generation localisation library for Elixir. Think of it as ex_cldr version 3.0. The first version will be released ...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews