From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-05-21 11:01:28
"Joaquin M Lopez Munoz" <joaquin_at_[hidden]> wrote in message
> Hello Gennadiy, I'm returning to this discussion. Excuse
> the big delay.
> By the end of your post, you wrote:
>> I am not really crazy about the term Bookmark. IMO Order/Index is much
>> better reflect the nature of the concepts we are trying to model. But
>> is step in right direction IMO.
> Well, let me use Index/Bookmark if only during this
> discussion so as to not introduce further confusion,
> since I think you agree with me it is concepts we're
> most interested now, rather than words.
> I'm not in love with "bookmark" either, it is just a
> hack word I came by with some resonance to the
> concept it is being used to refer to here.
> Now, returning to the original flow of your post:
> Gennadiy Rozental <gennadiy.rozental <at> thomson.com> writes:
>> That's the primary reason I would need an Index. Aa Order may have have
>> different complexity guarantees. But in some cases I need partucular
>> to be performed much faster then it is guaranted by order search
>> Essentially I am looking for an ability to do something like this:
>> address_book_t ab;
>> typedef address_book_t::order<2>::type full_name_order;
>> // this operation is compile time
>> full_name_order fno = ab.get_order<FullName>();
>> // this operation has constant complexity, since Last name Index provide
>> direct access
>> p = fno.get_index<LastName>::equal_range( "Smith" );
>> In some cases Index could have non-constant complexity, but still could
>> used to significantly speedup orderred collection search. Lets say I have
>> Input messages log ordered sequencially (meaning that the order is just
>> natuaral order messages where comming in). And I have int64 number of
>> comming in every day. Now for this order I want to define Time index to
>> speedup lookup for messages in partucilar time interval. This operation
>> probably wont be constant (due to continues nature of time) but still
>> be implemented much faster then global serach through messages
>> In addition for the same collection I may want to define Symbol (some
>> attribute in a messages) order. And for that order I need first letter
>> My primary point in above examples is that both Order and Index are
>> class citizents and current desing doesn't account for the latter.
>> > > IMO we need another level of indirection that would support Index
>> > > within an
>> > > Order concept. I do not see how existing design could handle this.
> Well, if we concentrate now on the kind of data structures
> we'd need in order to achieve what you request, I come up with the
> following conclusions:
> 1. If the index to be sped up is of the ordered kind, then
> the only way to have faster lookups for clusters of elements
> (which, according to my terminology, are groups of elements
> equivalent under some sorting criterion compatible to that
> used by the index, see http://tinyurl.com/zm6h3), we'd probably
> have to resort to hashing (which improves rb-tree O(log n)
> lookup) and have some inner structures like
> storing pointers to the first element of each cluster. This
> has to be properly synchronized with the ordered index on
It could be hash, it could be random access or it could be any other custom
faster lookup. This is essencially is just a way to jump particulat position
in the Order based on some conditions. I may have records ordered by
creation time for last week and index that allows me to jump to start of
todays and yestadays entries.
> 2. If the index to be sped up is of the sequenced kind, we've
> got a problem: you require that the bookmark refer
> to clusters by using iterators from the index itself, as
> implied in your example:
> p = fno.get_index<LastName>::equal_range( "Smith" );
> and explicitly stated by you in a previous post:
> "All indexes for the same order present the same
> iterator which is a view iterator."
> This is AFAICS impossible if the index is sequenced,
I may misunderstand what sequenced order is. I understand it as just a
"natural" order entries where added into collection with. Why couldn't I
have an Index that would allow me to jump directly to the every 10000th
> since the elements can be freely rearranged and thus
> a cluster need not be adjacent (from the point of view
> of the sequenced index iterator).
What do you mean by rearanged and cluster here?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk