Initially, your datastructure looks like it's just pigeon-holing data (unrelated, but see bucket sort), but your example of the 'special' structure is a little confusing. Terms like stack, queue, dequeue, trie, red-black-tree, list, etc -- are all there to facilitate easier communication.
The datastructure I describe consists of two arrays, just as
I said. No stack, no queue, no dequeue, no trie, no tree, no
list. Just an array on integers, that is,
U integers
equidistant apart. Just the same way you have an array of integers in C. The trick is just that you say
my array
lies from here to here in memory, and you initially
accept whatever values happen to be in that segment of
memory. (Although you might use a stack for array B).
Does this 'special structure' have a name?
That I am not sure of. The technique is described in
Kurt Mehlhorn: "Data structures and algorithms 1: sorting and searching" in Brauer, Rozenberg and Salomaa (Ed): EATCS monographs on theoretical computer science. Berlin, Heidelberg, New York, Tokyo: Springer-Verlag, 1984. Section III.8.1
where it is used to implement a
bit vector.
What are you trying to emulate?
A bit vector ;-)
As it stands, all classical operations being O(1) is only doable when your datastructure is as large as the domain space, right?
Yes, and I had hoped that was clear from the description.
It's not used very frequently. I understand this is just a question to see if it's possible, but where would this be used and is there a space to fit it?
I've used it once in an academic paper, describing a technique to create a triangulation on a 2-manifold, by applying a sequence of vertex-splits starting from a minimal triangulation. The main result used
O (n log n) time (with
n the number of vertices of
the triangulation), but by using
n of the described datastructures, the sequence can be obtained in
linear time (as long as you have
Θ (n2) scratch space available).
I have no pressing need to implement this in Perl right now. But I would like to know whether it's possible to do
something similar in Perl.
Abigail
