From: Robert Klemme Date: 2011-07-18T16:57:59+09:00 Subject: Re: does OrderedHash exist? On Sat, Jul 16, 2011 at 6:10 PM, Josh Cheek wrote: > On Sat, Jul 16, 2011 at 7:32 AM, Robert Klemme > wrote: > >> On Sat, Jul 16, 2011 at 9:34 AM, Oren Shani 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? 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 -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/