Sorted list?


#1

Hi all.

Is somewhere effective realization of “sorted list” container?
(“effective” here means “right algorithm”, not “written in C”)

Thanks.

V.


#2

Please example more. Do you mean:

[ 2, 1, 3, 0 ].sort #=> [ 0, 1, 2, 3 ]

T.


#3

From: removed_email_address@domain.invalid [mailto:removed_email_address@domain.invalid]
Sent: Sunday, June 04, 2006 4:43 AM

Please example more. Do you mean:

[ 2, 1, 3, 0 ].sort #=> [ 0, 1, 2, 3 ]

Nope. I’ve meant:

lst = SortedList.new(3, 1, 4, 0)

lst.to_a #=> [ 0, 1, 3, 4 ]

lst.insert(2)
lst.to_a #=> [ 0, 1, 2, 3, 4 ]

T.

V.


#4

On Jun 3, 2006, at 9:49 PM, Victor S. wrote:

lst.to_a #=> [ 0, 1, 3, 4 ]

lst.insert(2)
lst.to_a #=> [ 0, 1, 2, 3, 4 ]

T.

V.

I was going to suggest http://raa.ruby-lang.org/project/ruby-rbtree/
but it is written in C.

However, this is as far as I can tell pure ruby:
http://raa.ruby-lang.org/project/ruby-treap/


#5

From: Logan C. [mailto:removed_email_address@domain.invalid]
Sent: Sunday, June 04, 2006 5:10 AM

lst = SortedList.new(3, 1, 4, 0)

I was going to suggest http://raa.ruby-lang.org/project/ruby-rbtree/
but it is written in C.

However, this is as far as I can tell pure ruby:
http://raa.ruby-lang.org/project/ruby-treap/

Thanks, I think it would be sufficient.
BTW, I’m slightly surprized such a “fundamental” (?) thing is neither
part
of core, nor stdlib, nor some “common” extension.

V.


#6

On Jun 3, 2006, at 9:15 PM, Victor S. wrote:

BTW, I’m slightly surprized such a “fundamental” (?) thing is
neither part
of core, nor stdlib, nor some “common” extension.

Oh but it is… :wink:

require “set”
=> true

ordered = SortedSet.new([3, 1, 4, 0])
=> #<SortedSet: {0, 1, 3, 4}>

ordered.add(2)
=> #<SortedSet: {0, 1, 2, 3, 4}>

ordered.to_a
=> [0, 1, 2, 3, 4]

James Edward G. II


#7

On Jun 3, 2006, at 11:55 PM, James Edward G. II wrote:

ordered = SortedSet.new([3, 1, 4, 0])
sort of

This won’t work if you want multiple occurrences of items.

But thanks for pointing out SortedSet, I wasn’t aware of it before.

Gary W.


#8

From: James Edward G. II [mailto:removed_email_address@domain.invalid]
Sent: Sunday, June 04, 2006 6:55 AM

ordered = SortedSet.new([3, 1, 4, 0])
=> #<SortedSet: {0, 1, 3, 4}>

ordered.add(2)
=> #<SortedSet: {0, 1, 2, 3, 4}>

ordered.to_a
=> [0, 1, 2, 3, 4]

Oooops. I’m an idiot.

Thanks James!

James Edward G. II

Victor.


#9

removed_email_address@domain.invalid wrote:

Victor wrote:

Nope. I’ve meant:

Ah okay. See Facets’ Dictionary class.

http://facets/.rubyforge.org

Oops. My bad that’s like an ordered hash, not a list.

I should point out though that it is much more efficient to sort
manually when you need it then to have the elements inserted in the
ordered positon everytime time one is added.

T.


#10

From: removed_email_address@domain.invalid [mailto:removed_email_address@domain.invalid]
Sent: Sunday, June 04, 2006 7:48 AM

I should point out though that it is much more efficient to sort
manually when you need it then to have the elements inserted in the
ordered positon everytime time one is added.

It is very questionnable statement.

Storing values I need to have sortered into appropriate structure
(rb-tree,
for ex.) can be much more effective, than to resort values array.

Generally, all depends on many parameters, like insertions frequency,
array
size, comparison cost and so on.

T.

V.


#11

Victor S. wrote:

Oops. My bad that’s like an ordered hash, not a list.
Generally, all depends on many parameters, like insertions frequency, array
size, comparison cost and so on.

That’s true. I was stupidly thinking in contrast to a complete #sort
after each insert. My bad.

T.


#12

On Jun 3, 2006, at 11:52 PM, Victor S. wrote:

Oops. My bad that’s like an ordered hash, not a list.

I should point out though that it is much more efficient to sort
manually when you need it then to have the elements inserted in the
ordered positon everytime time one is added.

It is very questionnable statement.

I agree. What about heaps?

James Edward G. II


#13

On Sun, 4 Jun 2006, Victor S. wrote:

Hi all.

Is somewhere effective realization of “sorted list” container?
(“effective” here means “right algorithm”, not “written in C”)

Thanks.

V.

if you can’t use C then you rule out every single one of ruby’s
built-ins :wink:

rbtree is very good - i’ve been using it for years - i’d highly
reccomend
compiling it up and running with it

 harp:~ > cat a.rb
 require 'rbtree'
 class SortedList
   def initialize *elems
     @rbt = RBTree.new
     insert *elems
   end
   def insert *elems
     elems.each{|e| @rbt[e] = e}
     self
   end
   alias_method "<<", "insert"
   def to_a() @rbt.values end
   def inspect() to_a.inspect end
   class << self
     alias_method "[]", "new"
   end
 end

 sl = SortedList[ 0, 3, 1, 4, 2 ]
 p sl

 sl << -1 << 5
 p sl


 harp:~ > ruby a.rb
 [0, 1, 2, 3, 4]
 [-1, 0, 1, 2, 3, 4, 5]

on a side note - rbtree is amazingly fast.

regards.

-a


#14

Victor wrote:

Nope. I’ve meant:

Ah okay. See Facets’ Dictionary class.

http://facets/.rubyforge.org

T.