Probably not. It's not related to the problem of finding the minimum that I know of. It's the general problem of how you avoid initializing a large but sparse array. Recently, I did use the idea in a case of x i. y (you know, the problem I've been working on for 30 years :-).
Anyway, here it is: In the book *The Design and Analysis of Computer Algorithms*, by Aho, Hopcroft, and Ullman, Addison-Wesley, 1974, Exercise 2.12: Develop a technique to initialize an entry of a matrix to zero the first time it is accessed, thereby eliminating the O(‖V‖^2) time to initialize an adjacency matrix. [Hint: Maintain a pointer to each initialized entry to a back pointer on a stack. Each time an entry is accessed, verify that the contents are not random by making sure the pointer in that entry points to the active region on the stack and that the back pointer points to the entry.] The hint is part of the statement of the exercise in the book and gives away the game. The technique is sufficiently well-known that it is the top search result (of 3,800,000) on Googling "Exercise 2.12 sparse"<http://www.google.ca/search?q=Exercise+2.12+sparse> . On Thu, Mar 6, 2014 at 4:55 PM, Raul Miller <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
