Forum: Ruby Sorted list?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
2c7c807a1df0c76a8fc823c709b501a9?d=identicon&s=25 Victor Shepelev (Guest)
on 2006-06-04 03:34
(Received via mailing list)
Hi all.

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

Thanks.

V.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 unknown (Guest)
on 2006-06-04 03:43
(Received via mailing list)
Please example more. Do you mean:

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

T.
2c7c807a1df0c76a8fc823c709b501a9?d=identicon&s=25 Victor Shepelev (Guest)
on 2006-06-04 03:50
(Received via mailing list)
From: transfire@gmail.com [mailto:transfire@gmail.com]
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.
E34b5cae57e0dd170114dba444e37852?d=identicon&s=25 Logan Capaldo (Guest)
on 2006-06-04 04:12
(Received via mailing list)
On Jun 3, 2006, at 9:49 PM, Victor Shepelev 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/
2c7c807a1df0c76a8fc823c709b501a9?d=identicon&s=25 Victor Shepelev (Guest)
on 2006-06-04 04:18
(Received via mailing list)
From: Logan Capaldo [mailto:logancapaldo@gmail.com]
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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-06-04 05:58
(Received via mailing list)
On Jun 3, 2006, at 9:15 PM, Victor Shepelev 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...  ;)

 >> 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 Gray II
2c7c807a1df0c76a8fc823c709b501a9?d=identicon&s=25 Victor Shepelev (Guest)
on 2006-06-04 06:04
(Received via mailing list)
From: James Edward Gray II [mailto:james@grayproductions.net]
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 Gray II

Victor.
E7559e558ececa67c40f452483b9ac8c?d=identicon&s=25 unknown (Guest)
on 2006-06-04 06:07
(Received via mailing list)
On Jun 3, 2006, at 11:55 PM, James Edward Gray 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 Wright
45196398e9685000d195ec626d477f0e?d=identicon&s=25 unknown (Guest)
on 2006-06-04 06:44
(Received via mailing list)
Victor wrote:
> Nope. I've meant:

Ah okay. See Facets'  Dictionary class.

  http://facets/.rubyforge.org

T.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 unknown (Guest)
on 2006-06-04 06:50
(Received via mailing list)
transf...@gmail.com 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.
2c7c807a1df0c76a8fc823c709b501a9?d=identicon&s=25 Victor Shepelev (Guest)
on 2006-06-04 06:53
(Received via mailing list)
From: transfire@gmail.com [mailto:transfire@gmail.com]
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.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 unknown (Guest)
on 2006-06-04 12:48
(Received via mailing list)
Victor Shepelev 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.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-06-04 17:13
(Received via mailing list)
On Jun 3, 2006, at 11:52 PM, Victor Shepelev 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 Gray II
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2006-06-04 17:29
(Received via mailing list)
On Sun, 4 Jun 2006, Victor Shepelev 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 ;-)

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
This topic is locked and can not be replied to.