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=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,24d7acf9b853aac8 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news4.google.com!feeder.news-service.com!85.214.198.2.MISMATCH!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Natasha Kerensikova Newsgroups: comp.lang.ada Subject: Re: S-expression I/O in Ada Date: Wed, 18 Aug 2010 13:24:52 +0000 (UTC) Organization: A noiseless patient Spider Message-ID: References: <547afa6b-731e-475f-a7f2-eaefefb25861@k8g2000prh.googlegroups.com> <4c6bd750$0$6893$9b4e6d93@newsspool2.arcor-online.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Injection-Date: Wed, 18 Aug 2010 13:24:52 +0000 (UTC) Injection-Info: mx01.eternal-september.org; posting-host="Mda950WjNwNLAFOE7yJXQw"; logging-data="2881"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/QRWQhv7ASObP93uRIOnFM" User-Agent: slrn/0.9.9p1 (FreeBSD) Cancel-Lock: sha1:bY5fjdjC4LqepfRF7Z9HegsbIK4= Xref: g2news1.google.com comp.lang.ada:13484 Date: 2010-08-18T13:24:52+00:00 List-Id: On 2010-08-18, Georg Bauhaus wrote: > The difference in complexity, in both time and space, is likely > present in other operations. The Implementation Advice in the > LRM stipulates that Vector is likely an array, internally. It is > in GNAT's Vectors, last time I checked. In addition to Cursor based > operations, Vectors have Index based operations, like > arrays. Lists don't have them; I trust that Vectors have the > lowest overhead for directly accessing specific elements of any > container, e.g. "the elements at index 5 and 5 plus offset". > If you wanted the same for a list then this could mean linear > traversal. (At least when there are no auxiliary tables internal > to the list implementation, which might in turn be implemented > using a vector kind of thing, exposing a need for a vector > abstraction...) Yes, I do clearly see the advantage of Vectors over Doubly_Linked_Lists. What I have trouble with is the point of having Doubly_Linked_Lists. They must somehow have a specific use, otherwise they wouldn't have been included and everybody would use Vectors instead. Well, there is the Splice and Swap_Links stuff, and they probably make a significant difference when they are called a lot of times on large objects. That still look very specialized, and therefore very weak. Hence my impression of missing something more important. There is probably a difference in complexity for all operations, but they are not specified, and generally not predictable. Well, Vectors have cache-friendliness, D_L_Lists have (probably) more memory overhead per element, non-tail insertion should be less efficient on Vectors, etc. But these are pretty small and platform-specific details, I believe it's way too early in my project to care about them. So I'm basically face the question of Vectors vs D_L_Lists in a situation where they are about as efficient (mostly appends and linear traversal) and where I only need the interface common to both containers. That's a tough choice. (What is sure on the other hand is that I will rely on Cursor, and probably even make a S_Expressions.Cursor, to make switching as easy as possible.) Thanks for your explanations, Natacha