Regardless of whether "sparse" is present or not, you need to scan "dense" to find the value. No?
Thanks, -- Raul On Thu, Mar 6, 2014 at 8:37 PM, Roger Hui <rogerhui.can...@gmail.com> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
