From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,2cb1f0b6d642e1dc X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news2.google.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!nx01.iad01.newshosting.com!209.197.12.246.MISMATCH!nx02.iad01.newshosting.com!newshosting.com!198.186.194.249.MISMATCH!transit3.readnews.com!news-out.readnews.com!transit4.readnews.com!s09-10.readnews.com!not-for-mail Date: Mon, 28 Mar 2011 22:48:57 -0400 From: Hyman Rosen User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9 MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Pascal Calling Convention References: <9b04626e-567d-408c-aab3-39b964b3ffd6@l2g2000prg.googlegroups.com> <4d90efdd$1$14806$882e7ee2@usenet-news.net> <330393be-cb82-4cd8-ba44-6e59af7b75bf@v11g2000prb.googlegroups.com> <4d90fd41$1$14782$882e7ee2@usenet-news.net> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <4d9148d2$1$14782$882e7ee2@usenet-news.net> NNTP-Posting-Host: 9265433a.usenet-news.net X-Trace: DXC=>QS5eQciU8Y55omkZDZNYVQFZ3T]GPM]WmX0AG3X_jU_JL On 3/28/2011 6:08 PM, Adam Beneschan wrote: > On top of that, I don't see why anyone would prefer this over the > trivial structure that just allocates N bytes, initializes them to 0, > and sets a byte to 1 to add an element to the set, etc. That > structure has non-constant initialization, but so what? > Initialization will only take place once for a set; the other > operations are likely to be performed a lot more, and your code > performs multiple indexed accesses for every operation instead of just > one. And the initialization can often be done with a single machine > instruction. I didn't invent this data structure - I came across it in a paper and kept track of it because it made for a very good interview question. It's a structure no one has ever seen before, it's easy to describe and it's easy to program the operations. (Needless to say, many of the people to whom I've given the exercise fail miserably.) And it's a good program to keep at hand to serve as a counterexample when programming languages want access to uninitialized data to be undefined behavior. It's more sensible to regard such data as having arbitrary but fixed values, subject to a validity check. The particular need described in the paper was for a kind of graph where sets of nodes needed to be created and torn down quickly, and where such a set could potentially have millions of members while it typically only had a handful. They needed to avoid the initialization cost of setting many elements to zero, and this is the structure they invented. (In any case, you can't tell someone to go use an O(N) data structure when they've told you they want an O(1) one.)