wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Large Array Initialization
        
(Message started by: Dudidu on Dec 17^th, 2003, 11:36pm)

Title: Large Array Initialization
Post by Dudidu on Dec 17^th, 2003, 11:36pm

Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time:
* Init - Initializes the data structure to empty.
* Set(i, x) - Sets item x at index i in the data structure.
* Get(i) - Gets the item stored in index i (or 'empty' if nothing is there).
Remark: the data structure should use O(n) space.

Title: Re: Large Array Initialization
Post by Eigenray on Dec 18^th, 2003, 12:03am

I think this works, using 3n space, plus a counter:[hide]
We have three (0-indexed) arrays, A,B,C, and a counter.
The counter is how many elements have been set. A contains the data. For k<count, B[k] contains the index of the k-th element to be set. If A[k] has been set, C[k] tells when; otherwise, C[k] is undefined.

Init():
counter := 0

boolean IsSet(int k):
if (C[k] < counter) and (B[C[k]==k) return TRUE
else return FALSE

Set(i, x):
A[i]=x
if not IsSet(i)
B[count] := i
C[i] := count
count := count+1

Get(i):
if IsSet(i) return A[i]
else return 'empty'[/hide]

Title: Re: Large Array Initialization
Post by Dudidu on Dec 18^th, 2003, 12:20am

on 12/18/03 at 00:03:04, Eigenray wrote:

I think this works...

Eigenray hi,
I have a question/problem about your solution - array C hasn't been initialized (obviously), so it can hold any "junk" values, so checking 'C[k] < counter' in IsSet(...) (for example when Set(...) or Get(...) are called in the first time) might return true and then checking 'B[C[k]==k' might rise an 'out of bounds' exception (think of the case that C[k] is -1)...
Do I miss something ?

Title: Re: Large Array Initialization
Post by towr on Dec 18^th, 2003, 12:47am

Why not just use a normal array, don't initialize it, and make it the users problem if he retrieves the value from an unset array-cell.

Title: Re: Large Array Initialization
Post by Dudidu on Dec 18^th, 2003, 1:08am

on 12/18/03 at 00:47:27, towr wrote:

Why not just use a normal array, don't initialize it, and make it the users problem if he retrieves the value from an unset array-cell.

towr hi,
Two answers (I'm not sure that any of them will convince you):
* The obivious one... because this is the question ! (and without it there won't be a question).
* The reasonable one... because we want to give the user a more robust data structure that won't cause the program to crash because of user mistakes, which could have been prevented if the array had been initialized.

Title: Re: Large Array Initialization
Post by Eigenray on Dec 18^th, 2003, 1:51am

on 12/18/03 at 00:20:04, Dudidu wrote:

No, you're right. I was just leaving all the bounds checking out for simplicity, but I guess they should be included. Although if you define C to be an uint[], it shouldn't matter. But as long as (0<=)C[k]<counter, you know B[C[k] has been initialized, so the only way B[C[k]=k is if A[k] was the C[k]-th element to be initialized.

on 12/18/03 at 00:47:27, towr wrote:

Why not just use a normal array, don't initialize it, and make it the users problem if he retrieves the value from an unset array-cell.

There might be some applications where O(n) space is acceptable, but you want the running time to be o(n). For example, say you want to represent a set of m elements from {1,2,...,n}. If you use an array of length n, that allows for O(1) insertion and membership checks. If m is small, the bottleneck could easily be the O(n) initialization.

Title: Re: Large Array Initialization
Post by Dudidu on Dec 18^th, 2003, 2:14am

on 12/18/03 at 01:51:29, Eigenray wrote:

I was just leaving all the bounds checking out for simplicity...

Well done, your answer is correct !
Anyway, now I'm thinking whether one can improve the "space consumption" (i.e. better then the suggested(3n+log(n)))?

Title: Re: Large Array Initialization
Post by James Fingas on Dec 18^th, 2003, 5:00am

on 12/18/03 at 02:14:31, Dudidu wrote:

Anyway, now I'm thinking whether one can improve the "space consumption" (i.e. better then the suggested(3n+log(n)))?

I've been thinking about this, and I don't think you can (not using this fundamental method anyways) You must have an array that indexes each i into the numbers 1..k, and you must have a cross-index back to the i's, and you must also have a value for each i that is set. If the entire array is set, then this takes 3n elements.

Also note that two of these arrays (the index into 1..k and the cross-index back) must have elements of size log(n). Therefore, the usage is n + 2nlog(n) + log(n) (technically).