5 ms·

Initializing an array in constant time, My sneaky solution: getting and setting seem very simple - if you know the starting memory address and the size of an e

by user24 16y ago

Initializing an array in constant time, My sneaky solution: getting and setting seem very simple - if you know the starting memory address and the size of an element (assuming constantly sized elements), you can implement get(i) as "return the value at memory location: start + (i * size) and similarly for set. So as the question suggests, it's the initialising that's the problem. My sneaky solution is not to actually initialise the array. Instead, init(N,d) performs as follows: Store 'd' in some memory location outside of the array. Set(i,v) finds memory location: start + (i * size) and sets v and a checkdigit. Get(i) retrieves the value at memory location start + (i * size) and if the checkdigit isn't present or doesn't match, returns the default as set in init, else returns the value. I think (think) each of those is O(1), but I'm not sure if that's the expected solution. edit: reading up, I think this won't work as the uninitialised array will be filled with random data and so might 'happen' to pass the checkdigit test :(

anatoly 16y ago
The hard thing about this problem is to neutralize the "random data" that can pass whatever error-checking you want to enforce. I don't remember all the details but the trick is (substantial hint) SPOILER SPOILER SPOILER to use indirection. Let the data at location i in the array not be the actual value but an index to another array that we continue to fill as we get new set() calls to previously unvisited places. When someone says set(i,v), we look at location i in the first array and see an index into the second. Suppose we can tell if the index is genuine (previously put there by us) or random junk; then everything's easy - when it's junk, allocate a new cell in the second array for the value and update the index. get() with default value also becomes easy. So the problem remains, how to tell random junk from a genuine index we stored before, and I've remembered the rest by now but I'd better stop here.
hristov 16y ago
You are right, this won't work, you do not know what is in the check digit. There is actually a very clever way to do this, which involves using pointers that go back and forth to avoid the random value problem. I do not have time to explain it, (and since it involves pointers, it would be pretty hard to explain without a white board) but I encourage anyone interested to look into the Knuth book and check it out.
- user24 16y ago
  yeah I was reading up on a solution which sounds pretty much like what you're talking about. Trouble with these things is that if you think you've solved it, there's no way to find out without spoiling it if you haven't. (apart from thinking about it longer and harder)
- deleted 16y ago
  [deleted]

by user24 16y ago

anatoly 16y ago

The hard thing about this problem is to neutralize the "random data" that can pass whatever error-checking you want to enforce. I don't remember all the details but the trick is (substantial hint) SPOILER SPOILER SPOILER to use indirection. Let the data at location i in the array not be the actual value but an index to another array that we continue to fill as we get new set() calls to previously unvisited places. When someone says set(i,v), we look at location i in the first array and see an index into the second. Suppose we can tell if the index is genuine (previously put there by us) or random junk; then everything's easy - when it's junk, allocate a new cell in the second array for the value and update the index. get() with default value also becomes easy. So the problem remains, how to tell random junk from a genuine index we stored before, and I've remembered the rest by now but I'd better stop here.

hristov 16y ago

You are right, this won't work, you do not know what is in the check digit. There is actually a very clever way to do this, which involves using pointers that go back and forth to avoid the random value problem. I do not have time to explain it, (and since it involves pointers, it would be pretty hard to explain without a white board) but I encourage anyone interested to look into the Knuth book and check it out.

user24 16y ago
yeah I was reading up on a solution which sounds pretty much like what you're talking about. Trouble with these things is that if you think you've solved it, there's no way to find out without spoiling it if you haven't. (apart from thinking about it longer and harder)
deleted 16y ago
[deleted]