array initialization in O(1)

Thats impossible.
It will be possible if the processor is 100*sizeof(int) bit.
But unfortunately - as far as i know we have only till 128 bit processors.

...if it is an array of 100 pointers pointing all to the same location... :-)

Greetings,
    </ntr> :)

hi Neutron

nice thinking!!!!

"we have only till 128 bit processors. "

completely wrong

cellular computers
artificial neuronal networks
some more standard parallel machines
examples :
http://www.freenetpages.co.uk/hp/tgclarkson/pram-data.pdf
http://www.cs.nmsu.edu/~pfeiffer/classes/573/sem/s03/presentations/STARAN2.ppt

plus :
DIVA wideWord processor
"The combination of the execution control unit and
WideWord datapath is regarded as the WideWord
Processor. This component enables superword-level
parallelism [11] on wide words of 256 bits[...]"
http://www.isi.edu/~draper/papers/esscirc02.pdf
http://www.globaltechnoscan.com/8thAug-14thAug02/memory.htm

and
the Ax36 Video DSP uses a VLIW of 256 bits
http://www.omdi.com/download/competitive_analysis_Oct99.pdf

and
I avoided to mention the existing 256 bits graphics chips :D

VGR
>>we have only till 128 bit processors. "
>>completely wrong
Thaks for that update!!!

But even if we have 256 bit processor, the question still remains impossible.

There is additional discussion on this very same problem here:
http://www-tcsn.experts-exchange.com/Programming/Programming_Languages/C/Q_20739224.html

#define array_size 100
int array[array_size];

int back[array_size];
int fwd[array_size];
int top= -1;
int initvalue = 1;

initialize_array(int value){
  top = -1;  /* mark array as all initvalue */
  initvalue = value;
}

insert_into_array(int index, int value){
  if( index < 0 || index >= array_size ){
    error("index out of bounds");
  }
  if( 0 <= back[index] && back[index] <= top && fwd[back[index]] == index ){
    /* array[index] contains valid data */
  }else{
    /* array[index] is empty, mark index as valid */
    top+=1;
    fwd[top]=index;
    back[index]=top;
  }
  array[index]=value;
}

int read_from_array(int index){
  if( index < 0 || index >= array_size ){
    error("index out of bounds");
  }
  if( 0 <= back[index] && back[index] < top && fwd[back[index]] == index ){
    /* array[index] contains valid data */
    return(array[index]);
  }else{
    return initvalue;
  }
}

grg99 said it all

grg99 says:
> One sneaky way that might SEEM to be O(1) is to declare the array as a static global array.
> static variables are by C's definition, initialized to zero.
>
> But this is done by the startup code in C0.OBJ, and it may be done quickly, but it's still most likely done by
> a loop, so it's going to be O(n).   It's just that it's a HIDDEN loop, but it's still most likely O(n).

You could try a static global array with explicit iniitialization.  That would get initialized at compile
time, rather than load time (note that one of the array elements is not zero):

static int a[100] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 200,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

>You could try a static global array with explicit iniitialization.  That would get initialized at compile
>time, rather than load time (note that one of the array elements is not zero):

I forgot that case!

It souinds "free", but actually it's worse than most options, as then the zeroes have to be read from disk, which is going to be a BIGFACTOR * O(n) process,
at least 1,000 times slower than having the CPU zero out memory.  But it's "invisible" as you don't need an explicit loop
in your code.

No free lunch here either.


Sorry,

grg99

> It sounds "free", but actually it's worse than most options, as then the zeroes have to be
> read from disk, which is going to be a BIGFACTOR * O(n) process, at least 1,000 times slower
> than having the CPU zero out memory.  

Actually for such a small program, the extra 400 bytes will likely land in the same 4k page as
the rest of the program (or its data at least).  It really doesn't take any longer to read 400
bytes from a file than to read 4 bytes, because the data is read from the file in chunks that
are either sector sized, cluster sized, or VM page sized (depending on the OS).  So you only
have to worry if the initialized data spills into an additional "chunk" (which probably resides
in the drive's 2MB-8MB read-ahead cache anyway).

But even so, all our suggestions just push the work further back in the timeline.  It still has
to be done some time.  Although doing the work at compile time amortizes its impact across
all future runs.

>Actually for such a small program, the extra 400 bytes will likely land in the same 4k page as
>the rest of the program (or its data at least).

Ah yes, the cat and rat infinite factory.  You can breed an infinite number of cats,
as there's always at least one rat around, and the cats can eat that rat.
If the rats go hungry, just chop up some cats and feed them to the rats.

Well, not quite, you're just hoping the rat won't miss having its tail eaten.  But what about the next cat?

It's still O(n) times a BIG factor.  My hard disk can read zeroes at about 5MB/sec plus about 20msec to get started.  My CPU can
zero memory about 500 times as fast as that, with zero initial delay.  So we're talking about O(n) * 500.  
But you're right, sometimes you'll get the first few cats fed for free.

Regards,

grg99

This is not the solution to your problem, but maybe you can still use it somehow:   :-)

-you have a zero-based integer array
int[] numbers

-use element numbers[0] as index multiplicator when accessing array-elements with index>0
 This means that instead of:
      number[index]       to access element at position index>0
you would use
      number[number[0] * index]
or maybe
      number[number[0] & index]

- if you use * operator then assign   number[0]=1
- if you use & bitwise-AND operator then assign number[0]=-1

- when you need to set all values to zero, just assign    number[0]=0
  As a result, all lookups
     number[number[0] * index] == number[0 * index] == number[0] == 0
 also
     number[number[0] & index] == number[0 & index] == number[0] == 0

Convenient, but still useless :-)
...useless because when you wish to assign a non-null value to some array-element, you still have to fill zeros at all positions :-)

Greetings,
    </ntr> :)

>This is not the solution to your problem, but maybe you can still use it somehow:   :-)


You're darned tootin' it's not a solution!

It's worse than O(n), as every reference to the array is going to incur the quasi-initialized overhead.


(I'm assuming as in most cases each array element is going to be accessed more than once).

Of course it is going to incurr overhead, I was not talking about array i/o but about the zeroing operation :-)

Otherwise, it is pointless to discuss array-initialization in O(1) if you are not willing to sacrafice something somewhere.

Personally, I would (if possible at all) redesign the accessing logic, so a hash-map or a linked-list would be used instead of an array, and there you would anyway have to meet the overhead problem, even if initialization would be possible in O(1).

As J.R. said - "Sometimes you've gotta lose to win" :-)       (pardon my bad English)

Greetings,
    </ntr> :)

You can initialize an array on O(1) incurring only O(1) overhead on all array accesses
http://mmlab.ceid.upatras.gr/dstructures/Array_Initialization.pdf