in reply to Data structure challenge

With Perl, you can make initializing and clearing constant by using autovivication with arrays. Allocate the @A as an empty array. Setting any value will expand the array and set the other values to undef. This is O(N) but it is fast. Clearing is emptying out the entire array. It also has the advantage that the size of the array is the largest value used. Your data structure uses autovivication for the A array so it has the same performance but more overhead.

It is also important to realize the importance of the constants to running time. Preallocating the array pays O(U) cost in initialization but makes each operation more efficient. When inserting N items close to U, this can be significant.

Replies are listed 'Best First'.
Re: Data structure challenge
by Abigail-II (Bishop) on Mar 17, 2004 at 20:21 UTC
    Setting any value will expand the array and set the other values to undef.
    Well, yes, but that exactly what the challange wants you to avoid. You don't want to spend time creating undefined values.
    Your data structure uses autovivication for the A array so it has the same performance but more overhead.
    No. It's important to realize I did not describe the A array in Perl terms. Think C, or even better, assembler. Just declare an array as a chunk of memory where integers are stored. No initialization of the elements allowed - just accept whatever values are in memory.

    Abigail

[reply]

In Section Meditations