Augmenting Data Structures

Augmenting Data Structures

An interesting type of caching is where the data is stored inside the main data structure, rather than in a separate cache. Instead of recalculating derivative data every time you need it, a faster way is to store the data in the data structure. This is a form of caching that saves the time of recalculation, which need be done only once. If the data ever changes, the calculations must be redone and stored again. Hence, this method works best where data is unchanging, but can also tolerate modifications.

As an example of augmentation, consider a struct defined to represent a line segment (e.g. in a CAD drawing program). The struct contains four fields, for the x and y coordinates of the start and end points:

    struct line_segment {
        int x1, y1; // Start point
        int x2, y2; // End point
    };

Consider the computation of the length of the line segment, using:

    float flen = sqrtf((y2 - y1) * (y2 - y1) 
                     + (x2 - x1) * (x2 - x1));

If the length is a common calculation, it can be beneficial to cache the length of the line segment as an extra field in the struct:

    struct line_segment {
        int x1, y1; // Start point
        int x2, y2; // End point
        float length; // Length of line segment
    };

Whenever this length is needed during calculation it is immediately available as a field member. However, it is important to be careful that there is no consistency problem (where the length field is not the true length of the line segment). The main danger is that the length field won’t be recalculated every time one of the other fields change.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++