Author |
Topic: Large Array Initialization (Read 3039 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Large Array Initialization
« on: Dec 17th, 2003, 11:36pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Dec 17th, 2003, 11:37pm by Dudidu » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
|
Re: Large Array Initialization
« Reply #1 on: Dec 18th, 2003, 12:03am » |
Quote Modify
|
I think this works, using 3n space, plus a counter:
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'
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Large Array Initialization
« Reply #2 on: Dec 18th, 2003, 12:20am » |
Quote Modify
|
on Dec 18th, 2003, 12:03am, Eigenray wrote: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 ?
|
| « Last Edit: Dec 18th, 2003, 12:21am by Dudidu » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Large Array Initialization
« Reply #3 on: Dec 18th, 2003, 12:47am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Large Array Initialization
« Reply #4 on: Dec 18th, 2003, 1:08am » |
Quote Modify
|
on Dec 18th, 2003, 12:47am, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Large Array Initialization
« Reply #5 on: Dec 18th, 2003, 1:51am » |
Quote Modify
|
on Dec 18th, 2003, 12:20am, Dudidu wrote: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 ? |
|
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 Dec 18th, 2003, 12:47am, 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.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Large Array Initialization
« Reply #6 on: Dec 18th, 2003, 2:14am » |
Quote Modify
|
on Dec 18th, 2003, 1:51am, 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)))?
|
| « Last Edit: Dec 18th, 2003, 2:15am by Dudidu » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Large Array Initialization
« Reply #7 on: Dec 18th, 2003, 5:00am » |
Quote Modify
|
on Dec 18th, 2003, 2:14am, 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).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print