Is this still going to be faster than the test and branch loop? Thanks,
-- Raul On Thu, Mar 6, 2014 at 7: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
