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
