You are not guaranteed sortedness, but nobody promised that it'd be sorted.
On Thu, Mar 6, 2014 at 5:42 PM, Yike Lu <[email protected]> wrote: > Problem with the hash table is how do you guarantee sortedness when you > spit the result back out? > On Mar 6, 2014 6:49 PM, "Roger Hui" <[email protected]> wrote: > > > Well, if you use a hash table it'd be O(1) expected time to read and > write. > > The method I know is O(1) worst case time to read and write. > > > > > > On Thu, Mar 6, 2014 at 2:54 PM, Yike Lu <[email protected]> wrote: > > > > > Hmm, maybe not. It has to basically be able to insert ordered in > constant > > > time. Everything I remember seems to be log time for one or the other. > > > > > > I'm starting to lean towards a multi-pass / multi-array solution. > > > > > > > > > On Thu, Mar 6, 2014 at 4:42 PM, Roger Hui <[email protected]> > > > wrote: > > > > > > > The method I know offers O(1) time to read and write. Can your > > > dictionary > > > > do the same? (And I think we are talking about _how_ you implement a > > > > dictionary.) > > > > > > > > > > > > > > > > > > > > On Thu, Mar 6, 2014 at 2:34 PM, Yike Lu <[email protected]> > wrote: > > > > > > > > > Using a dictionary is another way. > > > > > > > > > > > > > > > On Thu, Mar 6, 2014 at 3:30 PM, Roger Hui < > [email protected] > > > > > > > > wrote: > > > > > > > > > > > Yes, that's the cost. The trick is to avoid initializing count > > > > > altogether, > > > > > > because for this subproblem M is much greater than n. The answer > > is > > > > > > algorithmic and not a matter of using this or that C operation. > > > > > > > > > > > > Recently I had occasion to use the trick for M=65536 and n about > > > 5000. > > > > > As > > > > > > originally posed, I think the intention was that M would be > > zillions. > > > > > > > > > > > > > ---------------------------------------------------------------------- > > > > > For information about J forums see > > http://www.jsoftware.com/forums.htm > > > > > > > > > > ---------------------------------------------------------------------- > > > > For information about J forums see > http://www.jsoftware.com/forums.htm > > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
