Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?
I would prefer to call ordered hash an OrderedHash, rather than Hash.
I saw that there existed ActiveSupport::OrderedHash in Rails, but its
API page recently disappeared...
I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.
Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?
After a long court battle, the ruby standard library has recently been
procured by Bloomberg News under a Freedom of Information Request.
I would prefer to call ordered hash an OrderedHash, rather than Hash.
Ruby allows you to call a class anything you want.
Hello,
i know that in Ruby 1.9 Hash is ordered, but it seems to be a
controversial solution.
Does there exist by any chance any standard library with an OrderedHash
class?
I would prefer to call ordered hash an OrderedHash, rather than Hash.
I saw that there existed ActiveSupport::OrderedHash in Rails, but its
API page recently disappeared...
Yes, it has been marked with the #:nodoc: rdoc tag(?) so it is now omitted
from the documentation. If I were you I'd go ask the guys in the "Ruby on
Rails: Core" mailing-list/group ( Redirecting to Google Groups) if you can expect
the class to stick around (and/or why it's been nodoc-ed). After all, since
your project is a rails one you're right to look to leverage this
ActiveSupport class.
I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.
Or it is named correctly and you can just assume a Hash isn't ordered (even
if it is for a specific version) and code accordingly. Or just copy or fork
ActiveSupport::OrderedHash for your own needs in your own project:
···
On Thu, Jul 14, 2011 at 4:03 PM, Alexey Muranov < muranov@math.univ-toulouse.fr> wrote:
I created a class called, HashArray which implements a pretty
straightforward Hash with order object. Content can be added, deleted,
reordered, etc, and then there is the as_array method that enables using
the object as an array.
I can send you the source if you want but I'd appreciate it if you (or
anyone else that reads this) could help me turn it into a gem...
If I were you I'd go ask the guys in the "Ruby
on
Rails: Core" mailing-list/group ( Redirecting to Google Groups) if you can
expect
the class to stick around (and/or why it's been nodoc-ed). After all,
since
your project is a rails one you're right to look to leverage this
ActiveSupport class.
Thanks Gifford, i didn't know about this mailing list.
I think by the way that the current ordered implementation of Hash is
nice, but should have been called OrderedHash, so that in future
versions Hash could be made unordered again.
Or it is named correctly and you can just assume a Hash isn't ordered
(even
if it is for a specific version) and code accordingly.
Yes, my "problem" is exactly that i did not want to assume Hash to be
ordered.
I'm curious how you manage to keep the data structure ordered and keep
access time O(1). It surely is O(1) since it's called _Hash_Array,
isn't it?
Kind regards
robert
···
On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani <orenshani7@gmail.com> wrote:
I created a class called, HashArray which implements a pretty
straightforward Hash with order object. Content can be added, deleted,
reordered, etc, and then there is the as_array method that enables using
the object as an array.
Insertion ordered is part of Ruby spec now. It is very unlikely to
change b/c a lot of people will be very pissed.
That said, there are other types of order. Consider hashery gem with
it's Dictionary class (which is an evolution of the orderedhash gem).
···
On Jul 14, 6:36 pm, Alexey Muranov <mura...@math.univ-toulouse.fr> wrote:
Kendall Gifford wrote in post #1010836:
> If I were you I'd go ask the guys in the "Ruby
> on
> Rails: Core" mailing-list/group (
>Redirecting to Google Groups) if you can
> expect
> the class to stick around (and/or why it's been nodoc-ed). After all,
> since
> your project is a rails one you're right to look to leverage this
> ActiveSupport class.
Thanks Gifford, i didn't know about this mailing list.
>> I think by the way that the current ordered implementation of Hash is
>> nice, but should have been called OrderedHash, so that in future
>> versions Hash could be made unordered again.
> Or it is named correctly and you can just assume a Hash isn't ordered
> (even
> if it is for a specific version) and code accordingly.
Yes, my "problem" is exactly that i did not want to assume Hash to be
ordered.
Not speaking for the OP, but the naive solution by keeping book of key
ordering in an Array for ordered access (mostly iteration) and going
straight for a plain Hash for storage and unordered access already
fulfills that. Non-trivial insertion would suffer, because it has to
reorganize the keys.
Regards,
Florian
···
On Jul 16, 2011, at 2:32 PM, Robert Klemme wrote:
On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani <orenshani7@gmail.com> wrote:
I created a class called, HashArray which implements a pretty
straightforward Hash with order object. Content can be added, deleted,
reordered, etc, and then there is the as_array method that enables using
the object as an array.
I'm curious how you manage to keep the data structure ordered and keep
access time O(1). It surely is O(1) since it's called _Hash_Array,
isn't it?
You don't necessarily have to keep it ordered the whole time. Order only
matters when you try to access it. So you could keep all the hash
properties, then as soon as someone tries to do something ordered, build a
heap O(n) and then iterate as you remove the minimum. Essentially heap sort,
but yielding each object as you remove it.
If you track whether it is sorted, then the first iteration is O(n lg n) and
the rest after that are O(n). Of course, if you keep adding lots of keys and
iterating frequently, then iteration performance would suffer. Seems like in
cases like that, you have to make a trade off somewhere
···
On Sat, Jul 16, 2011 at 7:32 AM, Robert Klemme <shortcutter@googlemail.com>wrote:
On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani <orenshani7@gmail.com> wrote:
> I created a class called, HashArray which implements a pretty
> straightforward Hash with order object. Content can be added, deleted,
> reordered, etc, and then there is the as_array method that enables using
> the object as an array.
I'm curious how you manage to keep the data structure ordered and keep
access time O(1). It surely is O(1) since it's called _Hash_Array,
isn't it?
> I created a class called, HashArray which implements a pretty
> straightforward Hash with order object. Content can be added, deleted,
> reordered, etc, and then there is the as_array method that enables using
> the object as an array.
I'm curious how you manage to keep the data structure ordered and keep
access time O(1). It surely is O(1) since it's called _Hash_Array,
isn't it?
Well, first of all I'd rather hear from Oren what he really did.
You don't necessarily have to keep it ordered the whole time. Order only
matters when you try to access it. So you could keep all the hash
properties, then as soon as someone tries to do something ordered, build a
heap O(n) and then iterate as you remove the minimum. Essentially heap sort,
but yielding each object as you remove it.
If you track whether it is sorted, then the first iteration is O(n lg n) and
the rest after that are O(n). Of course, if you keep adding lots of keys and
iterating frequently, then iteration performance would suffer. Seems like in
cases like that, you have to make a trade off somewhere
The approach you describe is best suited for usage scenarios where
there are two phases: 1. manipulation (insert, delete) 2. usage
(ordered iteration). But for that an ordinary Hash is sufficient
which then is sorted once.
If ordered accesses are mixed with inserts and deletions then probably
a data structure with permanent ordering is better suited. You
typically can't get both at the same time - updates with O(1) and
continuous ordering.
Kind regards
robert
···
On Sat, Jul 16, 2011 at 6:10 PM, Josh Cheek <josh.cheek@gmail.com> wrote:
On Sat, Jul 16, 2011 at 7:32 AM, Robert Klemme > <shortcutter@googlemail.com>wrote:
On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani <orenshani7@gmail.com> wrote:
