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=
:
>> > 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 usi=
ng
>> > the object as an array.
>>
>> I'm curious how you manage to keep the data structure ordered and keep
>> access time O(1). =A0It 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 so=
rt,
> 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

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/