Re: Multiple keys for a map

[Peter Brooks <peter.h.m.brooks@gmail.com>]

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.