No, you put (i,value) into sparse, sparse[i]=value;, then put ptr[i]=top;, then
put stack[top]=i;, then increment top. This assumes you don't assign
different values into sparse[i] at different times. The modifications are
obvious if you don't want to assume that.
Completely untested:
#define ASSERT(p,stmt) if(!(p)){stmt;}
T spval[M]; // sparse array of values
I4 spptr[M]; // sparse array of pointers
I4 stack[n], top=0;
void put(I4 i, T val) // set sparse[i] to val
{
ASSERT(0<=i&&i<n, INDEX_ERROR);
spval[i]=val;
spptr[i]=top;
stack[top++]=i;
}
T get(I4 i) // sparse[i]
{
ASSERT(0<=i&&i<n, INDEX_ERROR);
j=spptr[i];
ASSERT(0<=j&&j<top&&i==stack[j], VALUE_ERROR);
return spval[i];
}
int definedQ(I4 i) // is sparse[i] defined?
{
return 0<i&&i<n&&(j=spptr[i],0<=j&&j<top&&i==stack[j]);
}
On Thu, Mar 6, 2014 at 6:01 PM, Raul Miller <[email protected]> wrote:
> 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 <[email protected]>
> 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 <[email protected]>
> 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 <[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
> >>
> > ----------------------------------------------------------------------
> > 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
