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?
Trending in Questions
Other Trending Topics
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #blog-post
- #phoenix_html
- #iex
- #graphql
- #ai
- #genstage
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex











First 3 of 3 Posts
al2o3cr
Your intuition is correct - the documentation for
:queuehas a list of slow operations:See also the paper referenced in those docs, “Purely Functional Data Structures” by Chris Okasaki for detailed analysis.
alvises
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?
dom
Yes, some queue implementations do just that:
https://github.com/Qqwy/elixir_okasaki/blob/master/lib/okasaki/implementations/amortized_queue.ex#L9
http://ucsd-progsys.github.io/liquidhaskell-tutorial/09-case-study-lazy-queues.html