Ruby's builtin Datastructures

[Brian Schroeder]

Hello all,

for some time I'm wondering if there exists a library with datastructures
like deque, queue, list, btree, and similar in ruby, such that I don't
have to implement them myself?
Until now I have found nothing, so I'm posting here in the hope that I
should not have re-rtfm'd more.

Thanks,

Brian

 

[Simon Strandgaard]

for some time I'm wondering if there exists a library with datastructures
like deque, queue, list, btree, and similar in ruby, such that I don't
have to implement them myself?

deque, queue, list.. then ruby's builtin Array class will fit.


server> irb
irb(main):001:0> stack = []
=> []
irb(main):002:0> stack.push(3)
=> [3]
irb(main):003:0> stack.push(9)
=> [3, 9]
irb(main):004:0> stack.push(10)
=> [3, 9, 10]
irb(main):005:0> stack.pop
=> 10
irb(main):006:0> stack.pop
=> 9
irb(main):007:0> stack
=> [3]
irb(main):008:0>



which kind of btree do you want? b+ b* ... or

red-black tree
http://raa.ruby-lang.org/project/ruby-rbtree/

avl tree
http://raa.ruby-lang.org/project/ruby-avl/


Many goodies in the library section of RAA, which may interest you
http://raa.ruby-lang.org/cat.rhtml?category_major=Library

 

[Robert Klemme]

for some time I'm wondering if there exists a library with datastructures
like deque, queue, list, btree, and similar in ruby, such that I don't
have to implement them myself?

deque, queue, list.. then ruby's builtin Array class will fit.


server> irb
irb(main):001:0> stack = []
=> []
irb(main):002:0> stack.push(3)
=> [3]
irb(main):003:0> stack.push(9)
=> [3, 9]
irb(main):004:0> stack.push(10)
=> [3, 9, 10]
irb(main):005:0> stack.pop
=> 10
irb(main):006:0> stack.pop
=> 9
irb(main):007:0> stack
=> [3]
irb(main):008:0>

As queue:

irb(main):010:0> queue = []
=> []
irb(main):011:0> queue.push 1
=> [1]
irb(main):012:0> queue.push 2
=> [1, 2]
irb(main):013:0> queue.push 3
=> [1, 2, 3]
irb(main):014:0> queue.unshift
=> [1, 2, 3]
irb(main):015:0> queue.shift
=> 1
irb(main):016:0> queue.shift
=> 2
irb(main):017:0> queue.shift
=> 3
irb(main):018:0>

You can easily make that a bit more intuitive, if you like:

irb(main):018:0> class Array; alias :enq ush; alias :deq :shift; end
=> nil
irb(main):019:0> queue = []
=> []
irb(main):020:0> queue.enq 1
=> [1]
irb(main):021:0> queue.enq 2
=> [1, 2]
irb(main):022:0> queue.enq 3
=> [1, 2, 3]
irb(main):023:0> queue.deq
=> 1
irb(main):024:0> queue.deq
=> 2
irb(main):025:0> queue.deq
=> 3
irb(main):026:0> queue.deq
=> nil


And there's also a thread safe queue:

$ irb -r thread
irb(main):001:0> queue = Queue.new
=> #<Queue:0x1017ad68 @que=[], @waiting=[]>
irb(main):002:0> queue.enq 1
=> nil
irb(main):003:0> queue.enq 2
=> nil
irb(main):004:0> queue.enq 3
=> nil
irb(main):005:0> queue
=> #<Queue:0x1017ad68 @que=[1, 2, 3], @waiting=[]>
irb(main):006:0> queue.deq
=> 1
irb(main):007:0> queue.deq
=> 2
irb(main):008:0> queue.deq
=> 3

Regards

robert

 

[Brian Schroeder]

Thanks for your answer. I should have looked in the raa by myself. Just a
question regarding array as deque. How efficient is it? Is all the data
shifted through the array every time I push something at the front and
remove it from the back, or is it organized more efficiently?

Thanks,

Brian

deque, queue, list.. then ruby's builtin Array class will fit.


server> irb
irb(main):001:0> stack = []
=> []
irb(main):002:0> stack.push(3)
=> [3]
irb(main):003:0> stack.push(9)
=> [3, 9]
irb(main):004:0> stack.push(10)
=> [3, 9, 10]
irb(main):005:0> stack.pop
=> 10
irb(main):006:0> stack.pop
=> 9
irb(main):007:0> stack
=> [3]
irb(main):008:0>



which kind of btree do you want? b+ b* ... or

red-black tree
http://raa.ruby-lang.org/project/ruby-rbtree/

avl tree
http://raa.ruby-lang.org/project/ruby-avl/


Many goodies in the library section of RAA, which may interest you
http://raa.ruby-lang.org/cat.rhtml?category_major=Library

 

[Simon Strandgaard]

Thanks for your answer. I should have looked in the raa by myself. Just a
question regarding array as deque. How efficient is it? Is all the data
shifted through the array every time I push something at the front and
remove it from the back, or is it organized more efficiently?

I don't know how Array is implemented.. I think matz (Ruby's author) has
chosen a datastructure with constant-time head/tail insert/removal.
Not sure though.


It would be nice with an O(x) chart of the most common operations:


my guess .. please correct me if im wrong

-------------------------------
push element O(1)
pop element O(1)
shift element O(?) I hope O(1)
unshift element O(?) I hope O(1)
insert element O(n)
remove element O(n)
...

 

[Mauricio Fernández]

my guess .. please correct me if im wrong

-------------------------------
push element O(1) amortized O(1), I think
pop element O(1)
shift element O(?) I hope O(1) O(1)
unshift element O(?) I hope O(1) O(n)
insert element O(n)
remove element O(n)
...

--
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

* gb notes that fdisk thinks his cdrom can store one terabyte
-- Seen on #Linux

 

[Carlos]

Thanks for your answer. I should have looked in the raa by myself. Just a
question regarding array as deque. How efficient is it? Is all the data
shifted through the array every time I push something at the front and
remove it from the back, or is it organized more efficiently?

If I'm not mistaken, #push (appends at the end), #pop (remove last) and
#shift (remove first) are efficient (#shift moves the pointer). #unshift
(insert at beginning) moves all elements.

But I can be mistaken.

 

[Mark Hubbart]

Thanks for your answer. I should have looked in the raa by myself.
Just a
question regarding array as deque. How efficient is it? Is all the data
shifted through the array every time I push something at the front and
remove it from the back, or is it organized more efficiently?

One of the great things about ruby is how easy it is to test things
like this

mark@imac% ruby
require 'profile'
def t_pop(ary) 5000.times{|n| ary.pop} end
def t_push(ary) 5000.times{|n| ary.push n} end
def t_shift(ary) 5000.times{|n| ary.shift} end
def t_unshift(ary) 5000.times{|n| ary.unshift n} end

a=[]
t_push a
t_pop a
t_unshift a
t_shift a
% cumulative self self total
time seconds seconds calls ms/call ms/call name
71.77 11.06 11.06 4 2765.00 3850.00 Integer#times
8.37 12.35 1.29 5000 0.26 0.26 Array#unshift
7.46 13.50 1.15 5000 0.23 0.23 Array#pop
7.40 14.64 1.14 5000 0.23 0.23 Array#push
4.93 15.40 0.76 5000 0.15 0.15 Array#shift
0.84 15.53 0.13 1 130.00 130.00
Profiler__.start_profile
0.06 15.54 0.01 1 10.00 3720.00 Object#t_shift
0.00 15.54 0.00 4 0.00 0.00
Module#method_added
0.00 15.54 0.00 1 0.00 3860.00 Object#t_pop
0.00 15.54 0.00 1 0.00 15410.00 #toplevel
0.00 15.54 0.00 1 0.00 4080.00 Object#t_unshift
0.00 15.54 0.00 1 0.00 3750.00 Object#t_push


Interpretation: it looks like unshift is slightly (~6%) slower than
pop. shift is barely faster than push. Still, they are all comparable
in speed.

I ran this test a few times, with similar results.

cheers,
--Mark

 

[Charles Comstock]

How much does it cost for an array access in the middle? Why does it cost
order(n) to remove the tail? Why doesn't it float backwards until it needs
memory ahead of it for instance? I'd be curious to now a bit more of about
this, as well as how the other datastructures are implemented.

Charlie

 

[Mauricio Fernández]

How much does it cost for an array access in the middle?

O(1), since an Array is implemented as a C array of VALUEs.

Why does it cost order(n) to remove the tail? Why doesn't it float
backwards until it needs memory ahead of it for instance?

Array uses internally an array of VALUEs, array->ptr.
When you unshift a VALUE, it has to be inserted at array->ptr[0]; all
elements must be shifted, hence O(n). You cannot just do array->ptr--
since you'd fall outside the malloc()ed area.

I'd be curious to now a bit more of about
this, as well as how the other datastructures are implemented.

I recommend you read the sources, they are very easy to follow. For
instance, to see how unshift is implemented, just look at array.c, and
scroll down to the method definition to find the associated C function.
rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
================

--
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

baz bat bamus batis bant.
-- James Troup