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.

In reply to Re: Data structure challenge by flyingmoose
in thread Data structure challenge by Abigail-II

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.