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=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.224.126.137 with SMTP id c9mr5056307qas.2.1379496846443; Wed, 18 Sep 2013 02:34:06 -0700 (PDT) X-Received: by 10.49.3.134 with SMTP id c6mr1993416qec.0.1379496846426; Wed, 18 Sep 2013 02:34:06 -0700 (PDT) Path: border1.nntp.dca3.giganews.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!d5no354626qap.0!news-out.google.com!gv3ni456qab.0!nntp.google.com!d5no392154qap.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Wed, 18 Sep 2013 02:34:06 -0700 (PDT) In-Reply-To: <10z06jaj3ok8l$.tmrmqhwjgloi.dlg@40tude.net> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=105.236.35.136; posting-account=p-xPhAkAAADjHQWEO7sFME2XBdF1P_2H NNTP-Posting-Host: 105.236.35.136 References: <4f66d847-d030-4aa9-8bdf-9bcc5f3a0852@googlegroups.com> <3al7xx87ldc3.67wd6mjqten8.dlg@40tude.net> <10z06jaj3ok8l$.tmrmqhwjgloi.dlg@40tude.net> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Multiple keys for a map From: Peter Brooks Injection-Date: Wed, 18 Sep 2013 09:34:06 +0000 Content-Type: text/plain; charset=ISO-8859-1 X-Original-Bytes: 2466 Xref: number.nntp.dca.giganews.com comp.lang.ada:183378 Date: 2013-09-18T02:34:06-07:00 List-Id: On Wednesday, 18 September 2013 09:22:33 UTC+2, Dmitry A. Kazakov wrote: > On Tue, 17 Sep 2013 10:49:15 -0700 (PDT), Peter Brooks wrote: > > > > > On Tuesday, 17 September 2013 18:52:37 UTC+2, Dmitry A. Kazakov wrote: > > >> > > >> Maps can be used to index such a table, or red-black trees, or whatever. > > >> > > >> You could also take an existing light-weight RDBMS, e.g. SQLite3 or > > >> Berkeley DB. There exist many Ada bindings to SQLite3. > > >> > > > Thank you, yes, I'm hoping to avoid that overhead > > If you want a better than O(n) search you need a map (or an equivalent of) > for each search criterion. With wildcarded triplets it gives 7 > maps/indices: > > x,y,z -> Element > *,y,z -> Bucket of (x,y,z) keys or other references to elements in above > x,*,* > x,y,* > x,*,* > *,y,* > *,*,z > > It is quite straightforward to implement. > That makes good sense - with a graph as well, it'd go up to 14, which is still quite reasonable in terms of overhead. I'll look into it. I see that it's quite easy to make it all memory resident, so there doesn't need to be any disc overhead.