When saying binary tree, I thought of a trie actually. I know it's still O(log n) so does not satisfy the conditions, but a binary trie's code is not as complicated as that of a balanced binary tree.

As for initializing memory: the C library certainly won't initialize the whole array when calling malloc. However, on multi-user OS, the system has to initialize all the pages allocated by a process, for security reasons. If it would not do that, you could get vulnerable informations by allocating much memory and searching for daat that other processes freed but hav not zeroed. This does not take much time because 1. malloc tries to reuse the memory freed by a process, so it doesn't have to ask for a new chunk evry time, 2. the os can do it in idle time, so you don't have to wait for it when you allocate the memory, 3. zeroing a chunk of memory is fast. The first reason may not count with very large arrays, as malloc gets thoes with mmap, and when they're freed they're munmapped.

The question you asked still holds however, because using such a structure is good even in such OS'es, as you may use it many time, and you don't have to zero it evry time the same process clears and reuses one. I still don't know if it can be done in Perl.

In reply to Re: Re: Data structure challenge by ambrus
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.