Hi all.
Is somewhere effective realization of “sorted list” container?
(“effective” here means “right algorithm”, not “written in C”)
Thanks.
V.
Please example more. Do you mean:
[ 2, 1, 3, 0 ].sort #=> [ 0, 1, 2, 3 ]
T.
From: [email protected] [mailto:[email protected]]
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.
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/
From: Logan C. [mailto:[email protected]]
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.
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… 
require “set”
=> trueordered = 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
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.
From: James Edward G. II [mailto:[email protected]]
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.
[email protected] wrote:
Victor wrote:
Nope. I’ve meant:
Ah okay. See Facets’ Dictionary class.
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.
From: [email protected] [mailto:[email protected]]
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.
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.
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
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
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
Victor wrote:
Nope. I’ve meant:
Ah okay. See Facets’ Dictionary class.
T.