And how do you find that value? With the scheme I can say tab[i], after verifying that i=stack[ptr[i]]. (Both tab and ptr are size M arrays.)
On Thu, Mar 6, 2014 at 5:30 PM, Raul Miller <rauldmil...@gmail.com> wrote: > 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 <rogerhui.can...@gmail.com> > 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 <rauldmil...@gmail.com> > 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 <rogerhui.can...@gmail.com> > >> 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 <yikelu.h...@gmail.com> > 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 <rogerhui.can...@gmail.com > > > >> >> 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 <yikelu.h...@gmail.com> > >> wrote: > >> >> > > >> >> > > Using a dictionary is another way. > >> >> > > > >> >> > > > >> >> > > On Thu, Mar 6, 2014 at 3:30 PM, Roger Hui < > >> rogerhui.can...@gmail.com> > >> >> > > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
