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
