Re: Data structure challenge

Seems interesting, but you kind of lost me. I'm easy to lose sometimes, so don't take this as a knock on your post. IMHO, this would be more understandable if you used more terms found in the data structure references. 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. Anyhow, as it stands, you've lost me. Does this 'special structure' have a name? What are you trying to emulate? I can sort of grok the intent, but an explanation of the workings and principle is probably in order.

As it stands, all classical operations being O(1) is only doable when your datastructure is as large as the domain space, right? In many cases, this means working on small data sets or with huge amounts of data. Result? 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? If one datastructure fit everywhere, we wouldn't have the cool montage of data-structures, of course, so I guess I've made your point :)

Also, the cost of a hash function that maps to a completely unique value (as noted in my previous paragraph) is expensive both in time and space. Maybe Perl is cool and doesn't make an array as wide as it is and can leave them sparse...but can it really? Not sure. Hence this is why hashes collide and tend to be a little slow -- but the hash function is less expensive since collisions are allowed (not speaking Perl, but stuff in general) -- and collapsing down to a smaller value is important.

Comment on Re: Data structure challenge

Replies are listed 'Best First'.
Re: Data structure challenge by Abigail-II (Bishop) on Mar 17, 2004 at 20:49 UTC
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 `Θ (n²)` 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	[reply]
Re: Re: Data structure challenge by flyingmoose (Priest) on Mar 17, 2004 at 21:23 UTC
Thanks for typing this -- this makes it a lot more clear what is going on. Interesting stuff... Again I apologize for my long list of questions too... Infinite telecoms and project managers will do that to you. I'll take a better look at this when I get home...	[reply]