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
