It seems to me that you could accomplish the same thing without the "sparse" memory. The numeric values are present in "dense". Am I missing something?
Thanks, -- Raul On Thu, Mar 6, 2014 at 8:10 PM, Roger Hui <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
