Re: [boost] [serialization] request: low-level info about order of serialization
I'm slowly designing the addition of serialization support to Boost.MultiIndex, and come up with a need that, AFAIK, the current serialization library does not cover:
The serialization of a multi_index_container should ensure that the order in which elements appear is preserved for all indices of the container.
Appear?
This implies serializing the elements and then recording the appropriate rearrangements in each index. I'm writing the code for serializing these rearrangements in an efficient manner as some sort of "diff" sequences, using an algorithm called "longest increasing subsequence" (LIS).
The algorithm would greatly benefit for some low-level API by the serialization lib that, given an object reference, would return the order in which that object was serialized. I guess this information is already available internally, as the lib must keep track of previously saved objects.
If this requirement is deemed too exotic to provide to the general user, well, I can write something myself without aid from the lib, but I thought I should ask at least :)
It seems too exotic to me. The focus of the serialization library is to re-create exactly that which was there before. So far, that has already been possible with the API provided. Some containers (e.g. slist) required a little bit of special handling to preserve sequence but this did not require any change in the basic API. All of this special handling is part of the implementation of the container in question. I'm really not sure what your doing, so without knowing more its hard for me to comment. Robert Ramey
Hi Robert, Robert Ramey ha escrito:
I'm slowly designing the addition of serialization support to Boost.MultiIndex, and come up with a need that, AFAIK, the current serialization library does not cover:
The serialization of a multi_index_container should ensure that the order in which elements appear is preserved for all indices of the container.
Appear?
Ummm, I guess I'm not explaining myself, let me try with an example: consider a multi_index_container like this: typedef multi_index_container< int, indexed_by< sequenced<>, sequenced<>
bilist;
Then, when serializing such a bilist, the order maintained by indices #0 and #1 must be recorded separately. Roughly speaking, this involves: 1. serializing the elements in the order induced by index #0. 2. traversing index #1 and serializing a record of rearrangements with respect to index #0. Step 2 can be accomplished in a simple manner by serializing pointers to the (previously serialized) elements, but in the order induced by index #1. As Boost.Serialization keeps track of previously stored objects, this will work OK. To further exemplify this, consider a particular bilist like this: index #0: [begin(),end) = 1 4 3 5 2 6 index #1: [begin(),end) = 1 3 5 6 2 4 then all the info we need to reconstruct the container can be saved as: 1 4 3 5 2 6 &1 &3 &5 &6 &2 &4 where & means we save a pointer to a previously serialized element. I hope everything's clear up to this point. But now, we can do better: it is not necessary to save that much info for reconstructing index #1, as we really only need the "difference" with respect to the order induced by index #0. In fact, index #1 has the same order as index #0 except that elements 4 and 2 are relocated. So we can instead save this info (sort of): 1 4 3 5 2 6 &2 &4 and at reconstruction time we can simply relocate those elements in index #1 whose position differ from that in index #0. Generally speaking, the best algorithm for computing such a rearrangement between index #1 and index #0 involves calculating what's called a "longest increasing subsequence"; check for instance http://tinyurl.com/6ouog for details. And now we get to the core of my request: this algorithm needs to know the order in which the base elements were serialized in step 1, in the manner I propose in my previous post: given an object, return an ordinal corresponding to the position that object was serialized in the archive. I'm not saying this request is worth honoring, but at least I want to make sure you know exactly why I need it. Of course, I can record that information myself, but it feels like duplicate work as your lib most likely already has it. If I haven't made myself clear please do ask. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
This implies serializing the elements and then recording the appropriate rearrangements in each index. I'm writing the code for serializing these rearrangements in an efficient manner as some sort of "diff" sequences, using an algorithm called "longest increasing subsequence" (LIS).
The algorithm would greatly benefit for some low-level API by the serialization lib that, given an object reference, would return the order in which that object was serialized. I guess this information is already available internally, as the lib must keep track of previously saved objects.
If this requirement is deemed too exotic to provide to the general user, well, I can write something myself without aid from the lib, but I thought I should ask at least :)
It seems too exotic to me.
The focus of the serialization library is to re-create exactly that which was there before. So far, that has already been possible with the API provided. Some containers (e.g. slist) required a little bit of special handling to preserve sequence but this did not require any change in the basic API. All of this special handling is part of the implementation of the container in question.
I'm really not sure what your doing, so without knowing more its hard for me to comment.
Robert Ramey
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Joaquín Mª López Muñoz -
Robert Ramey