Author |
Topic: Large Array Initialization (Read 3051 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?
|
|
|
|