Thanks for finding the typo. You are a friend if you have that book on
your bookshelf. :-) Version 0.3 of an implementation in C:
#define ASSERT(p,stmt) if(!(p)){stmt;}
#define SPARSE_VALUE 0
T sparse[M]; // sparse array of values
I4 sptr[M]; // sparse array of pointers
I4 stack[N], top=0;
int definedQ(I4 i){I4 j=sptr[i]; return 0<=j&&j<top&&i==stack[j];}
// is sparse[i] defined?
void put(I4 i, T val) // set sparse[i] to val
{
ASSERT(0<=i&&i<M, INDEX_ERROR);
sparse[i]=val;
if(!definedQ(i)){sptr[i]=top; stack[top++]=i;}
}
T get(I4 i) // sparse[i]
{
ASSERT(0<=i&&i<M, INDEX_ERROR);
return definedQ(i) ? sparse[i] : SPARSE_VALUE;
}
In my recent use of this idea for x i. y, the "pointer" or index is the
actual result, so I was able to dispense with both the separate array of
pointers and the stack.
On Fri, Mar 7, 2014 at 11:33 AM, Peter B. Kessler <
[email protected]> wrote:
> On 03/06/14 17:10, Roger Hui 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
>>
>
> s/Maintain a pointer *to* each initialized entry/Maintain a pointer *in*
> each initialized entry/
>
> he says after taking to book off his shelf and opening it to Exercise 2.12.
>
> Thanks for the reminder about that idea.
>
> The point is that you control the small dense table of back-pointers to
> initialized data in the otherwise uninitialized large array. Checking if
> an entry in the large sparse array holds initialized data reads a pointer
> (or index) from the large array, uses that to find if there's a
> back-pointer (or index) in the small dense array that refers to that entry.
> The data for an entry is in (or parallel to) the small dense array. You
> do need more space to hold the pointers and back-pointers, but only one
> pointer/back-pointer pair per initialized entry. If you treat the small
> dense array as a stack (e.g., with a top-of-stack marker) then you don't
> have to initialize the memory for the small dense array either.
>
> ... peter
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
