Arrgh! The index i is bounded by M, not by n. Thus:
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<M, INDEX_ERROR);
spval[i]=val;
spptr[i]=top;
stack[top++]=i;
}
T get(I4 i) // sparse[i]
{
ASSERT(0<=i&&i<M, INDEX_ERROR);
j=spptr[i];
ASSERT(0<=j&&j<top&&i==stack[j], INDEX_ERROR);
return spval[i];
}
int definedQ(I4 i) // is sparse[i] defined?
{
return 0<i&&i<M&&(j=spptr[i],0<=j&&j<top&&i==stack[j]);
}
On Thu, Mar 6, 2014 at 7:47 PM, Roger Hui <[email protected]> wrote:
> 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
